Gráfico bipartito completo - Complete bipartite graph

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 {de lo contrario}} \ end {array}} \ right.}$
Diámetro	${\ Displaystyle \ left \ {{\ begin {array} {ll} 1 & m = n = 1 \\ 2 & {\ text {de lo contrario}} \ end {array}} \ right.}$
Circunferencia	${\ Displaystyle \ left \ {{\ begin {array} {ll} \ infty & m = 1 \ lor n = 1 \\ 4 & {\ text {de otro modo}} \ end {array}} \ right.}$
Automorfismos	${\ Displaystyle \ left \ {{\ begin {array} {ll} 2m! n! & n = m \\ m! n! & {\ text {de lo contrario}} \ 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.

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 . El propio Llull había realizado dibujos similares de gráficos completos tres siglos antes.

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, se trata de un gráfico bipartito ( V ₁ , V ₂ , E ) de tal manera que por cada dos vértices v ₁ ∈ V ₁ y V ₂ ∈ V ₂ , v ₁ v ₂ es una ventaja en E . Un gráfico bipartito completo con particiones de tamaño | V ₁ | = my | V ₂ | = n , se denota K _{m, n} ; cada dos gráficos con la misma notación son isomorfos .

Ejemplos de

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 . 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 .
• 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 a tres edificios; es imposible resolverlo sin cruces debido a la falta de planitud de K _3,3 .
• 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

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.
• 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 .
• Cada gráfico bipartito completo. K _{n , n} es una gráfica de Moore y una ( n , 4) - jaula .
• 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.
• 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.
• 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 .
• 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 .
• 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.

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