¿Cómo puedo visualizar la identidad $m \leq3n -6$ (donde $m$ es el número de bordes, $n$ el número de vértices) para simples gráficos planares finitos conectados?
Respuestas
¿Demasiados anuncios?
zyx
Puntos
20965
Utilizaré el más fácil de comprender $E$ y $V$ en lugar de $m$ y $n$ . Quieres mostrar $I = 3V - E \geq 6$ . Llame a $I$ el "invariante" del gráfico. La desigualdad en $I$ es un análogo discreto del teorema de Gauss-Bonnet en geometría diferencial.
$2I$ es la suma de $(6 - \deg v)$ sobre todos los vértices. El límite inferior de $I$ significa que el grado medio debe ser inferior a $6$ en un gráfico plano (finito). Mejor: la curvatura local media debe ser positiva para que un gráfico se dibuje en una esfera.
Se necesitan algunas condiciones en el gráfico para que esta interpretación se mantenga. El gráfico debe ser superior a un determinado tamaño o la desigualdad es falsa. Si está vacía, $E=V=0$ y la afirmación es falsa. Si un árbol, $V = E+1$ y se necesita $E \geq 2$ . Estos casos son degenerados en el sentido de que el resultado se refiere a la incrustación en superficies, y si el esqueleto 1 del grafo es contractible el problema no es de naturaleza topológica. Un ciclo de longitud $2$ o más satisface la desigualdad por lo que se supone que hay un ciclo no trivial. Es necesario un grafo simple sin bucles, de lo contrario se puede sostener $V$ constante y añadir un número ilimitado de aristas. Dentro de los grafos simples no contratables el caso mínimo es un triángulo y la desigualdad se mantiene en ese caso. Para ver $6 - \deg v$ como medida combinatoria de la curvatura local de una superficie, los ciclos mínimos en el gráfico deberían ser todos triángulos, y como veremos, esto se refleja como holgura en la desigualdad sobre $I$ si algunas de las caras no son triangulares.
$I$ se reduce añadiendo aristas entre vértices no conectados (cada adición de una arista reduce $I$ por $1$ ). Así, para un conjunto fijo de vértices $V$ el caso crítico será cuando cada cara sea un triángulo, es decir, una triangulación. Si la triangulación es de una superficie compacta, el número de caras $F$ satisface $2E = 3F$ y la invariante es $I = 3V - 3E + 3F$ , que es 3x la característica de Euler de la superficie. Concluimos que $I = 3(2-2g) = 6 - 4g$ donde $g$ es el género de la superficie, lo que explica el número $6$ y la suposición de planaridad, $g=0$ .
Así que: una interpretación visual de $I$ es, dibujar la gráfica en una superficie de género $g $ , añadiendo algún número $k$ de aristas si es necesario para obtener una triangulación; entonces $I = 6 - 4g + k$ . Si el gráfico es plano, entonces $g=0$ es alcanzable, con $I = 6+k$ y $I = 6$ si y sólo si existe un dibujo con todas las caras triangulares. La desigualdad es cierta para grafos simples planares con $3$ o más vértices, y la igualdad se mantiene precisamente para las triangulaciones de un triángulo, como se propone en otra respuesta.
Finalmente, si para cada cara se define su exceso como $(e - 3)$ el número de aristas por las que es mayor que un triángulo, entonces $I = 6 - 4g + \text{total excess of the graph}$ . Esta cantidad se calcula para cualquier dibujo particular del gráfico, pero $I$ es, por definición, expresable puramente en términos del número de vértices y aristas, por lo que el exceso total menos $4g$ es independiente del dibujo.
Andrew Bolster
Puntos
111
Digamos que tiene un gráfico con $m = 3n - 6$ . Entonces, añade un vértice más. Esta relación dice que puedes añadir como máximo 3 aristas para mantener el gráfico plano.
Si quieres más, trabaja en esto tú mismo. Dibuja 3 vértices. Dibuja tantas aristas como puedas para que el gráfico sea plano. La desigualdad dice $m \leq 3 \cdot 3 - 6 = 3$ . Por supuesto, se puede llegar a 3 dibujando todos los bordes y formando un $K_3$ .
Ahora, añade un vértice más. Dibuja todas las aristas que puedas, pero mantén el gráfico plano. Sólo hay 3 posibles aristas adicionales y en realidad puedes dibujar las 3 ya que un $K_4$ también es planar.
Ahora, añade un vértice más. Dibuja todas las aristas que puedas y mantén el gráfico plano. La desigualdad dice que puedes dibujar como máximo 3. En este caso, hay 4 aristas posibles, así que no podrás dibujarlas todas.
Repite el proceso (continuando y/o empezando de nuevo) hasta que tenga un poco más de sentido.
user25293
Puntos
16
Empieza visualizando tres vértices, con tres aristas: un triángulo.
Si añadimos un vértice fuera del triángulo, tenemos puede sólo podrá dibujar dos aristas más (posiblemente tres), pero si en su lugar añadimos el vértice dentro de el triángulo, vamos a ciertamente ser capaz de añadir tres aristas.
Para añadir el máximo número de aristas posible, siempre que añadamos un vértice, debemos colocarlo dentro de uno de los triángulos existentes. Esto da lugar a tres aristas adicionales por cada vértice adicional. Por tanto, la relación entre aristas y vértices (en el caso óptimo) es de 3:1, lo que nos da (aproximadamente) $m \leq 3n$ . Considerando nuestro caso base (n=3, m=3), podemos ver que de hecho $m \leq 3n - 6$ .
