¿Qué valores puede alcanzar$v-e+f$ si$G$ es un gráfico plano (no conectado)?

Question

Deje $G=(V,E)$ ser un plano gráfico y seleccione representación planar.

Si $G$ está conectado, entonces, de acuerdo a la fórmula de Euler, tenemos $$v − e + f = 2,$$ were $v$ is the number of vertices, $e$ the number of edges and $f$ el número de regiones delimitadas por bordes, incluyendo el exterior, infinitamente grande de la región.

Me preguntaba qué valores de $v-e+f$ puede asumir si $G$ es plana, pero no conectado. Después de algún dibujo, creo que esto puede ser cualquier número entero mayor que 1, pero no puedo demostrarlo.

Hay alguien que me pueda ayudar?

Answer 1

tenga en cuenta que una de las caras de un gráfico plano es la región sin límites "fuera" del gráfico. esto es común a los componentes conectados por separado, por lo que puede resumir los componentes y obtener:

$$ v-e + f = 1 + C $$ donde$C$ es la cantidad de componentes conectados.

Answer 2

Creo $v-e+f\geq 2$. Dado un plano gráfico de $G$ $v$ vértices, $e$ bordes y $f$ caras y $c$ componentes, podemos construir un nuevo gráfico de $G'$ mediante la adición de un nuevo vértice $x$ y añadiendo $c$ bordes, que $x$ está conectado a un vértice arbitrario en el "exterior" de cada componente.

$G'$ es plana y tiene el mismo número de caras como $G$ ($G'$ puede ser dibujado a verse como una estrella con los componentes de la $G$ tomando el lugar de la final de los vértices con $x$ el centro). (*)

Por otra parte, $G'$ está conectado por lo $(v+1)-(e+c)+f=2$. Por lo tanto $(v-e+f=1+c \geq 2)$.

P. S. yo no estoy del todo seguro de la demanda (*) todavía. Puede ser que necesite para pensar bien las cosas y si es posible dar una razón mejor si es cierto.

Answer 3

Puede aplicar la fórmula de Euler a cada componente conectado. ¡Cuidado con la cara exterior!

Tu encuentras: $\sum_i v_i - e_i + f_i = 2c$. Y$\sum_i v_i = v, \sum_i e_i = e, \sum_i f_i = c + \sum_i (f_i - 1) = c + f - 1$.

Por lo tanto,$v - e + c + f - 1 = 2c$, que da$v - e + f = c + 1$.

Answer 4

Si logramos "construir" un gráfico no conectado con$v-e+f=1$, entonces terminamos.

Deje$G_1$ ser un gráfico de planificador, por lo tanto$v-e+f=2$, ahora agregamos a este gráfico un gráfico$G_2$ que tiene solo dos vértices,$v_1,v_2$ (que no son los vértices de$G_1$, por supuesto) y un borde, que los conectó y solo a ellos. Así que la característica de Euler ($v-e+f$) de$G_1\cup G_2$ es$1$.

Ahora puede duplicar ese$G$$\ \ n$ veces, para obtener$v-e+f=n$.