A cut of a graph (V, E) is a partition of a graph into two non-empty
sets A and B. Each set contains only the vertices that connect one
vertex in the set to another in the set. Meanwhile, there are also edges
connecting the vertices from set A to set B and vice versa. For eg.
Similarly we have directed graph. Edges, that cross from A, to B are called are crossing edges.
In a graph with n nodes, you can either put them in set A, or set B. This gives us 2n cuts of the graph. However, since each set must be nonempty, it is actually 2n-2. Meanwhile, a crossing edge of a cut (A, B) is an edge whose endpoint is in A and head is in B.
Also, see the minimum cut problem or min cut problem.
In a graph with n nodes, you can either put them in set A, or set B. This gives us 2n cuts of the graph. However, since each set must be nonempty, it is actually 2n-2. Meanwhile, a crossing edge of a cut (A, B) is an edge whose endpoint is in A and head is in B.
Also, see the minimum cut problem or min cut problem.
0 comments:
Post a Comment