Grafo bipartito

miniatura| 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..

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; . 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., p. 7. Se todos os vértices do mesmo lado da bipartición teñen o mesmo grao, entón  chámase birregular.

 Exemplos 
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..

Exemplos máis abstractos inclúen os seguintes:

 Toda árbore é bipartita. .
 Os grafos ciclo cun número par de vértices son bipartitos.
 Todo grafo plano cuxas caras teñen todas as lonxitudes par é bipartito. .
 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., p. 11. 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..

 Propiedades 

 Caracterización 
Os grafos bipartitos poden caracterizarse de varios xeitos diferentes:

 Un grafo non dirixido é bipartito se e só se non contén un ciclo impar.
 Un grafo é bipartito se e só se é de 2 cores, (é dicir, o seu número cromático é menor ou igual a 2)., p. 7.
 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.
 Un grafo é bipartito se e só se o espectro do grafo é simétrico..

 Teorema de Kőnig e grafos perfectos 
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.. . 

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.. 

 Grao 
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 
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., p. 17. 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  é o conxunto de vértices do hipergrafo,  é o conxunto de hiperarestas e  contén unha aresta desde un vértice de hipergrafo  ata unha aresta do hipergrafo  exactamente cando  é un dos extremos de . Baixo esta correspondencia, as matrices de biadxacencia dos grafs bipartitos son exactamente as matrices de incidencia dos hipergrafos correspondentes. 

 Ciclo impar transversal 
miniatura| 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. 

 Coincidencia 
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.. 
 Notas 


 Véxase tamén 

 Bibliografía 

 Outros artigos 
Dimensión bipartita, o número mínimo de grafos bipartitos completos cuxa unión é o grafo dado
Hipergrafo bipartito, unha xeneralización do grafo bipartito a hipergrafos.
Proxección de redes bipartitas, unha técnica con pesos para comprimir información sobre redes bipartitas
Grafo bipartito convexo, un grafo bipartito cuxos vértices poden ser ordenados de xeito que as veciñanzas dos vértices sexan contiguas
Grafo multipartito, unha xeneralización de grafos bipartitos a máis de dous subconxuntos de vértices
Grafos de paridade, unha xeneralización de grafos bipartitos na que cada dous camiños inducidos entre os mesmos dous puntos teñen a mesma paridade
Grafo dividido, un grafo no que os vértices poden dividirse en dous subconxuntos, un deles é independente e o outro é un clique
Problema de Zaraankiewicz sobre o número máximo de arestas nun grafo bipartito con subgrafos prohibidos
 Ligazóns externas 

 Information System on Graph Classes and their Inclusions : bipartite graph 

 Bipartite graphs in systems biology and medicine

Categoría:Teoría de grafos