# 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.

Title | cut |
---|---|

Canonical name | Cut |

Date of creation | 2013-03-22 13:00:53 |

Last modified on | 2013-03-22 13:00:53 |

Owner | vampyr (22) |

Last modified by | vampyr (22) |

Numerical id | 5 |

Author | vampyr (22) |

Entry type | Definition |

Classification | msc 05C20 |

Related topic | MaximumFlowminimumCutTheorem |

Defines | minimum cut |