Graf bipartit complet

En teoria de grafs un graf bipartit complet és aquell graf bipartit en el qual tots els vèrtexs de la partició $V_{1}$ estan connectats a tots els vèrtexs de la partició $V_{2}$ i viceversa.^[1]^[2]

Definició

Un graf bipartit complet $G:=(V_{1}\cup V_{2},E)\,$ és un graf bipartit tal que $\forall v_{1}\in V_{1},\forall \ v_{2}\in V_{2}\rightarrow i(v_{1},v_{2})\in E.\,$ És a dir, un graf bipartit complet està format per dos conjunts disjunts de vèrtexs i totes les possibles arestes que uneixen aquests vèrtexs.

El graf complet bipartit amb particions de mida $\left|V_{1}\right|=m$ i $\left|V_{2}\right|=n,$ és denotat com $K_{m,n}\,$ .

Exemples

K_3,1
K_3,2
K_3,3

Propietats

Sigui $K_{m,n}$ un graf bipartit amb $\left|V_{1}\right|=m$ i $\left|V_{2}\right|=n$ , es verifica que $\left|E\right|=\left|V_{1}\right|\cdot \left|V_{2}\right|=m\cdot n$ i $K_{m,n}\,$ posseeix $m^{n-1}\cdot n^{m-1}$ arbres d'expansió.^[3]
Donat un graf bipartit, comprovar si conté un subgraf bipartit complet $K_{i,i}$ per un paràmetre $i$ és un problema NP-complet.^[4]
Un graf planar no pot contenir K_3,3 com a subconjunt, i un graf planar exterior (sense vèrtexs interns) no pot contenir K_3,2 com a subconjunt. (No són condicions suficients per a la planaritat i la planaritat exterior, però són necessàries). D'altra banda, segons el teorema de Wagner, tot graf no planar conté K_3,3 o bé el graf complet K₅ com a subconjunts.^[5]
Tot graf bipartit complet de la forma $K_{i,i}$ és un graf de Moore.^[6]
Tot graf bipartit complet és un graf modular, és a dir, cada triplet de vèrtexs té una mediana que pertany als camins més curts entre cada parell possible d'aquests vèrtexs.^[7]

Referències

↑ Bondy, John Adrian; Murty, U. S. R.. Graph Theory with Applications. North-Holland, 1976, p. 5. ISBN 0-444-19451-7.
↑ Diestel 2005, p. 17
↑ Jungnickel, Dieter. «Algorithms and Computation in Mathematics». A: Graphs, Networks and Algorithms. 5. Springer, 2012, p. 557. ISBN 9783642322785.
↑ Garey, Michael R.; Johnson, David S. «[GT24] Balanced complete bipartite subgraph». A: W. H. Freeman. Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, p. 196. ISBN 0-7167-1045-5.
↑ Diestel 2005, p. 105
↑ Biggs, Norman. Algebraic Graph Theory. Cambridge University Press, 1993, p. 181. ISBN 9780521458979.
↑ Bandelt, H.-J.; Dählmann, A.; Schütte, H. «Absolute retracts of bipartite graphs». Discrete Applied Mathematics, 16, 3, 1987, pàg. 191–215. DOI: 10.1016/0166-218X(87)90058-8.

Bibliografia

Diestel, Reinhard. Graph Theory. 3rd. Springer, 2005. ISBN 3-540-26182-6. (Electronic edition).

Vegeu també

[bm-1] Bondy, John Adrian; Murty, U. S. R.. Graph Theory with Applications. North-Holland, 1976, p. 5. ISBN 0-444-19451-7.

[d-2] Diestel 2005, p. 17

[3] Jungnickel, Dieter. «Algorithms and Computation in Mathematics». A: Graphs, Networks and Algorithms. 5. Springer, 2012, p. 557. ISBN 9783642322785.

[4] Garey, Michael R.; Johnson, David S. «[GT24] Balanced complete bipartite subgraph». A: W. H. Freeman. Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, p. 196. ISBN 0-7167-1045-5.

[5] Diestel 2005, p. 105

[6] Biggs, Norman. Algebraic Graph Theory. Cambridge University Press, 1993, p. 181. ISBN 9780521458979.

[7] Bandelt, H.-J.; Dählmann, A.; Schütte, H. «Absolute retracts of bipartite graphs». Discrete Applied Mathematics, 16, 3, 1987, pàg. 191–215. DOI: 10.1016/0166-218X(87)90058-8.

[1]

[2]

[3]

[4]

[5]

[6]

[7]