Bipartite graph
A bipartite or bipartite graph is a mathematical model for relations between the elements of two sets. It is very well suited for the study of assignment problems. Furthermore, for bipartite graphs can be many graph properties with significantly less effort to calculate than is possible in the general case.
Definitions
A simple graph (V set of vertices, set of edges E ) is called bipartite or few, if his node can be divided into two disjoint subsets A and B, so that no edges run within both subsets between the nodes. That is true for an edge either and or and. The amount then called bipartition of the graph and the quantities and partition classes. In simplified terms, a bipartite graph is a graph in which two groups of nodes exist, within which no nodes are interconnected.
The graph is called complete bipartite if there exists a bipartition such that each node is connected to each of nodes. Such a graph is also called, and wherein each of the number of nodes and. A complete bipartite graph in which is or is star graph.
Properties
- The pair number corresponds to the vertex cover number.
- The partition classes are already by definition stable quantities.
- With the algorithm of Hopcroft and Karp can be found in a greatest pairing and also determine the stability number.
- The chromatic index equal to its maximum degree. A valid edge-coloring can be determined in.
- Every bipartite graph is 2- knotenfärbbar. Thus, each partition class is assigned a color. Conversely, every 2- colorable graph is bipartite.
- A regular bipartite graph has a perfect matching.
- A graph is bipartite if and only if it contains no odd cycle.
- All bipartite graphs are Class 1 graphs, their Kantenchromatische number therefore corresponds to its maximum degree.
- For bipartite graphs the list chromatic index is equal to the chromatic index. This bipartite graphs are a class of graphs for which applies the list coloring conjecture.
- For bipartite graphs, the total chromatic number and the maximum degree. So shall the total coloring conjecture for bipartite graphs.
With a simple algorithm based on depth-first search is useful to determine whether a graph is bipartite, and determine a valid partition or 2- coloring in linear time.
Application
Generalization
A k- partiter graph is a graph whose set of nodes can be divided into partitions so that there is no edge between two nodes in a partition.