Comprobar si un grafo es planar

Question

Tengo que comprobar si un grafo es planar. El tipo es

$$ e ≤ 3v − 6 .$$

De La Wikipedia:

Tenga en cuenta que estos teoremas proporcionar las condiciones necesarias para la planaridad que no son condiciones suficientes, y por lo tanto sólo puede ser utilizado para probar un grafo no es plano, no se que es plana. Si ambos teorema 1 y 2 fallan, se pueden emplear otros métodos.

Me pregunto ¿qué debo hacer para demostrar que un grafo es planar.

Answer 1

Estás buscando el siguiente resultado?

Teorema: En la conexión de un simple plano gráfico con $v$ vértices y $e$ bordes, si $v \geq 3$,$e \leq 3v-6$.

Normalmente, esto se demostró a través de Euler Característico de la Fórmula (por ejemplo, aquí [pdf advertencia]); I una vez que se establece como una tarea cuestión.

Este teorema puede ser utilizado para mostrar, por ejemplo, que $K_5$ es no-planar (ya que no satisface $e \leq 3v-6$). Pero, como Alon Amit comentado, el bound $e \leq 3v-6$ también puede ser satisfecho por los no-grafos planares, tales como $K_{3,3}$ (donde más sofisticados argumentos deben utilizarse en su lugar).

El más sencillo (humanos) manera de demostrar que un grafo es planar es dibujar en el plano (sin cruzar los bordes). Kuratowski y de Wagner teoremas son importantes los resultados que dan las condiciones necesarias y suficientes para la planaridad.

Si usted está después de un software determinado, no creo que me podría explicar mejor que en el StackExchange post Shahab mencionado (aquí).

Answer 2

En realidad un plano gráfico debe ser un dispersas gráfico que, en el caso de $K_{3,3}$ significa que contiene $9$ bordes y $6$ vértices que muestra que $K_{3,3}$ no es escasa. Por euler verificación de $K_{3,3}$ no contiene $3$ de la longitud de los ciclos o triángulos, lo que significa que $e\leq 2v-6$ no está satisfecho.

Answer 3

Una adición a Douglas S. Stones post, quien mencionó $K_{3,3}$. Este grafo es bipartito y la de menor longitud de ciclo en este gráfico es $4$.

Para $K_5$ $K_{3,3}$ los siguientes criterios, que se menciona en el artículo de Wikipedia sobre grafos planares, puede ser utilizado. (Esos son precisamente los resultados que se refieren como el Teorema 1 y el Teorema 2 en tu post.)

Para un plano gráfico tener $v$ vértices y $e$ bordes, el siguiente se tiene:

• Si $v \ge 3$$e \le 3v - 6$;
• Si $v \ge 3$ y no hay ciclos de longitud $3$,$e \le 2v - 4$.

(La primera puede ser utilizado para demostrar que la $K_5$ no es plana, la segunda puede ser utilizado para $K_{3,3}$.)

La idea de la prueba es similar. Y se basa en la fórmula de Euler $$v-e+f=2,$$ que es equivalente a $f=2-v+e$.

Límite de cada cara se compone de al menos $3$ bordes. Ya que cada arista pertenece a los límites de las dos caras, si se suman las longitudes de los límites de todos los rostros, se obtiene, precisamente,$2e$. Así que podemos ver que
$2e\ge 3f$
$2e\ge 6-3v+3e$
$3v-6\ge e$.

Si, por otra parte, sabemos que el ciclo más corto como en menos de longitud $4$, obtenemos que cada límite debe tener al menos $4$ bordes. Por lo tanto
$2e\ge 4f$
$2e\ge 8-4v+4e$
$e\ge 4-2v+2e$
$2v-4\ge e$.

Answer 4

Para demostrar que un grafo es planar tenemos que dibujar en un plano y si se puede dibujar con la condición de que no hay dos bordes se intersectan entre sí que podemos decir que el grafo es planar. Tan simple como eso.