Grafo bipartito completo

Gráfico bipartito donde cada nodo del primer conjunto está vinculado a todos los nodos del segundo conjunto

En el campo matemático de la teoría de grafos , un grafo bipartito completo o biclique es un tipo especial de grafo bipartito donde cada vértice del primer conjunto está conectado a cada vértice del segundo conjunto. ^{[1] [2]}

La teoría de grafos se suele fechar como algo que comienza con el trabajo de Leonhard Euler de 1736 sobre los Siete Puentes de Königsberg . Sin embargo, los dibujos de grafos bipartitos completos ya se imprimieron en 1669, en relación con una edición de las obras de Ramon Llull editada por Athanasius Kircher . ^{[3] [4]} El propio Llull había hecho dibujos similares de grafos completos tres siglos antes. ^[3]

Definición

Un grafo bipartito completo es un grafo cuyos vértices pueden ser particionados en dos subconjuntos V ₁ y V ₂ tales que ninguna arista tiene ambos puntos finales en el mismo subconjunto, y cada arista posible que podría conectar vértices en diferentes subconjuntos es parte del grafo. Es decir, es un grafo bipartito ( V ₁ , V ₂ , E ) tal que para cada dos vértices v ₁ ∈ V ₁ y v ₂ ∈ V ₂ , v ₁ v ₂ es una arista en E . Un grafo bipartito completo con particiones de tamaño | V ₁ | = m y | V ₂ | = n , se denota K _{m , n} ; ^{[1] [2]} cada dos grafos con la misma notación son isomorfos .

Ejemplos

Los gráficos de estrellas son K _1,3 , K _1,4 , K _1,5 y K _1,6 .

Un gráfico bipartito completo de K _4,7 que muestra que el problema de la fábrica de ladrillos de Turán con 4 sitios de almacenamiento (puntos amarillos) y 7 hornos (puntos azules) requiere 18 cruces (puntos rojos)

• Para cualquier k , K _{1, k} se llama estrella . ^[2] Todos los gráficos bipartitos completos que son árboles son estrellas.
  • El gráfico K _1,3 se denomina garra y se utiliza para definir los gráficos sin garra . ^[5]
• El gráfico K _3,3 se denomina gráfico de utilidades . Este uso proviene de un problema matemático estándar en el que tres servicios públicos deben estar conectados a tres edificios; es imposible resolverlo sin cruces debido a la falta de planaridad de K _3,3 . ^[6]
• Los biclíneos máximos que se encuentran como subgrafos del dígrafo de una relación se denominan conceptos . Cuando se forma un retículo tomando encuentros y uniones de estos subgrafos, la relación tiene un retículo de conceptos inducido . Este tipo de análisis de relaciones se denomina análisis formal de conceptos .

Propiedades

• Dado un gráfico bipartito, probar si contiene un subgráfico bipartito completo K _{i , i} para un parámetro  i es un problema NP-completo . ^[8]
• Un grafo plano no puede contener K _3,3 como menor ; un grafo exterior-planar no puede contener K _3,2 como menor (Estas no son condiciones suficientes para la planaridad y exterior-planaridad, pero son necesarias). Por el contrario, todo grafo no plano contiene K _3,3 o el grafo completo K ₅ como menor; este es el teorema de Wagner . ^[9]
• Todo grafo bipartito completo. K _{n , n} es un grafo de Moore y una jaula ( n ,4) . ^[10]
• Los grafos bipartitos completos K _{n , n} y K _{n , n +1} tienen el máximo número posible de aristas entre todos los grafos libres de triángulos con el mismo número de vértices; este es el teorema de Mantel . El resultado de Mantel se generalizó a grafos k -partitos y grafos que evitan camarillas más grandes como subgrafos en el teorema de Turán , y estos dos grafos bipartitos completos son ejemplos de grafos de Turán , los grafos extremales para este problema más general. ^[11]
• El gráfico bipartito completo K _{m , n} tiene un número de cobertura de vértices de min { m , n } y un número de cobertura de aristas de max { m , n }.
• El gráfico bipartito completo K _{m , n} tiene un conjunto independiente máximo de tamaño max { m , n }.
• La matriz de adyacencia de un grafo bipartito completo K _{m , n} tiene valores propios √ nm , − √ nm y 0; con multiplicidad 1, 1 y n + m − 2 respectivamente. ^[12]
• La matriz laplaciana de un grafo bipartito completo K _{m , n} tiene valores propios n + m , n , m y 0; con multiplicidad 1, m − 1 , n − 1 y 1 respectivamente.
• Un gráfico bipartito completo K _{m , n} tiene m ^{n −1} n ^{m −1} árboles de expansión . ^[13]
• Un gráfico bipartito completo K _{m , n} tiene una coincidencia máxima de tamaño min { m , n }.
• Un gráfico bipartito completo K _{n , n} tiene una coloración de arista n adecuada correspondiente a un cuadrado latino . ^[14]
• Todo grafo bipartito completo es un grafo modular : cada triple de vértices tiene una mediana que pertenece a los caminos más cortos entre cada par de vértices. ^[15]

