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 set.

La teoría de grafos en sí suele fecharse a partir del 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. 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₁<. /span> y V₂ de manera que ninguna arista tenga ambos puntos finales en el mismo subconjunto, y todas las posibles aristas que puedan conectar vértices en diferentes subconjuntos es parte del gráfico. Es decir, es un grafo bipartito (V₁, V₂, E) tal que por cada dos vértices v₁ ∈ V₁ y v₂ ∈ V< sub>2, v₁v₂ es una ventaja en E. Un gráfico bipartito completo con particiones de tamaño |V₁| = m y |< i>V₂| = n, se denota K_m,n; cada dos gráficas con la misma notación son isomorfas.

Ejemplos

• 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 libres de garra.
• El gráfico K_3,3 se llama el gráfico de utilidad. Este uso viene de un rompecabezas matemático estándar en el que tres utilidades deben estar conectadas a tres edificios; es imposible resolver sin cruces debido a la no planaridad de K_3,3.
• Los bicliques máximos encontrados como subgrafos del digraph de una relación se llaman conceptos. Cuando se forma una celosía tomando encuentros y unidas 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

K3,3	K4.4	K5,5
3 aristas	4 colores de borde	5 aristas
Polígonos complejos regulares de la forma 2{4}p han tenido gráficos bipartitos completos con 2p vértices (rojo y azul) y p2 2-edges. También se pueden dibujar como p aristas.

• Dado un gráfico bipartito, prueba si contiene un subgrafo bipartito completo K_i,i para un parámetroi es un problema completo de NP.
• Un gráfico plano no puede contener K_3,3 como menor; un gráfico externo no puede contener K_3,2 como menor (Estas condiciones no son suficientes para la planaridad y la planaridad externa, sino necesarias). Por el contrario, cada gráfica no plana contiene cualquiera 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 un gráfico Moore y un ()n,4)- jaula.
• Los gráficos bipartitos completos K_n,n y K_{n,n+ 1} tienen el número máximo posible de bordes entre todos los gráficos sin triángulo con el mismo número de vértices; este es el teorema de Mantel. El resultado de Mantel fue generalizado k- Gráficos y gráficos partitos que evitan las camarillas más grandes como subgrafos en el teorema de Turán, y estos dos gráficos bipartitos completos son ejemplos de gráficos Turán, los gráficos extremos para este problema más general.
• El gráfico bipartito completo K_m,n tiene un número de cobertura de vértice min{}m, n} y un número de cobertura de bordes max{}m, n}.
• El gráfico bipartito completo K_m,n tiene un conjunto de tamaño máximo independiente max{}m, n}.
• La matriz adyacencia de un gráfico bipartito completo K_m,n ha eigenvalues √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 ha eigenvalues 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^m−1 azotando árboles.
• Un gráfico bipartito completo K_m,n tiene una combinación máxima de tamaño min{}m,n}.
• Un gráfico bipartito completo K_n,n tiene un n-edge-coloring adecuado correspondiente a un cuadrado latino.
• Cada gráfico bipartito completo es un gráfico modular: cada triple de vértices tiene una mediana que pertenece a caminos más cortos entre cada par de vértices.