Saltar ao contido

Grafo bipartito

Na Galipedia, a Wikipedia en galego.
Un grafo bipartito completo con m = 5 e n = 3
O grafo de Heawood é bipartito.

No campo matemático da teoría de grafos, un grafo bipartito (ou bigrafo) é un grafo cuxos vértices se poden dividir en dous conxuntos disxuntos e independentes e , é dicir, cada aresta conecta un vértice en a outro en . Os conxuntos de vértices e adoitan denominarse partes do grafo. De forma equivalente, un grafo bipartito é un grafo que non contén ciclos de lonxitude impar.[1][2]


Escríbese moitas veces para denotar un grafo bipartito cuxa partición ten as partes e , con denotando as arestas do grafo. Se un grafo bipartito non está conectado, pode ter máis dunha bipartición; [3] neste caso, a notación é útil para especificar unha bipartición particular que pode ser de importancia nunha aplicación. Se , é dicir, se os dous subconxuntos teñen a mesma cardinalidade, entón chámase grafo bipartito equilibrado.[4] Se todos os vértices do mesmo lado da bipartición teñen o mesmo grao, entón chámase birregular.

O exemplo máis común acontece cando se modelan relacións entre dúas clases diferentes de obxectos. Por exemplo, un grafo de xogadores de equipos de chave, cunha ligazón entre un xogador e un equipo se o xogador xoga nese equipo, é un exemplo natural dunha rede de afiliación, un tipo de grafo bipartito usado na análise de redes sociais.[5]

Exemplos máis abstractos inclúen os seguintes:

  • Toda árbore é bipartita. [6]
  • Os grafos ciclo cun número par de vértices son bipartitos.[6]
  • Todo grafo plano cuxas caras teñen todas as lonxitudes par é bipartito. [7]
  • O grafo bipartito completo en m e n vértices, indicado como Kn,m é o grafo bipartito , onde U e V son conxuntos disxuntos de tamaño m e n, respectivamente, e E conecta cada vértice en U con todos os vértices en V. Dedúcese que K m,n ten mn arestas.[8] Intimamente relacionados cos grafos bipartitos completos están os grafos de coroa, formados a partir de grafos bipartitos completos eliminando as arestas dunha coincidencia perfecta.[9]

Propiedades

[editar | editar a fonte]

Caracterización

[editar | editar a fonte]

Os grafos bipartitos poden caracterizarse de varios xeitos diferentes:

  • Un grafo non dirixido é bipartito se e só se non contén un ciclo impar.[10]
  • Un grafo é bipartito se e só se é de 2 cores, (é dicir, o seu número cromático é menor ou igual a 2).[4]
  • Un grafo é bipartito se e só se cada aresta pertence a un número impar de cortes, os subconxuntos mínimos de arestas cuxa eliminación aumenta o número de compoñentes do grafo.[11]
  • Un grafo é bipartito se e só se o espectro do grafo é simétrico.[12]

Teorema de Kőnig e grafos perfectos

[editar | editar a fonte]

Nos grafos bipartitos, o tamaño da cobertura mínima do vértice é igual ao tamaño da coincidencia máxima; este é o teorema de Kőnig.[13] [14]

Outra clase de resultados relacionados refírense aos grafos perfectos: todo grafo bipartito, o complemento de cada grafo bipartito, o grafo de liñas de cada grafo bipartito e o complemento do grafo de liñas de cada grafo bipartito son todos perfectos. A perfección dos grafos bipartitos é fácil de ver (o seu número cromático é dous e o seu tamaño máximo de clique tamén é de dous) mais a perfección dos complementos dos grafos bipartitos é menos trivial, e é outra reformulación do teorema de Kőnig. Este foi un dos resultados que motivou a definición inicial de grafos perfectos.[15]

Para un vértice, o número de vértices adxacentes chámase grao do vértice e denotase . A fórmula de suma de graos para un grafo bipartito indica que

A secuencia de graos dun grafo bipartito é o par de listas que contén cada unha os graos das dúas partes e . Por exemplo, o grafo bipartito completo K3,5 ten unha secuencia de graos . Os grafos bipartitos isomorfos teñen a mesma secuencia de graos. Porén, a secuencia de graos non identifica, en xeral, de forma única un gráafo bipartito; nalgúns casos, os grafos bipartitos non isomorfos poden ter a mesma secuencia de graos.

Relación con hipergrafos e grafos dirixidos

[editar | editar a fonte]