Véase también

• Gráfico libre de bicliques , una clase de gráficos dispersos definidos por la evitación de subgrafos bipartitos completos
• Gráfico de corona , un gráfico formado al eliminar una coincidencia perfecta de un gráfico bipartito completo
• Gráfico multipartito completo , una generalización de gráficos bipartitos completos a más de dos conjuntos de vértices
• Ataque biclicuo

Referencias

1. Bondy, John Adrian ; Murty, USR (1976), Teoría de grafos con aplicaciones, Holanda Septentrional, pág. 5, ISBN 0-444-19451-7.
2. Diestel, Reinhard (2005), Teoría de grafos (3.ª ed.), Springer , ISBN 3-540-26182-6. Edición electrónica, página 17.
3. Knuth, Donald E. (2013), "Dos mil años de combinatoria", en Wilson, Robin; Watkins, John J. (eds.), Combinatoria: antigua y moderna , Oxford University Press, págs. 7–37, ISBN 0191630624.
4. Read, Ronald C.; Wilson, Robin J. (1998), Un atlas de gráficos , Clarendon Press, pág. ii, ISBN 9780198532897.
5. Lovász, László ; Plummer, Michael D. (2009), Teoría del emparejamiento, Providence, RI: AMS Chelsea, p. 109, ISBN 978-0-8218-4759-6, Sr.  2536865. Reimpresión corregida del original de 1986.
6. Gries, David ; Schneider, Fred B. (1993), Un enfoque lógico para las matemáticas discretas, Springer, pág. 437, ISBN 9780387941158.
7. Coxeter, Regular Complex Polytopes , segunda edición, pág. 114
8. Garey, Michael R. ; Johnson, David S. (1979), "[GT24] Subgrafo bipartito completo balanceado", Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , W. H. Freeman , pág. 196, ISBN 0-7167-1045-5.
9. Diestel 2005, pág. 105
10. Biggs, Norman (1993), Teoría de grafos algebraicos, Cambridge University Press, pág. 181, ISBN 9780521458979.
11. Bollobás, Béla (1998), Teoría de grafos moderna, Textos de posgrado en matemáticas , vol. 184, Springer, pág. 104, ISBN 9780387984889.
12. Bollobás (1998), pág. 266.
13. Jungnickel, Dieter (2012), Gráficos, redes y algoritmos, Algoritmos y computación en matemáticas, vol. 5, Springer, pág. 557, ISBN 9783642322785.
14. Jensen, Tommy R.; Toft, Bjarne (2011), Problemas de coloración de gráficos, Serie Wiley en Matemáticas discretas y optimización, vol. 39, Wiley, pág. 16, ISBN 9781118030745.
15. Bandelt, H.-J.; Dählmann, A.; Schütte, H. (1987), "Retractos absolutos de grafos bipartitos", Discrete Applied Mathematics , 16 (3): 191–215, doi : 10.1016/0166-218X(87)90058-8 , MR  0878021.