Graf bipartit complet: diferència entre les revisions

Contingut suprimit Contingut afegit

En línia

Revisió del 20:24, 23 març 2021

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]

@@ Línia 15: / Línia 15: @@
 == Propietats ==
-* Sigui <math>K_{m,n}</math> un graf bipartit amb <math>\left|V_1\right|=m</math> i <math>\left|V_2\right|=n</math>, es verifica que <math>\left|E\right| = \left|V_1\right|\cdot\left|V_2\right| = m\cdot n</math> i <math>K_{m,n}\,</math> posseeix <math>m^{n-1}\cdot n^{m-1}</math> [[Arbre d'expansió|arbres d'expansió]].
+* Sigui <math>K_{m,n}</math> un graf bipartit amb <math>\left|V_1\right|=m</math> i <math>\left|V_2\right|=n</math>, es verifica que <math>\left|E\right| = \left|V_1\right|\cdot\left|V_2\right| = m\cdot n</math> i <math>K_{m,n}\,</math> posseeix <math>m^{n-1}\cdot n^{m-1}</math> [[Arbre d'expansió|arbres d'expansió]].<ref>{{ref-llibre |cognom=Jungnickel |nom=Dieter |títol=Graphs, Networks and Algorithms |pàgines=557 |editorial=Springer |any=2012 |isbn=9783642322785 |capítol=Algorithms and Computation in Mathematics |edició=5}}</ref>
 * Donat un graf bipartit, comprovar si conté un subgraf bipartit complet <math>K_{i, i}</math> per un paràmetre <math>i</math> és un problema [[NP-complet]].<ref>{{ref-llibre |cognom1=Garey |nom1=Michael R. |cognom2=Johnson |nom2=David S. |títol=Computers and Intractability: A Guide to the Theory of NP-Completeness |pàgines=196 |capítol=[GT24] Balanced complete bipartite subgraph |editor=W. H. Freeman |any=1979 |isbn=0-7167-1045-5}}</ref>
 * Un [[graf planar]] no pot contenir ''K''<sub>3,3</sub> com a subconjunt, i un graf planar exterior (sense vèrtexs interns) no pot contenir ''K''<sub>3,2</sub> com a subconjunt. (No són [[Condició suficient|condicions suficients]] per a la planaritat i la planaritat exterior, però són necessàries). D'altra banda, segons el [[Test de planaritat#Teorema de Wagner|teorema de Wagner]], tot graf no planar conté ''K''<sub>3,3</sub> o bé el [[graf complet]] ''K''<sub>5</sub> com a subconjunts.<ref>{{harvnb|Diestel|2005|p=105}}</ref>
 * Tot graf bipartit complet de la forma <math>K_{i, i}</math> és un [[graf de Moore]].<ref>{{ref-llibre |cognom=Biggs |nom=Norman |títol=Algebraic Graph Theory |pàgines=181 |editorial=Cambridge University Press |any=1993 |isbn=9780521458979}}</ref>
+* 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.<ref>{{ref-publicació | cognom1 = Bandelt | nom1 = H.-J. | cognom2 = Dählmann | nom2 = A. | cognom3 = Schütte | nom3 = H. | doi = 10.1016/0166-218X(87)90058-8 | exemplar = 3 | publicació = Discrete Applied Mathematics | mr = 878021 | pàgines = 191–215 | títol = Absolute retracts of bipartite graphs | volum = 16 | any = 1987 }}.</ref>
 == Referències ==