Graph Cut
Jump to navigation
Jump to search
A Graph Cut is a graph node operation (graph partitioning) that creates two disjoint edge subsets.
- Context:
- It can range from being a Minimum Graph Cut to being a Maximum Graph Cut.
- It can be a Binary Graph Cut for a Binary Graph.
- See: Graph Operation, Graph, Set Partition.
References
2012
- http://en.wikipedia.org/wiki/Cut_(graph_theory)
- In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are in its cut-set.
In an unweighted undirected graph, the size or weight of a cut is the number of edges crossing the cut. In a weighted graph, the same term is defined by the sum of the weights of the edges crossing the cut.
In a flow network, an 's-t cut is a cut that requires the source and the sink to be in different subsets, and its cut-set only consists of edges going from the source's side to the sink's side. The capacity of an s-t cut is defined by the sum of capacity of each edge in the cut-set.
The cut of a graph can sometimes refer to its cut-set instead of the partition. ...
- A cut [math]\displaystyle{ C=(S,T) }[/math] is a partition of [math]\displaystyle{ V }[/math] of a graph [math]\displaystyle{ G=(V,E) }[/math].
- In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are in its cut-set.