A matriz de biadxacencia dun grafo bipartito é unha matriz (0,1) de tamaño que ten un un para cada par de vértices adxacentes e un cero para os non adxacentes.[16] As matrices de biadxacencia pódense utilizar para describir equivalencias entre grafos bipartitos, hipergrafos e grafos dirixidos.

Un hipergrafo é unha estrutura combinatoria que, como un grafo non dirixido, ten vértices e arestas, mais na que as arestas poden unir conxuntos arbitrarios de vértices en lugar de ter que ter exactamente dous extremos. Un grafo bipartito pode usarse para modelar un hipergrafo no que U é o conxunto de vértices do hipergrafo, V é o conxunto de hiperarestas e E contén unha aresta desde un vértice de hipergrafo v ata unha aresta do hipergrafo e exactamente cando v é un dos extremos de e. Baixo esta correspondencia, as matrices de biadxacencia dos grafs bipartitos son exactamente as matrices de incidencia dos hipergrafos correspondentes.

Ciclo impar transversal

[editar | editar a fonte]
Un grafo cun ciclo transversal impar de tamaño 2: eliminando os dous vértices inferiores azuis sae un grafo bipartito.

Un ciclo impar transversal é un problema algorítmico NP-completo que pregunta, dada un grafo G = (V, E) e un número k, se existe un conxunto de k vértices cuxa eliminación de G faría que o grafo resultante fose bipartito.[17]

Coincidencia

[editar | editar a fonte]

Unha coincidencia nun grafo é un subconxunto das súas arestas, das que non hai dúas que compartan un punto final. Os algoritmos de tempo polinómico son coñecidos por moitos problemas algorítmicos sobre coincidencias, incluíndo a coincidencia máxima (atopar unha coincidencia que utilice o maior número de arestas posíbel),a coincidencia de peso máximo e o matrimonio estábel.[18]

  1. Diestel, Reinard (2005). Graph Theory. Graduate Texts in Mathematics. Springer. ISBN 978-3-642-14278-9. Consultado o 2012-02-27. 
  2. Asratian, Armen S. (1998). Bipartite Graphs and their Applications. Cambridge Tracts in Mathematics. Cambridge University Press. ISBN 9780521593458. .
  3. Chartrand, Gary; Zhang, Ping (2008). Chromatic Graph Theory. Discrete Mathematics And Its Applications 53. CRC Press. p. 223. ISBN 9781584888000. .
  4. 4,0 4,1 Asratian, Denley & Häggkvist (1998), p. 7.
  5. Wasserman, Stanley; Faust, Katherine (1994). Social Network Analysis: Methods and Applications. Structural Analysis in the Social Sciences 8. Cambridge University Press. pp. 299–302. ISBN 9780521387071. .
  6. 6,0 6,1 Scheinerman, Edward R. (2012). Mathematics: A Discrete Introduction. Cengage Learning. ISBN 9780840049421. .
  7. Bandelt, H.-J.; Chepoi, V. (2010). Combinatorics and geometry of finite and infinite squaregraphs 24. pp. 1399–1440. .
  8. Asratian, Denley & Häggkvist (1998), p. 11.
  9. Archdeacon, D.; Debowsky, M. (2004). Cycle systems in the complete bipartite graph minus a one-factor 284. pp. 37–43. .
  10. Bang-Jensen, Jørgen; Gutin, Gregory (2001). Digraphs: Theory, Algorithms and Applications (PDF) (1st ed.). Springer. p. 25. ISBN 9781852332686. Consultado o 2023-01-02. 
  11. Woodall, D. R. (1990). A proof of McKee's Eulerian-bipartite characterization. 
  12. Biggs, Norman (1994). Algebraic Graph Theory (2nd ed.). Cambridge University Press. p. 53. ISBN 9780521458979. .
  13. Kőnig, Dénes (1931). Gráfok és mátrixok. pp. 116–119. .
  14. Gross, Jonathan L. (2005). Graph Theory and Its Applications. Discrete Mathematics And Its Applications. CRC Press. ISBN 9781584885054. .
  15. Béla Bollobás (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. Springer. p. 165. ISBN 9780387984889. .
  16. Asratian, Denley & Häggkvist (1998), p. 17.
  17. Yannakakis, Mihalis (1978). Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78). pp. 253–264. doi:10.1145/800133.804355. 
  18. Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). "12. Assignments and Matchings". Network Flows: Theory, Algorithms, and Applications. Prentice Hall. pp. 461–509. .

Véxase tamén

[editar | editar a fonte]

Bibliografía

[editar | editar a fonte]

Outros artigos

[editar | editar a fonte]

Ligazóns externas

[editar | editar a fonte]