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 {\displaystyle V_{1}} estan connectats a tots els vèrtexs de la partició V 2 {\displaystyle V_{2}} i viceversa.[1][2]

Definició

Un graf bipartit complet G := ( V 1 ∪ V 2 , E ) {\displaystyle G:=(V_{1}\cup V_{2},E)\,} és un graf bipartit tal que ∀ v 1 ∈ V 1 , ∀   v 2 ∈ V 2 → i ( v 1 , v 2 ) ∈ E . {\displaystyle \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 | V 1 | = m {\displaystyle \left|V_{1}\right|=m} i | V 2 | = n , {\displaystyle \left|V_{2}\right|=n,} és denotat com K m , n {\displaystyle K_{m,n}\,} .

Exemples

  • K3,1
    K3,1
  • K3,2
    K3,2
  • K3,3
    K3,3

Propietats

  • Sigui K m , n {\displaystyle K_{m,n}} un graf bipartit amb | V 1 | = m {\displaystyle \left|V_{1}\right|=m} i | V 2 | = n {\displaystyle \left|V_{2}\right|=n} , es verifica que | E | = | V 1 | ⋅ | V 2 | = m ⋅ n {\displaystyle \left|E\right|=\left|V_{1}\right|\cdot \left|V_{2}\right|=m\cdot n} i K m , n {\displaystyle K_{m,n}\,} posseeix m n − 1 ⋅ n m − 1 {\displaystyle 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 {\displaystyle K_{i,i}} per un paràmetre i {\displaystyle i} és un problema NP-complet.[4]
  • Un graf planar no pot contenir K3,3 com a subconjunt, i un graf planar exterior (sense vèrtexs interns) no pot contenir K3,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é K3,3 o bé el graf complet K₅ com a subconjunts.[5]
  • Tot graf bipartit complet de la forma K i , i {\displaystyle 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

  1. ↑ Bondy, John Adrian; Murty, U. S. R.. Graph Theory with Applications. North-Holland, 1976, p. 5. ISBN 0-444-19451-7. 
  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.

Bibliografia

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

Vegeu també

  • Graf bipartit
  • Graf complet