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 gráfico bipartito completo o biclique es un tipo especial de gráfico bipartito donde cada vértice del primer conjunto está conectado a cada vértice del segundo conjunto. [1] [2]
Un gráfico bipartito completo es un gráfico cuyos vértices se pueden dividir en dos subconjuntos V 1 y V 2 de modo que ninguna arista tenga ambos puntos finales en el mismo subconjunto, y cada arista posible que pueda conectar vértices en diferentes subconjuntos sea parte del gráfico. Es decir, es un gráfico bipartito ( V 1 , V 2 , E ) tal que por cada dos vértices v 1 ∈ V 1 y v 2 ∈ V 2 , v 1 v 2 es una arista en E . Un gráfico bipartito completo con particiones de tamaño | V 1 | = metro y | V 2 | = n , se denota K m , n ; [1] [2] cada dos gráficas con la misma notación son isomorfas .
Ejemplos
Para cualquier k , K 1, k se llama estrella . [2] Todos los gráficos bipartitos completos que son árboles son estrellas.
La gráfica K 3,3 se llama gráfica de utilidad . Este uso proviene de un rompecabezas matemático estándar en el que se deben conectar tres servicios públicos a tres edificios; es imposible resolver sin cruces debido a la no planaridad de K 3,3 . [6]
Las bicliques máximas encontradas como subgrafos del dígrafo de una relación se llaman conceptos . Cuando se forma una red tomando encuentros y uniones de estos subgrafos, la relación tiene un concepto de red inducida . Este tipo de análisis de relaciones se denomina análisis de conceptos formales .
Propiedades
Dado un gráfico bipartito, probar si contiene un subgrafo bipartito completo Ki, i para un parámetro i es un problema NP-completo . [8]
Cada gráfico bipartito completo. K n , n es un gráfico de Moore y una jaula ( n ,4) . [10]
Los gráficos bipartitos completos K n , n y K n , n +1 tienen el máximo número posible de aristas entre todos los gráficos 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 gráficos k -partitos y gráficos que evitan camarillas más grandes como subgrafos en el teorema de Turán , y estos dos gráficos bipartitos completos son ejemplos de gráficos de Turán , los gráficos extremos para este problema más general. [11]
La matriz de adyacencia de un gráfico 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 gráfico 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 }.
Todo grafo bipartito completo es un grafo modular : cada triplete de vértices tiene una mediana que pertenece a los caminos más cortos entre cada par de vértices. [15]
Ver también
Gráfico libre de bicliques , una clase de gráficos dispersos definidos evitando subgrafos bipartitos completos
^ abc Diestel, Reinhard (2005), Teoría de grafos (3.ª ed.), Springer , ISBN3-540-26182-6. Edición electrónica, página 17.
^ ab 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, ISBN0191630624.
^ Leer, Ronald C.; Wilson, Robin J. (1998), Atlas de gráficos , Clarendon Press, pág. ii, ISBN9780198532897.
^ Jungnickel, Dieter (2012), Gráficos, redes y algoritmos, algoritmos y computación en matemáticas, vol. 5, Springer, pág. 557, ISBN9783642322785.
^ 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, ISBN9781118030745.
^ Bandelt, H.-J.; Dählmann, A.; Schütte, H. (1987), "Retracciones absolutas de gráficos bipartitos", Matemáticas aplicadas discretas , 16 (3): 191–215, doi : 10.1016/0166-218X(87)90058-8 , SEÑOR 0878021.