¿Qué es la función SSCG?
Estoy tratando de entender el SSCG ($k$) , pero no entiendo algunas cosas ... Entiendo la idea de grafo menor, pero no entiendo el significado de$k$ (¿Qué es la longitud de una gráfica?).
Pero no entiendo qué te dan estas funciones como resultado (sé que es un conjunto de gráficos, pero no entiendo qué es común a esos gráficos)
Trato de averiguar cuáles son los $SSCG(0)=2$ y $SSCG(1)=5$.
Si alguien aquí me puede decir qué son (esos conjuntos de gráficos), creo que será mucho más claro para mí, y me explicará en un lenguaje simple la idea de la$SSCG$ función (con algunos ejemplos de los gráficos que se incluyen en k = 1 o k = 2, por ejemplo ...).
¡Gracias!
PD: estoy hablando del $SSCG$ y no el $SCG$ :)
Respuestas
La función $SSCG(k)$ no da un conjunto de gráficos, es una función que toma un número natural $k$y devuelve un número natural $SSCG(k)$ (ahora explicamos cómo).
Se dice que un gráfico es un gráfico subcúbico simple si es un gráfico simple en el que cada vértice tiene un grado como máximo $3$. Para explicar$SSCG$, presentamos nuestra propia nueva definición. Dejar$S = (G_1, G_2, \dots, G_n)$ser una secuencia de gráficos. La longitud de la secuencia es el número de gráficos que contiene. Llamamos a la secuencia$k$-Válido si satisface las siguientes cosas:
- Cada grafico $G_i$ es un gráfico subcúbico simple,
- La gráfica $G_i$ tiene como máximo $i+k$ vértices $(|V(G_i)|\leq i+k)$,
- Cada gráfico $G_i$ no tiene ningún gráfico que venga antes que él como menor (así que si $i<j$, luego $G_i$ no es menor de $G_j$).
Según una versión del teorema de Robertson-Seymour , hay un límite superior finito en la longitud de un$k$-secuencia válida. Entonces definimos$SSCG(k)$ ser la longitud máxima entre todos $k$-secuencias válidas. Tenga en cuenta que, por el motivo que sea, el gráfico vacío$\emptyset$ sin vértices se cuenta como un gráfico.
Para entender lo que está pasando aquí, calculemos $SSCG(0)$ y $SSCG(1)$ explícitamente.
Encontrar $SSCG(0)$, basta con encontrar todo $0$-secuencias válidas. El primer gráfico$G_1$ de un $0$-la secuencia válida tiene como máximo $1+0 = 1$vértices. Desde$G_1$ es simple, debe ser el gráfico vacío o $K_1$. El gráfico vacío es menor de todos los gráficos, por lo que ningún gráfico puede seguirlo en una secuencia válida. Entonces la secuencia con$G_1=\emptyset$ tiene longitud $1$. Pero que si$G_1=K_1$? Tenga en cuenta que$K_1$ es un menor de cada gráfico que tiene al menos un vértice, por lo que el único gráfico que puede venir después $K_1$ en una secuencia válida es el gráfico vacío, y obtenemos la secuencia $(G_1, G_2) = (K_1, \emptyset)$ con longitud $2$. Esto agota todas las posibilidades, por lo que vemos que la longitud máxima de un$0$-la secuencia válida es $2$, entonces $SSCG(0) = 2$.
Ahora intentemos $SSCG(1)$. Por el requisito 2 para un$1$-secuencia válida, sabemos que el primer gráfico $G_1$ de cualquier $1$-la secuencia válida tiene como máximo $1+1 = 2$vértices. Entonces nuestras únicas posibilidades son$\emptyset, K_1, K_2$ y $I_2$ (donde dejamos $I_k$ ser el gráfico con $k$vértices y sin aristas). Por el argumento anterior, conocemos cualquier secuencia que comience con$\emptyset$ o $K_1$ tiene longitud como máximo $2$. Así que consideremos una secuencia que comience con$G_1 = I_2$. Desde$I_2$ es menor de cualquier gráfico con $2$ o más vértices, debemos tener $|V(G_2)| < 2$, entonces $G_2 = K_1$ o $G_2 = \emptyset$ y vemos que cualquier secuencia que comience con $I_2$, como $(I_2, K_1, \emptyset)$ tiene longitud como máximo $3$. Finalmente, considere el$1$-secuencias válidas que comienzan con $G_1 = K_2$. La gráfica$K_2$ es menor de cualquier gráfico que tenga al menos un borde, por lo que $G_2$ no puede tener ningún borde (ni puede $G_i$ para cualquier otro $i>1$). Lo sabemos$G_2$ debe tener como máximo $2+1 = 3$ vértices, entonces $G_2 \in \{K_1, I_2, I_3\}$. Ya hemos demostrado que si nuestra secuencia tiene$I_2$, solo podemos conseguir otro $2$ gráficos en él$K_1$ y $\emptyset$), así que intentamos $G_2 = I_3$. Porque$I_3$ es menor de cada gráfico con al menos $3$ vértices, tenemos eso $G_3$ tiene como máximo $2$vértices y sin aristas. Lo mejor que podemos hacer es establecer$G_3 = I_2$. Usando los argumentos anteriores, esto nos da una secuencia$(K_2, I_3, I_2, K_1, \emptyset)$ de longitud $5$y no podemos hacerlo mejor. Entonces$SSCG(1) = 5$.
Encontré esta página mucho más útil que la página de wikipedia para entender esto.