|
|
|
|
|
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)
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 MSC: | 05C20 (Combinatorics :: Graph theory :: Directed graphs , tournaments) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|