## You are here

Homecut

## Primary tabs

# cut

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.

Defines:

minimum cut

Related:

MaximumFlowminimumCutTheorem

Type of Math Object:

Definition

Major Section:

Reference

## Mathematics Subject Classification

05C20*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections