Английская Википедия:Complete bipartite graph
Шаблон:Short description Шаблон:Infobox graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.[1][2]
Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete bipartite graphs were already printed as early as 1669, in connection with an edition of the works of Ramon Llull edited by Athanasius Kircher.[3][4] Llull himself had made similar drawings of complete graphs three centuries earlier.[3]
Definition
A complete bipartite graph is a graph whose vertices can be partitioned into two subsets Шаблон:Math and Шаблон:Math such that no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph. That is, it is a bipartite graph Шаблон:Math such that for every two vertices Шаблон:Math andШаблон:Math, Шаблон:Math is an edge in Шаблон:Mvar. A complete bipartite graph with partitions of size Шаблон:Math and Шаблон:Math, is denoted Шаблон:Math;[1][2] every two graphs with the same notation are isomorphic.
Examples
- For any Шаблон:Mvar, Шаблон:Math is called a star.[2] All complete bipartite graphs which are trees are stars.
- The graph Шаблон:Math is called a claw, and is used to define the claw-free graphs.[5]
- The graph Шаблон:Math is called the utility graph. This usage comes from a standard mathematical puzzle in which three utilities must each be connected to three buildings; it is impossible to solve without crossings due to the nonplanarity of Шаблон:Math.[6]
- The maximal bicliques found as subgraphs of the digraph of a relation are called concepts. When a lattice is formed by taking meets and joins of these subgraphs, the relation has an Induced concept lattice. This type of analysis of relations is called formal concept analysis.
Properties
| Шаблон:Math | Шаблон:Math | Шаблон:Math |
|---|---|---|
| Файл:Complex polygon 2-4-3-bipartite graph.png | Файл:Complex polygon 2-4-4 bipartite graph.png | Файл:Complex polygon 2-4-5-bipartite graph.png |
| Файл:Complex polygon 2-4-3.png 3 edge-colorings |
Файл:Complex polygon 2-4-4.png 4 edge-colorings |
Файл:Complex polygon 2-4-5.png 5 edge-colorings |
| Regular complex polygons of the form Шаблон:Math have complete bipartite graphs with Шаблон:Math vertices (red and blue) and Шаблон:Math 2-edges. They also can also be drawn as Шаблон:Mvar edge-colorings. | ||
- Given a bipartite graph, testing whether it contains a complete bipartite subgraph Шаблон:Math for a parameter Шаблон:Mvar is an NP-complete problem.[8]
- A planar graph cannot contain Шаблон:Math as a minor; an outerplanar graph cannot contain Шаблон:Math as a minor (These are not sufficient conditions for planarity and outerplanarity, but necessary). Conversely, every nonplanar graph contains either Шаблон:Math or the complete graph Шаблон:Math as a minor; this is Wagner's theorem.[9]
- Every complete bipartite graph. Шаблон:Math is a Moore graph and a Шаблон:Math-cage.[10]
- The complete bipartite graphs Шаблон:Math and Шаблон:Math have the maximum possible number of edges among all triangle-free graphs with the same number of vertices; this is Mantel's theorem. Mantel's result was generalized to Шаблон:Mvar-partite graphs and graphs that avoid larger cliques as subgraphs in Turán's theorem, and these two complete bipartite graphs are examples of Turán graphs, the extremal graphs for this more general problem.[11]
- The complete bipartite graph Шаблон:Math has a vertex covering number of Шаблон:Math and an edge covering number of Шаблон:Math
- The complete bipartite graph Шаблон:Math has a maximum independent set of size Шаблон:Math
- The adjacency matrix of a complete bipartite graph Шаблон:Math has eigenvalues Шаблон:Math, Шаблон:Math and 0; with multiplicity 1, 1 and Шаблон:Math respectively.[12]
- The Laplacian matrix of a complete bipartite graph Шаблон:Math has eigenvalues Шаблон:Math, Шаблон:Mvar, Шаблон:Mvar, and 0; with multiplicity 1, Шаблон:Math, Шаблон:Math and 1 respectively.
- A complete bipartite graph Шаблон:Math has Шаблон:Math spanning trees.[13]
- A complete bipartite graph Шаблон:Math has a maximum matching of size Шаблон:Math
- A complete bipartite graph Шаблон:Math has a proper [[edge coloring|Шаблон:Mvar-edge-coloring]] corresponding to a Latin square.[14]
- Every complete bipartite graph is a modular graph: every triple of vertices has a median that belongs to shortest paths between each pair of vertices.[15]
See also
- Biclique-free graph, a class of sparse graphs defined by avoidance of complete bipartite subgraphs
- Crown graph, a graph formed by removing a perfect matching from a complete bipartite graph
- Complete multipartite graph, a generalization of complete bipartite graphs to more than two sets of vertices
- Biclique attack
References
- ↑ 1,0 1,1 Шаблон:Citation.
- ↑ 2,0 2,1 2,2 Шаблон:Citation. Electronic edition, page 17.
- ↑ 3,0 3,1 Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation. Corrected reprint of the 1986 original.
- ↑ Шаблон:Citation.
- ↑ Coxeter, Regular Complex Polytopes, second edition, p.114
- ↑ Шаблон:Citation.
- ↑ Шаблон:Harvnb
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Harvtxt, p. 266.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
