PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very low 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

$\displaystyle 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)

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 25 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 5629 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)