.svg)
No campomatemático dateoría de grafos, ungrafo bipartito (oubigrafo) é ungrafo cuxosvértices se poden dividir en dous conxuntosdisxuntos eindependentes e, é dicir, cadaaresta conecta unvértice en a outro en. Os conxuntos de vértices e adoitan denominarsepartes do grafo. De forma equivalente, un grafo bipartito é un grafo que non conténciclos 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 mesmacardinalidade, entón chámase grafo bipartitoequilibrado.[4] Se todos os vértices do mesmo lado da bipartición teñen o mesmograo, entón chámasebirregular.
O exemplo máis común acontece cando se modelanrelació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 dunharede de afiliación, un tipo de grafo bipartito usado naanálise de redes sociais.[5]
Exemplos máis abstractos inclúen os seguintes:
Os grafos bipartitos poden caracterizarse de varios xeitos diferentes:
Nos grafos bipartitos, o tamaño dacobertura mínima do vértice é igual ao tamaño dacoincidencia máxima; este é oteorema de Kőnig.[13][14]
Outra clase de resultados relacionados refírense aosgrafos perfectos: todo grafo bipartito, ocomplemento de cada grafo bipartito, ografo 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 seunúmero cromático é dous e o seu tamañomá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ámasegrao do vértice e denotase. Afó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 completoK3,5 ten unha secuencia de graos. Os grafos bipartitosisomorfos 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.
Amatriz 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.
Unhipergrafo é 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 queU é o conxunto de vértices do hipergrafo,V é o conxunto de hiperarestas eE contén unha aresta desde un vértice de hipergrafov ata unha aresta do hipergrafoe exactamente candov é un dos extremos dee. Baixo esta correspondencia, as matrices de biadxacencia dos grafs bipartitos son exactamente asmatrices de incidencia dos hipergrafos correspondentes.
Unciclo impar transversal é un problemaalgorítmicoNP-completo que pregunta, dada un grafoG = (V,E) e un númerok, se existe un conxunto dek vértices cuxa eliminación deG faría que o grafo resultante fose bipartito.[17]
Unhacoincidencia nun grafo é un subconxunto das súas arestas, das que non hai dúas que compartan un punto final. Os algoritmos detempo polinómico son coñecidos por moitos problemas algorítmicos sobre coincidencias, incluíndo acoincidencia máxima (atopar unha coincidencia que utilice o maior número de arestas posíbel),acoincidencia de peso máximo e omatrimonio estábel.[18]
 | Wikimedia Commons ten máis contidos multimedia na categoría: Grafo bipartito |
