¿Por qué el número de vértices de un grafo de camarilla es menor que el de su grafo padre?

Question

Estoy leyendo sobre la teoría de grafos y el ejemplo que da para un Subgráfico de clicas se ve así...

Ahora dice que el gráfico inferior es "obviamente" el gráfico de camarilla para el superior. ¿Esto se debe a que es el grafo más pequeño que se puede hacer para que todos los vértices sean adyacentes? Por ejemplo, ¿un grafo con 5 o 6 vértices tendría que dejar algunos sin conectar?

También menciona que una Camarilla es un "Subgráfico completo máximo" pero yo pensaba que los subgráficos debían contener las mismas aristas. Entonces, ¿por qué sólo hay 3 nodos con grados superiores a 2 pero en la camarilla hay 4?

Answer 1

Parece que estás confundiendo los conceptos de camarilla , camarilla maximalista y gráfico de cliqueo . A camarilla de un gráfico $G = (V, E)$ es un conjunto $X \subseteq V$ tal que cada dos vértices en $X$ son adyacentes (conectados por una arista.) A camarilla maximalista de $G$ es una camarilla $X$ que sea lo más grande posible (es decir, añadir cualquier vértice violaría la condición de camarilla).

El gráfico de cliqueo de $G$ es un nuevo gráfico $H = (V', E')$ , definida de la siguiente manera. El conjunto de vértices $V'$ es el conjunto de camarillas máximas de $G$ . (¡Cada vértice del gráfico de la camarilla representa una camarilla completa en el gráfico original!) El conjunto de aristas $E'$ es el conjunto de pares de camarillas máximas $\{X, Y\}$ tal que $X \cap Y \neq \varnothing$ . (Dos camarillas máximas están conectadas por una arista si comparten un vértice).

El primer gráfico representado en su pregunta tiene $4$ cliques máximas distintas, cada una de las cuales es un triángulo. (Véase la imagen aquí. ) Cada dos de estas cuatro camarillas comparten al menos un vértice. Por lo tanto, el gráfico de camarillas de ese primer gráfico es $K_4$ el gráfico completo en $4$ vértices.

Answer 2

Para el grafo de camarillas, las camarillas (máximas) del grafo original son los vértices, y son adyacentes si las camarillas correspondientes comparten un vértice en el grafo original.

En tu ejemplo, las camarillas máximas del grafo original son todas de tamaño 3, por lo que las cuatro $3$ -Los ciclos del primer gráfico están representados por los cuatro vértices del gráfico de la camarilla. Dos $3$ -Los ciclos del gráfico original comparten al menos un vértice, por lo que los vértices del gráfico de la camarilla son todos adyacentes.