PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
cut (Definition)

On a digraph, define a sink to be a vertex with out-degree zero and a source to be a vertex with in-degree zero. Let $G$ be a digraph with non-negative weights and with exactly one sink and exactly one source. A cut $C$ on $G$ is a subset of the edges such that every path from the source to the sink passes through an edge in $C$ In other words, if we remove every edge in $C$ from the graph, there is no longer a path from the source to the sink.

Define the weight of $C$ as $$W_C = \sum_{e \in C} W(e)$$ where $W(e)$ is the weight of the edge $e$

Observe that we may achieve a trivial cut by removing all the edges of $G$ Typically, we are more interested in minimal cuts, where the weight of the cut is minimized for a particular graph.




"cut" is owned by vampyr.
(view preamble | get metadata)

View style:

See Also: maximum flow/minimum cut theorem

Also defines:  minimum cut
Log in to rate this entry.
(view current ratings)

Cross-references: minimal, graph, passes through, path, edges, subset, weights, in-degree, source, out-degree, vertex, sink, digraph
There are 34 references to this entry.

This is version 2 of cut, born on 2002-08-30, modified 2002-08-30.
Object id is 3398, canonical name is Cut.
Accessed 7426 times total.

Classification:
AMS MSC05C20 (Combinatorics :: Graph theory :: Directed graphs , tournaments)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)