Gráfico bipartito completo

Gráfico bipartito donde cada vértice del primer conjunto está conectado a cada vértice del segundo conjunto

Gráfico bipartito completo
Un gráfico bipartito completo con m = 5 y n = 3
Vértices	n + m
Bordes	Minnesota
Radio	${\displaystyle \left\{{\begin{array}{ll}1&m=1\vee n=1\\2&{\text{otherwise}}\end{array}}\right.}$
Diámetro	${\displaystyle \left\{{\begin{array}{ll}1&m=n=1\\2&{\text{otherwise}}\end{array}}\right.}$
Circunferencia	${\displaystyle \left\{{\begin{array}{ll}\infty &m=1\lor n=1\\4&{\text{otherwise}}\end{array}}\right.}$
Automorfismos	${\displaystyle \left\{{\begin{array}{ll}2m!n!&n=m\\m!n!&{\text{otherwise}}\end{array}}\right.}$
Número cromático	2
Índice cromático	max { m , n }
Espectro	${\displaystyle \left\{0^{n+m-2},(\pm {\sqrt {nm}})^{1}\right\}}$
Notación	${\displaystyle K_{m,n}}$
Tabla de gráficos y parámetros

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 en sí misma se fecha típicamente como comenzando con el trabajo de 1736 de Leonhard Euler sobre los Siete Puentes de Königsberg . Sin embargo, ya se imprimieron dibujos de gráficos bipartitos completos ya 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 realizado dibujos similares de grafos 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 ₁ y V _{2 de} modo que ningún borde tenga ambos extremos en el mismo subconjunto, y cada borde posible que pueda conectar vértices en diferentes subconjuntos es parte del gráfico. Es decir, es un gráfico bipartito ( V ₁ , V ₂ , E ) tal que por cada dos vértices v ₁ ∈ V ₁ y v ₂ ∈ V ₂ , v ₁ v ₂ es una arista en E. Un gráfico bipartito completo con particiones de tamaño | V ₁ | = my | V ₂ | = n , se denota K _{m, n} ; ^{[1] [2]} cada dos gráficos con la misma notación son isomorfos .

Ejemplos

La estrella grafica 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 llama garra y se utiliza para definir los gráficos sin garras . ^[5]
• La gráfica K _3,3 se llama gráfica de utilidad . Este uso proviene de un acertijo matemático estándar en el que tres servicios públicos deben estar conectados cada uno a tres edificios; es imposible resolverlo sin cruces debido a la falta de planitud de K _3,3 . ^[6]

• Los bicliques máximos que se encuentran como subgráficos del dígrafo de una relación se denominan conceptos . Cuando se forma una celosía tomando encuentros y uniones de estos subgrafos, la relación tiene una celosía de concepto inducido . Este tipo de análisis de relaciones se denomina análisis de concepto formal .

Propiedades

Ejemplo K _{p , p} gráficos bipartitos completos ^[7]

K 3,3	K 4,4	K 5,5
3 colores de borde	4 colores de borde	5 colores de bordes
Los polígonos complejos regulares de la forma 2 {4} p tienen gráficos bipartitos completos con 2 p vértices (rojo y azul) y p 2 2 aristas. También se pueden dibujar como colorantes de bordes p .

• Dado un gráfico bipartito, probando si contiene una completa bipartito subgrafo K _{i , i} para un parámetro  i es un NP-completo problema. ^[8]
• Un gráfico plano no puede contener K _3,3 como menor ; un gráfico del plano exterior no puede contener K _3,2 como menor (estas no son condiciones suficientes para la planaridad y el plano exterior, pero son necesarias). A la inversa, cada gráfico no plano contiene K _3,3 o el gráfico completo K ₅ como menor; este es el teorema de Wagner . ^[9]
• Cada gráfico bipartito completo. K _{n , n} es una gráfica de Moore y una ( n , 4) - jaula . ^[10]
• Los gráficos bipartitos completos K _{n , n} y K _{n , n +1} tienen el número máximo posible de aristas entre todos los gráficos sin triángulos con el mismo número de vértices; este es el teorema de Mantel . El resultado de Mantel se generalizó a gráficas de k -partitas y gráficas que evitan camarillas más grandes como subgrafias en el teorema de Turán , y estas dos gráficas bipartitas completas son ejemplos de gráficas de Turán , las gráficas extremas para este problema más general. ^[11]
• El gráfico bipartito completo K _{m , n} tiene un vértice que cubre el número de min { m , n } y un borde que cubre el número 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 √ 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 , my 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 un color de borde n apropiado correspondiente a un cuadrado latino . ^[14]
• Cada 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]

Ver también

• Gráfico sin biclices , una clase de gráficos dispersos que se definen al evitar los 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 biclique

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), Graph Theory (3.a 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.), Combinatorics: Ancient and Modern , Oxford University Press, págs. 7-37, ISBN 0191630624.
4. Leer, Ronald C .; Wilson, Robin J. (1998), An Atlas of Graphs , Clarendon Press, pág. ii, ISBN 9780198532897.
5. Lovász, László ; Plummer, Michael D. (2009), Teoría de emparejamiento , Providence, RI: AMS Chelsea, p. 109, ISBN 978-0-8218-4759-6, MR  2536865. Reimpresión corregida del original de 1986.
6. Gries, David ; Schneider, Fred B. (1993), A Logical Approach to Discrete Math , Springer, pág. 437, ISBN 9780387941158.
7. Coxeter, Politopos complejos regulares , segunda edición, p.114
8. Garey, Michael R .; Johnson, David S. (1979), "[GT24] Subgrafo bipartito completo equilibrado", Computadoras e intratabilidad: Una guía para la teoría de NP-Completeness , W. H. Freeman , p. 196 , ISBN 0-7167-1045-5.
9. Diestel 2005 , p. 105
10. Biggs, Norman (1993), Teoría de gráficos algebraicos , Cambridge University Press, p. 181, ISBN 9780521458979.
11. Bollobás, Béla (1998), Teoría de grafos modernos , Textos de posgrado en matemáticas , 184 , Springer, p. 104, ISBN 9780387984889.
12. Bollobás (1998) , p. 266.
13. Jungnickel, Dieter (2012), Gráficos, redes y algoritmos , algoritmos y computación en matemática, 5 , Springer, p. 557, ISBN 9783642322785.
14. Jensen, Tommy R .; Toft, Bjarne (2011), Graph Coloring Problems , Wiley Series in Discrete Mathematics and Optimization, 39 , Wiley, p. 16, ISBN 9781118030745.
15. 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 , MR 0878021 .