Gráfico de Kneser
En teoría de grafos , el grafo de Kneser K ( n , k ) (alternativamente KG n , k ) es el grafo cuyos vértices corresponden a los subconjuntos de elementos k de un conjunto de n elementos , y donde dos vértices son adyacentes si y solo si el dos conjuntos correspondientes son inconexos . Los gráficos de Kneser llevan el nombre de Martin Kneser , quien los investigó por primera vez en 1956.
El gráfico de Kneser K (2 n - 1, n - 1) es el gráfico impar O n ; en particular, O 3 = K (5, 2) es el gráfico de Petersen (ver figura superior derecha).
Como Kneser ( 1956 ) conjeturado, el número cromático de la Kneser gráfico K ( n , k ) para es exactamente n - 2 k + 2 ; por ejemplo, el gráfico de Petersen requiere tres colores en cualquier coloración adecuada. Esta conjetura se demostró de varias formas.
El gráfico de Johnson J ( n , k ) es el gráfico cuyos vértices son los subconjuntos de k elementos de un conjunto de n elementos, siendo dos vértices adyacentes cuando se encuentran en un conjunto de elementos ( k - 1) . El gráfico de Johnson J ( n , 2) es el complemento del gráfico de Kneser K ( n , 2) . Los gráficos de Johnson están estrechamente relacionados con el esquema de Johnson , y ambos llevan el nombre de Selmer M. Johnson .
La generalizada Kneser gráfico K ( n , k , s ) tiene el mismo conjunto de vértices como el Kneser gráfico K ( n , k ) , pero conecta dos vértices siempre que corresponden a los conjuntos que se cruzan en s o menos elementos ( Denley 1997 ). Por tanto, K ( n , k , 0) = K ( n , k ) .
El gráfico de Kneser bipartito H ( n , k ) tiene como vértices los conjuntos de k y n - k elementos extraídos de una colección de n elementos. Dos vértices están conectados por una arista siempre que un conjunto sea un subconjunto del otro. Al igual que el gráfico de Kneser, es un vértice transitivo con grado El gráfico de Kneser bipartito se puede formar como una cubierta doble bipartita de K ( n , k ) en la que se hacen dos copias de cada vértice y se reemplaza cada borde por un par de bordes que conectan los pares correspondientes de vértices ( Simpson 1991). El gráfico de Kneser bipartito H (5, 2) es el gráfico de Desargues y el gráfico de Kneser bipartito H ( n , 1) es un gráfico de corona .
.jpg/440px-Kneser_graph_KG(7,3).jpg)
.jpg){kind=link}