Lesson plan
Dicut
In mathematics, a dicut is a set of edges in a directed graph, defined from a partition of the vertices into two subsets, so that each edge that has an endpoint in both subsets is directed from the first subset to the second. This is analogous to a cut in undirected graphs (although the cut refers to the partition of vertices rather than the set of edges between them, so it is more accurate to say that the dicut is analogous to the cut-set). Each strongly connected component of the graph must be entirely contained in one of the two subsets, so a strongly connected graph has no nontrivial dicuts. Often, the underlying directed graph is assumed to be weakly connected; if not, the empty edge set would correspond to multiple vertex partitions. The second of the two subsets in a dicut, a subset of vertices with no edges that exit the subset, is called a closure. The closure problem is the algorithmic problem of finding a dicut, in an edge-weighted directed graph, whose total weight is as large as possible. It can be solved in polynomial time. In weakly connected planar graphs, dicuts and cycles are dual concepts. The dual graph of a directed graph, embedded in the plane, is a graph with a vertex for each face of the given graph, and a dual edge between two dual vertices when the corresponding two faces are separated by an edge.…
Article summary
In mathematics, a dicut is a set of edges in a directed graph, defined from a partition of the vertices into two subsets, so that each edge that has an endpoint in both subsets is directed from the first subset to the second. This is analogous to a cut in undirected graphs (although the cut refers to the partition of vertices rather than the set of edges between them, so it is more accurate to say that the dicut is analogous to the cut-set). Each strongly connected component of the graph must be entirely contained in one of the two subsets, so a strongly connected graph has no nontrivial dicuts. Often, the underlying directed graph is assumed to be weakly connected; if not, the empty edge set would correspond to multiple vertex partitions. The second of the two subsets in a dicut, a subset of vertices with no edges that exit the subset, is called a closure. The closure problem is the algorithmic problem of finding a dicut, in an edge-weighted directed graph, whose total weight is as large as possible. It can be solved in polynomial time. In weakly connected planar graphs, dicuts and cycles are dual concepts. The dual graph of a directed graph, embedded in the plane, is a graph with a vertex for each face of the given graph, and a dual edge between two dual vertices when the corresponding two faces are separated by an edge.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.