En teoría de grafos , una rama de las matemáticas , el gráfico simplex κ( G ) de un gráfico no dirigido G es en sí mismo un gráfico, con un nodo para cada camarilla (un conjunto de vértices mutuamente adyacentes) en G. Dos nodos de κ( G ) están unidos por una arista siempre que las dos camarillas correspondientes difieren en la presencia o ausencia de un solo vértice.
El conjunto vacío se incluye como una de las camarillas de G que se utilizan para formar el gráfico de camarillas, al igual que cada conjunto de un vértice y cada conjunto de dos vértices adyacentes. Por lo tanto, el gráfico simplex contiene una subdivisión del propio G. La gráfica simplex de una gráfica completa es una gráfica de hipercubo , y la gráfica simplex de una gráfica cíclica de longitud cuatro o más es una gráfica de engranajes . El gráfico simplex del gráfico complemento de un gráfico de trayectoria es un cubo de Fibonacci .
A los subgrafos completos de G se les puede dar la estructura de un álgebra de medianas : la mediana de tres camarillas A , B y C está formada por los vértices que pertenecen a la mayoría de las tres camarillas. [1] Dos vértices cualesquiera que pertenezcan a este conjunto mediano deben pertenecer al menos a uno de A , B o C y, por lo tanto, deben estar unidos por un borde, por lo que la mediana de tres camarillas es en sí misma una camarilla. La gráfica simplex es la gráfica mediana correspondiente a esta estructura de álgebra mediana. Cuando G es el gráfico complementario de un gráfico bipartito , a las camarillas de G se les puede dar una estructura más fuerte como una red distributiva , [2] y en este caso la gráfica simplex es la gráfica de la red. Como ocurre con los gráficos de medianas en general, cada gráfico simplex es en sí mismo bipartito .
El gráfico simplex tiene un vértice para cada simplex en el complejo de camarilla X ( G ) de G , y dos vértices están unidos por una arista cuando uno de los dos símplex correspondientes es una faceta del otro. Por lo tanto, los objetos (vértices en el gráfico simplex, simples en X ( G ) ) y las relaciones entre objetos (bordes en el gráfico simplex, relaciones de inclusión entre simplesx en X ( G ) ) están en correspondencia uno a uno entre X ( GRAMO ) y κ( GRAMO ) .
Los gráficos simplex fueron introducidos por Bandelt y van de Vel (1989), [3] quienes observaron que un gráfico simplex no tiene cubos si y sólo si el gráfico subyacente no tiene triángulos , y demostró que el número cromático del gráfico subyacente es igual al número mínimo n tal que el gráfico simplex pueda incrustarse isométricamente en un producto cartesiano de n árboles. Como consecuencia de la existencia de gráficos sin triángulos con alto número cromático , demostraron que existen álgebras topológicas de medianas bidimensionales que no pueden integrarse en productos de un número finito de árboles reales . Imrich, Klavžar y Mulder (1999) también utilizan gráficos simplex como parte de su prueba de que probar si un gráfico no tiene triángulos o si es un gráfico mediano se puede realizar con la misma rapidez.