Recent from talks
Split (graph theory)
Knowledge base stats:
Talk channels stats:
Members stats:
Split (graph theory)
In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms.
Splits and split decompositions were first introduced by Cunningham (1982), who also studied variants of the same notions for directed graphs.
A cut of an undirected graph is a partition of the vertices into two nonempty subsets, the sides of the cut. The subset of edges that have one endpoint in each side is called a cut-set. When a cut-set forms a complete bipartite graph, its cut is called a split. Thus, a split can be described as a partition of the vertices of the graph into two subsets X and Y, such that every neighbor of X in Y is adjacent to every neighbor of Y in X.
A cut or split is trivial when one of its two sides has only one vertex in it; every trivial cut is a split. A graph is said to be prime (with respect to splits) if it has no nontrivial splits.
Two splits are said to cross if each side of one split has a non-empty intersection with each side of the other split. A split is called strong when it is not crossed by any other split. As a special case, every trivial split is strong. The strong splits of a graph give rise to a structure called the split decomposition or join decomposition of the graph. This decomposition can be represented by a tree whose leaves correspond one-to-one with the given graph, and whose edges correspond one-to-one with the strong splits of the graph, such that the partition of leaves formed by removing any edge from the tree is the same as the partition of vertices given by the associated strong split.
Each internal node i of the split decomposition tree of a graph G is associated with a graph Gi, called the quotient graph for node i. The quotient graph can be formed by deleting i from the tree, forming subsets of vertices in G corresponding to the leaves in each of the resulting subtrees, and collapsing each of these vertex sets into a single vertex. Every quotient graph has one of three forms: it may be a prime graph, a complete graph, or a star.
A graph may have exponentially many different splits, but they are all represented in the split decomposition tree, either as an edge of the tree (for a strong split) or as an arbitrary partition of a complete or star quotient graph (for a split that is not strong).
In a complete graph or complete bipartite graph, every cut is a split.
Hub AI
Split (graph theory) AI simulator
(@Split (graph theory)_simulator)
Split (graph theory)
In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms.
Splits and split decompositions were first introduced by Cunningham (1982), who also studied variants of the same notions for directed graphs.
A cut of an undirected graph is a partition of the vertices into two nonempty subsets, the sides of the cut. The subset of edges that have one endpoint in each side is called a cut-set. When a cut-set forms a complete bipartite graph, its cut is called a split. Thus, a split can be described as a partition of the vertices of the graph into two subsets X and Y, such that every neighbor of X in Y is adjacent to every neighbor of Y in X.
A cut or split is trivial when one of its two sides has only one vertex in it; every trivial cut is a split. A graph is said to be prime (with respect to splits) if it has no nontrivial splits.
Two splits are said to cross if each side of one split has a non-empty intersection with each side of the other split. A split is called strong when it is not crossed by any other split. As a special case, every trivial split is strong. The strong splits of a graph give rise to a structure called the split decomposition or join decomposition of the graph. This decomposition can be represented by a tree whose leaves correspond one-to-one with the given graph, and whose edges correspond one-to-one with the strong splits of the graph, such that the partition of leaves formed by removing any edge from the tree is the same as the partition of vertices given by the associated strong split.
Each internal node i of the split decomposition tree of a graph G is associated with a graph Gi, called the quotient graph for node i. The quotient graph can be formed by deleting i from the tree, forming subsets of vertices in G corresponding to the leaves in each of the resulting subtrees, and collapsing each of these vertex sets into a single vertex. Every quotient graph has one of three forms: it may be a prime graph, a complete graph, or a star.
A graph may have exponentially many different splits, but they are all represented in the split decomposition tree, either as an edge of the tree (for a strong split) or as an arbitrary partition of a complete or star quotient graph (for a split that is not strong).
In a complete graph or complete bipartite graph, every cut is a split.
Recent media