Difference between revisions of "Graph Cut"

From Cohen Courses
Jump to navigationJump to search
 
Line 1: Line 1:
 
n 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.<br>
 
n 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.<br>
Min-Cut: A cut is minimum if the size of the cut is not larger than the size of any other cut.
+
Min-Cut: A cut is minimum if the size of the cut is not larger than the size of any other cut.<br>
 
Max-Cut: A cut is maximum if the size of the cut is not smaller than the size of any other cut.
 
Max-Cut: A cut is maximum if the size of the cut is not smaller than the size of any other cut.
  
 
(Text taken from Wikipedia: http://en.wikipedia.org/wiki/Cut_(graph_theory))
 
(Text taken from Wikipedia: http://en.wikipedia.org/wiki/Cut_(graph_theory))

Latest revision as of 02:28, 2 November 2011

n 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.
Min-Cut: A cut is minimum if the size of the cut is not larger than the size of any other cut.
Max-Cut: A cut is maximum if the size of the cut is not smaller than the size of any other cut.

(Text taken from Wikipedia: http://en.wikipedia.org/wiki/Cut_(graph_theory))