Diferentes maneras de simplificar la estructura de un gráfico

Question

Deje $G = (V,E)$ ser un grafo finito gráfico simple sin bucles.

Definición Vamos a llamar a un subconjunto $U\subset V$ autónoma si cada vértice de $V\ \setminus U$ es adiacent a cada vértice de $U$ o no adiacent a cualquiera de ellos.

Esta noción se utiliza en J. Körner, G. Simonyi, Zs. Tuza, Perfecto para parejas de gráficos, Combinatorica, 12 (2) (1992), 179-192 para derivar una ecuación que la gráfica de la entropía debe satisfacer. Esta ecuación relaciona la entropía de $G$ con la entropía de los más pequeños gráfica obtenida por el colapso de $U$ a un vértice, conectado con cada uno de los vértices que estaba conectado a cada vértice de $U$.

Me sorprendió mucho en el chat que una construcción similar se utiliza en la teoría de autómatas para simplificar ciertas máquinas de estado finito.

Hay otras construcciones que se emplean generalmente para vincular una determinada función en una gráfica con la misma función que calcula en un pequeño pero relacionados con la gráfica?

[Mi motivación es la conjetura su equivalente gráfico de la entropía y tratan de probar.]

Answer 1

Tenemos la noción de división de descomposición, que se define como sigue.

Deje $S$ ser un subconjunto de los vértices, y vamos a definir $N(S)=\{t\in V\ \setminus S : \exists\ s\in S, (t,s)\in E\}$ como el conjunto de vecinos de $S$.

Deje $\{V_1, V_2\}$ ser una partición del conjunto de vértices tales que $|V_1|\ge 2$, $|V_2|\ge 2$. También vamos a definir $V_{1}' = N(V_2)$, $V_{2}' = N(V_1)$.

Definición. $\{V_1, V_2\}$ es una división de la gráfica de $G$ si $\forall v\in V_{1}'$, $\forall w \in V_{2}'$ tenemos $(v,w)\in E$. Si $G$ no tiene ningún tipo de división decimos que $G$ es el primer para la división de descomposición.

Si $\{V_1, V_2\}$ es un partido para $G$ le podría agregar un nuevo nodo $m$ para el conjunto de vértices, conectado con exactamente los nodos en $V_{1}'\cup V_{2}'$, llamado marcador.

Definición Si $\{V_1, V_2\}$ es un partido para $G$ con marcador de $m$ llamamos división de descomposición de $G$ en el conjunto del primer gráficos obtenidos de forma recursiva por encontrar un split para los gráficos, cuyo vértice conjuntos de $V_1\cup m$$V_2\cup m$.

El cómputo de la división de descomposición es polinomial en el tamaño de la gráfica, como se muestra en el T. H. Ma, J. Spinrad, Dividir la Descomposición del Grafo Gráficos, Actas de la primera edición de los ACM-SIAM simposio sobre Discreto algoritmos(1990), 252-260.

Answer 2

Tenemos los siguientes conocido lema acerca de los colorantes.

Deje $G$ ser un gráfico, y $v$, $w$ no adyacentes vértices. Vamos a definir el gráfico de $G^{+}$, donde hemos añadido a $G$ el borde de la $(v,w)$. También vamos a definir $G^{-}$, la gráfica se identifican $v$ $w$ en un nuevo vértice adyacente a cada vértice que era adyacente a al menos uno de ellos.

Lema. $\chi(G)=\min\{\chi(G^{+}),\chi(G^{-})\}$

Para probar esto, podemos notar que hay un bijection entre los colorantes de $G$ donde $v$ $w$ tienen diferentes colores y colorantes de $G^{+}$. También hay un bijection entre los colorantes de $G$ donde $v$ $w$ tienen el mismo color y el color de $G^{-}$.