4 votos

La comprensión de la prueba: Un árbol de expansión en $G$ implica un árbol de expansión en el grafo dual

El teorema estoy leyendo es como sigue:

Supongamos $G$ está conectado a un plano gráfico. Deje $T$ ser el conjunto de aristas en $G$ que forman un árbol de expansión y deje $T^*$ ser el conjunto de todos los bordes que son duales de los bordes no en $T$. Entonces los bordes de $T^*$ forma de un árbol de expansión de $G^*$.

La prueba de que quiero entender (de este libro) continúa mostrando que $T^*$ es acíclico y luego se conecta. Lo que tengo duda es en que $T^*$ está conectado. El argumento (que ha cambiado un poco desde el libro) es la siguiente:

Nos muestran que $T^*$ está conectado. Para probar que esto deje $T^*=T_1\sqcup T_2$. Deje $U$ ser la unión de las regiones en $G$ con capital en $T^*$. $U$ no es todo el plano (sin punto de $T_2$ pertenece a ella). Por lo tanto el límite de $B$ $U$ es no-vacío. Ahora $B$ se compone de ciertos bordes de $T$, teniendo una región de $U$ en un lado y una región que no se en $U$ en el otro lado. Por lo tanto, no hay ningún vértice de grado $1$ sobre el límite, que es un contradicción porque eso significaría que el límite de los rendimientos de un ciclo en el $T$. Por lo $T^*$ es un árbol de expansión.

No entiendo qué es $U$ y porqué $B$ será la forma en que describe. ¿Qué hace el autor decir, por el capital?

1voto

Jon Mark Perry Puntos 4480

La prueba es bastante simple pero muy mal puesto. Primero presuponemos $T^*$ está desconectado. El autor indica que esta por $T^*=T_1\sqcup T_2$, pero probablemente debería estar mejor escrito como $T^*=\bigsqcup_i T_i$.

La siguiente línea es muy mal redactada, creo que el autor se refiere a que $U$ es la unión de las regiones de $G$ que contienen un determinado $T_i$. Esto se deduce de la siguiente línea, que establece que $U$ no contiene regiones que 'tienen el capital' en algunos otros $T_j$.

El resto de los argumento de los estados que $U$ no es todo el plano, y por lo tanto tiene un límite interior, o una frontera exterior, o posiblemente ambos.

Y debido a este límite se divide $U$ $U'$ debe ser un ciclo, lo cual es una contradicción con la premisa de que el original $T$ es un árbol.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X