cut Cut 2002-08-30 00:48:20 2002-08-30 14:39:44 Definition minimum cut % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here On a digraph, define a \emph{sink} to be a vertex with out-degree zero and a \emph{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 \emph{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 \emph{minimal cuts}, where the weight of the cut is minimized for a particular graph.