En la teoría de grafos , una rama de las matemáticas , el grafo símplex κ( G ) de un grafo no dirigido G es en sí mismo un grafo, 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 difieran 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 grafo de camarillas, al igual que cada conjunto de un vértice y cada conjunto de dos vértices adyacentes. Por lo tanto, el grafo símplex contiene en su interior una subdivisión del propio G. El grafo símplex de un grafo completo es un grafo de hipercubo y el grafo símplex de un grafo de ciclo de longitud cuatro o más es un grafo de engranaje . El grafo símplex del grafo complementario de un grafo de trayectoria es un cubo de Fibonacci .
A los subgrafos completos de G se les puede dar la estructura de un álgebra mediana : la mediana de tres camarillas A , B y C está formada por los vértices que pertenecen a una mayoría de las tres camarillas. [1] Dos vértices cualesquiera que pertenezcan a este conjunto mediano deben pertenecer ambos al menos a uno de A , B o C y, por lo tanto, deben estar unidos por una arista, por lo que la mediana de tres camarillas es en sí misma una camarilla. El grafo símplex es el grafo mediano correspondiente a esta estructura de álgebra mediana. Cuando G es el grafo complementario de un grafo bipartito , a las camarillas de G se les puede dar una estructura más fuerte como una red distributiva , [2] y en este caso el grafo símplex es el grafo de la red. Como es cierto para los grafos medianos de manera más general, cada grafo símplex es en sí mismo bipartito .
El grafo símplex tiene un vértice por cada símplex en el complejo clique 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 grafo símplex, símplex en X ( G ) ) y las relaciones entre objetos (aristas en el grafo símplex, relaciones de inclusión entre símplex en X ( G ) ) están en correspondencia uno a uno entre X ( G ) y κ( G ) .
Los grafos simplex fueron introducidos por Bandelt y van de Vel (1989), [3] quienes observaron que un grafo simplex no tiene cubos si y solo si el grafo subyacente no tiene triángulos , y demostraron que el número cromático del grafo subyacente es igual al número mínimo n tal que el grafo simplex puede ser incrustado isométricamente en un producto cartesiano de n árboles. Como consecuencia de la existencia de grafos sin triángulos con un número cromático alto , demostraron que existen álgebras medianas topológicas bidimensionales que no pueden ser incrustadas en productos de un número finito de árboles reales . Imrich, Klavžar y Mulder (1999) también usan grafos simplex como parte de su prueba de que probar si un grafo no tiene triángulos o si es un grafo mediano puede realizarse con la misma rapidez.