Gráfico bipartito completo

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]

La teoría de grafos en sí suele datarse en su inicio con el trabajo de Leonhard Euler de 1736 sobre los Siete Puentes de Königsberg . Sin embargo, ya en 1669 se imprimieron dibujos de gráficos bipartitos completos, en relación con una edición de las obras de Ramon Llull editada por Athanasius Kircher . ^[3]^[4] El propio Llull había realizado dibujos similares de gráficos completos tres siglos antes. ^[3]

Definición

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 \in V 1$ y $v$ $2$ $\in$ $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 1,3$ se llama garra , y se utiliza para definir las gráficas libres de garras . ^[5]
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]
Un gráfico plano no puede contener $K 3,3$ como menor ; un gráfico plano externo no puede contener $K 3,2$ como menor (estas no son condiciones suficientes para la planaridad y la planaridad externa, pero son necesarias). Por el contrario, todo gráfico no plano contiene $K 3,3$ o el gráfico completo $K 5$ como menor; este es el teorema de Wagner . ^[9]
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]
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 bordes de $max {m, n}.$
El gráfico bipartito completo $K m, n$ tiene un conjunto máximo independiente de tamaño $max {m, n}.$
La matriz de adyacencia de un gráfico bipartito completo $K m, n$ tiene valores propios $\sqrt nm$ , $- \sqrt 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}.$
Un gráfico bipartito completo $K n, n$ tiene una coloración de bordes n adecuada correspondiente a un cuadrado latino . ^[14]
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
Gráfico de corona , un gráfico formado eliminando 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 biclique

Referencias

^ ab Bondy, John Adrian ; Murty, USR (1976), Teoría de grafos con aplicaciones, Holanda Septentrional, pág. 5, ISBN 0-444-19451-7.
^ abc Diestel, Reinhard (2005), Teoría de grafos (3.ª ed.), Springer , ISBN 3-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, ISBN 0191630624.
^ Leer, Ronald C.; Wilson, Robin J. (1998), Atlas de gráficos , Clarendon Press, pág. ii, ISBN 9780198532897.
^ Lovász, László ; Plummer, Michael D. (2009), Teoría del emparejamiento, Providence, RI: AMS Chelsea, p. 109, ISBN 978-0-8218-4759-6, señor 2536865. Reimpresión corregida del original de 1986.
^ Gries, David ; Schneider, Fred B. (1993), Un enfoque lógico de las matemáticas discretas, Springer, p. 437, ISBN 9780387941158.
^ Coxeter, Politopos complejos regulares , segunda edición, p.114
^ Garey, Michael R .; Johnson, David S. (1979), "[GT24] Subgrafo bipartito completo equilibrado", Computadoras e intratabilidad: una guía para la teoría de la integridad NP , W. H. Freeman , p. 196, ISBN 0-7167-1045-5.
^ Diéstel 2005, pag. 105
^ Biggs, Norman (1993), Teoría de grafos algebraicos, Cambridge University Press, pág. 181, ISBN 9780521458979.
^ Bollobás, Béla (1998), Teoría de grafos moderna, Textos de posgrado en matemáticas , vol. 184, Springer, pág. 104, ISBN 9780387984889.
^ Bollobás (1998), pág. 266.
^ Jungnickel, Dieter (2012), Gráficos, redes y algoritmos, algoritmos y computación en matemáticas, vol. 5, Springer, pág. 557, ISBN 9783642322785.
^ 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.
^ 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.