Grafo bipartito

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 $U$ e $V$, é dicir, cada aresta conecta un vértice en $U$ a outro en $V$. Os conxuntos de vértices $U$ e $V$ 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 $G=(U,V,E)$ para denotar un grafo bipartito cuxa partición ten as partes $U$ e $V$, con $E$ denotando as arestas do grafo. Se un grafo bipartito non está conectado, pode ter máis dunha bipartición; neste caso, a notación $(U,V,E)$ é útil para especificar unha bipartición particular que pode ser de importancia nunha aplicación. Se $|U|=|V|$, é dicir, se os dous subconxuntos teñen a mesma cardinalidade, entón $G$ chámase grafo bipartito equilibrado. Se todos os vértices do mesmo lado da bipartición teñen o mesmo grao, entón $G$ 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 K_n,m é o grafo bipartito $G=(U,V,E)$, 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. 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).
• 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 $\mathrm{deg}v$. A fórmula de suma de graos para un grafo bipartito indica que

$\sum _{v\in V}\mathrm{deg}v=\sum _{u\in U}\mathrm{deg}u=|E|.$

A secuencia de graos dun grafo bipartito é o par de listas que contén cada unha os graos das dúas partes $U$ e $V$. Por exemplo, o grafo bipartito completo K_3,5 ten unha secuencia de graos $(5,5,5),(3,3,3,3,3)$. 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 $(U,V,E)$ é unha matriz (0,1) de tamaño $|U|\times |V|$ que ten un un para cada par de vértices adxacentes e un cero para os non adxacentes. 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 $(U,V,E)$ pode usarse para modelar un hipergrafo no que Modelo:Mvar é o conxunto de vértices do hipergrafo, Modelo:Mvar é o conxunto de hiperarestas e Modelo:Mvar contén unha aresta desde un vértice de hipergrafo Modelo:Mvar ata unha aresta do hipergrafo Modelo:Mvar exactamente cando Modelo:Mvar é un dos extremos de Modelo:Mvar. Baixo esta correspondencia, as matrices de biadxacencia dos grafs bipartitos son exactamente as matrices de incidencia dos hipergrafos correspondentes.

Ciclo impar transversal

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.

Véxase tamén

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

• Modelo:Springer
• Information System on Graph Classes and their Inclusions: bipartite graph
• Modelo:Mathworld
• Bipartite graphs in systems biology and medicine