Artículos

14: Gráficos planos


14: Gráficos planos

Matemáticas discretas: una introducción abierta, tercera edición

Cuando se puede dibujar un gráfico conectado sin que se crucen los bordes, se llama. Cuando un gráfico plano se dibuja de esta manera, divide el plano en regiones llamadas.

Dibuja, si es posible, dos gráficos planos diferentes con el mismo número de vértices, aristas y caras.

Dibuja, si es posible, dos gráficos planos diferentes con el mismo número de vértices y aristas, pero con un número diferente de caras.

¿Cuándo es posible dibujar un gráfico para que ninguno de los bordes se cruce? Si esto es posible, decimos que el gráfico es (ya que puede dibujarlo en el avión).

Tenga en cuenta que la definición de plano incluye la frase "es posible". Esto significa que incluso si un gráfico no parece plano, aún podría serlo. Quizás pueda volver a dibujarlo de manera que no se crucen los bordes. Por ejemplo, este es un gráfico plano:

Eso es porque podemos volver a dibujarlo así:

Los gráficos son los mismos, por lo que si uno es plano, el otro también debe serlo. Sin embargo, el dibujo original del gráfico no era uno de los gráficos.

Cuando se dibuja un gráfico plano sin que los bordes se crucen, los bordes y los vértices del gráfico dividen el plano en regiones. Llamaremos a cada región a. El gráfico de arriba tiene 3 caras (sí, nosotros hacer incluir la región "exterior" como una cara). El número de caras no cambia independientemente de cómo dibuje el gráfico (siempre que lo haga sin que los bordes se crucen), por lo que tiene sentido atribuir el número de caras como una propiedad del gráfico plano.

ADVERTENCIA: solo puede contar caras cuando el gráfico se dibuja en forma plana. Por ejemplo, considere estas dos representaciones del mismo gráfico:

Si intentas contar caras usando el gráfico de la izquierda, podrías decir que hay 5 caras (incluida la exterior). Pero dibujar el gráfico con una representación plana muestra que, de hecho, solo hay 4 caras.

Existe una conexión entre el número de vértices ( (v )), el número de aristas ( (e )) y el número de caras ( (f )) en cualquier gráfico plano conectado. Esta relación se llama fórmula de Euler.

Fórmula de Euler para gráficas planas.

Para cualquier grafo plano conectado con (v ) vértices, (e ) aristas y (f ) caras, tenemos

¿Por qué es verdadera la fórmula de Euler? Una forma de convencerse de su validez es dibujar un gráfico plano paso a paso. Comience con el gráfico (P_2 text <:> )

Cualquier gráfico conectado (además de un solo vértice aislado) debe contener este subgrafo. Ahora construya su gráfico agregando bordes y vértices. Cada paso consistirá en agregar un nuevo vértice conectado por un nuevo borde a parte de su gráfico (creando así un nuevo "pico") o conectando dos vértices que ya están en el gráfico con un nuevo borde (completando un circuito).

¿Qué hacen estos "movimientos"? Al agregar el pico, el número de aristas aumenta en 1, el número de vértices aumenta en uno y el número de caras permanece igual. Pero esto significa que (v - e + f ) no cambia. Completar un circuito agrega un borde, agrega una cara y mantiene el mismo número de vértices. Entonces, nuevamente, (v - e + f ) no cambia.

Dado que podemos construir cualquier gráfico usando una combinación de estos dos movimientos, y hacerlo nunca cambia la cantidad (v - e + f text <,> ) esa cantidad será la misma para todos los gráficos. Pero observe que nuestro gráfico inicial (P_2 ) tiene (v = 2 text <,> ) (e = 1 ) y (f = 1 text <,> ) entonces (v - e + f = 2 text <.> ) Este argumento es esencialmente una prueba por inducción. Un buen ejercicio sería reescribirlo como una prueba de inducción formal.

Subsección Gráficos no planos

¡Investigar!

Para las gráficas completas (K_n text <,> ) nos gustaría poder decir algo sobre el número de vértices, aristas y (si la gráfica es plana) caras. Consideremos primero (K_3 text <:> )

¿Cuántos vértices tiene (K_3 )? Cuantos bordes?

Si (K_3 ) es plano, ¿cuántas caras debería tener?

Repita las partes (1) y (2) para (K_4 text <,> ) (K_5 text <,> ) y (K_ <23> text <.> )

¿Qué pasa con los gráficos bipartitos completos? ¿Cuántos vértices, aristas y caras (si fuera plano) tiene (K_ <7,4> )? ¿Para qué valores de (m ) y (n ) son (K_n ) y (K_) planar?

No todos los gráficos son planos. Si hay demasiados bordes y muy pocos vértices, algunos de los bordes deberán cruzarse. El gráfico más pequeño donde sucede esto es (K_5 text <.> )

Si intenta volver a dibujar esto sin que los bordes se crucen, rápidamente se mete en problemas. Parece que hay una ventaja de más. De hecho, podemos demostrar que no importa cómo lo dibuje, (K_5 ) siempre tendrá bordes cruzados.

Teorema 4.3.1.
Prueba .

La prueba es por contradiccion. Entonces asuma que (K_5 ) es plano. Entonces la gráfica debe satisfacer la fórmula de Euler para gráficas planas. (K_5 ) tiene 5 vértices y 10 aristas, por lo que obtenemos

lo que dice que si la gráfica se dibuja sin que ningún borde se cruce, habrá (f = 7 ) caras.

Ahora considere cuántos bordes rodean cada cara. Cada cara debe estar rodeada por al menos 3 bordes. Sea (B ) el número total de límites alrededor de todas las caras del gráfico. Entonces tenemos que (3f le B text <.> ) Pero también (B = 2e text <,> ) ya que cada borde se usa como un límite exactamente dos veces. Poniendo esto juntos obtenemos

Pero esto es imposible, ya que hemos determinado que (f = 7 ) y (e = 10 text <,> ) y (21 not le 20 text <.> ) Este es un contradicción entonces de hecho (K_5 ) no es plano.

El otro gráfico más simple que no es plano es (K_ <3,3> )

Demostrar que (K_ <3,3> ) no es plano responde al acertijo de casas y servicios públicos: no es posible conectar cada una de las tres casas a cada uno de los tres servicios públicos sin que las líneas se crucen.

Teorema 4.3.2.
Prueba .

De nuevo, procedemos por contradicción. Suponga que (K_ <3,3> ) fuera plano. Entonces, según la fórmula de Euler, habrá 5 caras, ya que (v = 6 text <,> ) (e = 9 text <,> ) y (6 - 9 + f = 2 text <.> )

¿Cuántos límites rodean estas 5 caras? Sea (B ) este número. Dado que cada borde se usa como límite dos veces, tenemos (B = 2e text <.> ) Además, (B ge 4f ) ya que cada cara está rodeada por 4 o más límites. Sabemos que esto es cierto porque (K_ <3,3> ) es bipartito, por lo que no contiene ciclos de 3 aristas. Por lo tanto

Pero esto diría que (20 le 18 text <,> ) lo cual es claramente falso. Por tanto, (K_ <3,3> ) no es plano.

Tenga en cuenta las similitudes y diferencias en estas pruebas. Ambas son pruebas por contradicción, y ambas comienzan usando la fórmula de Euler para derivar el (supuesto) número de caras en el gráfico. Luego, encontramos una relación entre el número de caras y el número de aristas en función de la cantidad de aristas que rodean cada cara. Esta es la única diferencia. En la prueba de (K_5 text <,> ) obtuvimos (3f le 2e ) y para (K_ <3,3> ) obtenemos (4f le 2e text <.> ) El coeficiente de (f ) es la clave. Es el menor número de bordes que pueden rodear cualquier rostro. Si algunos bordes rodean una cara, estos bordes forman un ciclo. Entonces ese número es el tamaño del ciclo más pequeño en el gráfico.

En general, si dejamos que (g ) sea el tamaño del ciclo más pequeño en una gráfica ( (g ) significa circunferencia, que es el término técnico para esto) entonces para cualquier gráfico plano tenemos (gf le 2e text <.> ) Cuando esto no está de acuerdo con la fórmula de Euler, sabemos con certeza que el gráfico no puede ser plano.

Subsección poliedros

¡Investigar!

Un cubo es un ejemplo de poliedro convexo. Contiene 6 cuadrados idénticos para sus caras, 8 vértices y 12 aristas. El cubo es un (también conocido como a) porque cada cara es un polígono regular idéntico y cada vértice une un número igual de caras.

Hay exactamente otros cuatro poliedros regulares: el tetraedro, el octaedro, el dodecaedro y el icosaedro con 4, 8, 12 y 20 caras respectivamente. ¿Cuántos vértices y aristas tiene cada uno de estos?

Otra área de las matemáticas en la que es posible que haya escuchado los términos "vértice", "borde" y "cara" es la geometría. A es un sólido geométrico formado por caras poligonales planas unidas en bordes y vértices. Estamos especialmente interesados ​​en los poliedros, lo que significa que cualquier segmento de línea que conecte dos puntos en el interior del poliedro debe estar completamente contenido dentro del poliedro. 7

Observe que desde (8 - 12 + 6 = 2 text <,> ) los vértices, las aristas y las caras de un cubo satisfacen la fórmula de Euler para gráficas planas. Esto no es una coincidencia. Podemos representar un cubo como un gráfico plano proyectando los vértices y las aristas en el plano. Una de esas proyecciones se ve así:

De hecho, todos El poliedro convexo se puede proyectar sobre el plano sin que los bordes se crucen. Piense en colocar el poliedro dentro de una esfera, con una luz en el centro de la esfera. Los bordes y vértices del poliedro proyectan una sombra sobre el interior de la esfera. A continuación, puede hacer un agujero en la esfera en el medio de una de las caras proyectadas y "estirar" la esfera para que quede plana en el plano. La cara perforada se convierte en la cara "exterior" del gráfico plano.

El punto es que podemos aplicar lo que sabemos sobre gráficas (en particular gráficas planas) a poliedros convexos. Dado que cada poliedro convexo se puede representar como un gráfico plano, vemos que la fórmula de Euler para gráficos planos también se aplica a todos los poliedros convexos. También podemos aplicar el mismo tipo de razonamiento que usamos para gráficos en otros contextos a poliedros convexos. Por ejemplo, sabemos que no hay un poliedro convexo con 11 vértices todos de grado 3, ya que esto daría 33/2 aristas.

Ejemplo 4.3.3.

¿Existe un poliedro convexo que consta de tres triángulos y seis pentágonos? ¿Qué hay de tres triángulos, seis pentágonos y cinco heptágonos (polígonos de 7 lados)?

¿Cuántas aristas tendrían esos poliedros? Para el primer poliedro propuesto, los triángulos contribuirían con un total de 9 aristas y los pentágonos contribuirían con 30. Sin embargo, esto cuenta cada arista dos veces (ya que cada arista limita exactamente con dos caras), dando 39/2 aristas, una imposibilidad. No existe tal poliedro.

El segundo poliedro no tiene este obstáculo. Los 35 bordes adicionales aportados por los heptágonos dan un total de 74/2 = 37 bordes. Hasta ahora tan bueno. Ahora, ¿cuántos vértices tiene este supuesto poliedro? Podemos usar la fórmula de Euler. Hay 14 caras, entonces tenemos (v - 37 + 14 = 2 ) o equivalentemente (v = 25 text <.> ) Pero ahora usa los vértices para contar las aristas nuevamente. Cada vértice debe tener grado al menos tres (es decir, cada vértice une al menos tres caras ya que el ángulo interior de todos los polígonos debe ser menor que (180 ^ circ )), por lo que la suma de los grados de los vértices es al menos 75. Dado que la suma de los grados debe ser exactamente el doble del número de aristas, esto dice que hay estrictamente más de 37 aristas. Una vez más, no existe tal poliedro.

Para concluir esta aplicación de gráficas planas, considere los poliedros regulares. Dijimos que solo hay cinco. ¿Cómo sabemos que esto es cierto? Podemos probarlo usando la teoría de grafos.

Teorema 4.3.4.

Hay exactamente cinco poliedros regulares.

Prueba .

Recuerda que todas las caras de un poliedro regular son polígonos regulares idénticos y que cada vértice tiene el mismo grado. Considere cuatro casos, según el tipo de polígono regular.

Caso 1: cada cara es un triángulo. Sea (f ) el número de caras. Entonces hay (3f / 2 ) bordes. Usando la fórmula de Euler tenemos (v - 3f / 2 + f = 2 ) entonces (v = 2 + f / 2 text <.> ) Ahora cada vértice tiene el mismo grado, digamos (k text < .> ) Entonces el número de aristas también es (kv / 2 text <.> ) Poniendo esto junto da

Tanto (k ) como (f ) deben ser números enteros positivos. Tenga en cuenta que ( frac <6f> <4 + f> ) es una función creciente para (f text <,> ) positiva limitada arriba por una asíntota horizontal en (k = 6 text <.> ) Por tanto, los únicos valores posibles para (k ) son 3, 4 y 5. Cada uno de ellos es posible. Para obtener (k = 3 text <,> ) necesitamos (f = 4 ) (este es el tetraedro). Para (k = 4 ) tomamos (f = 8 ) (el octaedro). Para (k = 5 ) tome (f = 20 ) (el icosaedro). Por lo tanto, hay exactamente tres poliedros regulares con triángulos por caras.

Caso 2: cada cara es un cuadrado. Ahora tenemos (e = 4f / 2 = 2f text <.> ) Usando la fórmula de Euler obtenemos (v = 2 + f text <,> ) y contando los bordes usando el grado (k ) de cada vértice nos da

Esta es nuevamente una función creciente, pero esta vez la asíntota horizontal está en (k = 4 text <,> ) por lo que el único valor posible que podría tomar (k ) es 3. Esto produce 6 caras, y nosotros tener un cubo. Solo hay un poliedro regular con caras cuadradas.

Caso 3: Cada cara es un pentágono. Realizamos el mismo cálculo que el anterior, esta vez obteniendo (e = 5f / 2 ) entonces (v = 2 + 3f / 2 text <.> ) Entonces

Ahora la asíntota horizontal está en ( frac <10> <3> text <.> ) Esto es menor que 4, así que solo podemos esperar hacer (k = 3 text <.> ) Podemos hazlo usando 12 pentágonos, obteniendo el dodecaedro. Este es el único poliedro regular con pentágonos como caras.

Caso 4: Cada cara es un (n ) - gon con (n ge 6 text <.> ) Siguiendo el mismo procedimiento anterior, deducimos que

que aumentará a una asíntota horizontal de ( frac <2n> text <.> ) Cuando (n = 6 text <,> ) esta asíntota está en (k = 3 text <.> ) Cualquier valor mayor de (n ) dará una asíntota. Por lo tanto, no existen poliedros regulares con caras más grandes que pentágonos. 8

Ejercicios Ejercicios

¿Es posible que un gráfico plano tenga 6 vértices, 10 aristas y 5 caras? Explicar.

No. Un gráfico plano (conectado) debe satisfacer la fórmula de Euler: (v - e + f = 2 text <.> ) Aquí (v - e + f = 6 - 10 + 5 = 1 text <.> )

La gráfica (G ) tiene 6 vértices con grados (2, 2, 3, 4, 4, 5 text <.> ) ¿Cuántas aristas tiene (G )? ¿Podría (G ) ser plano? Si es así, ¿cuántas caras tendría? Si no, explique.

(G ) tiene 10 aristas, ya que (10 ​​= frac <2 + 2 + 3 + 4 + 4 + 5> <2> text <.> ) Podría ser plano, y luego tendría 6 caras, usando la fórmula de Euler: (6-10 + f = 2 ) significa (f = 6 text <.> ) Sin embargo, para asegurarnos de que sea realmente plano, necesitaríamos dibujar una gráfica con esos vértices grados sin que los bordes se crucen. Esto se puede hacer mediante prueba y error (y es posible).

¿Es posible dibujar un gráfico conectado con 7 vértices y 10 aristas de modo que ninguna arista se cruce y cree 4 caras? Explicar.

¿Qué te diría la fórmula de Euler?

¿Es posible que un gráfico con 10 vértices y aristas sea un gráfico plano conectado? Explicar.

¿Existe una gráfica plana conectada con un número impar de caras donde cada vértice tiene grado 6? Demuestre su respuesta.

Puede usar el lema del apretón de manos para encontrar el número de aristas, en términos de (v text <,> ) el número de vértices.

Estoy pensando en un poliedro que contiene 12 caras. Siete son triángulos y cuatro son cuadralaterales. El poliedro tiene 11 vértices, incluidos los que rodean la cara misteriosa. ¿Cuántos lados tiene la última cara?

Digamos que el último poliedro tiene (n ) aristas y también (n ) vértices. El número total de aristas que tiene el poliedro es ((7 cdot 3 + 4 cdot 4 + n) / 2 = (37 + n) / 2 text <.> ) En particular, conocemos la última cara debe tener un número impar de aristas. También tenemos que (v = 11 text <.> ) Por la fórmula de Euler, tenemos (11 - (37 + n) / 2 + 12 = 2 text <,> ) y despejando (n ) obtenemos (n = 5 text <,> ) por lo que la última cara es un pentágono.

Considere algunos poliedros clásicos.

Un octaedro es un poliedro regular formado por 8 triángulos equiláteros (parece como dos pirámides con sus bases pegadas). Dibuja una representación gráfica plana de un octaedro. ¿Cuántos vértices, aristas y caras tiene un octaedro (y tu gráfica)?

El diseño tradicional de un balón de fútbol es de hecho una (proyección esférica de un) icosaedro truncado. Consiste en 12 pentágonos regulares y 20 hexágonos regulares. No hay dos pentágonos adyacentes (por lo que los bordes de cada pentágono son compartidos solo por hexágonos). ¿Cuántos vértices, aristas y caras tiene un icosaedro truncado? Explique cómo llegó a sus respuestas. Bono: dibuje la representación gráfica plana del icosaedro truncado.

Su "amigo" afirma que ha construido un poliedro convexo con 2 triángulos, 2 cuadrados, 6 pentágonos y 5 octágonos. Demuestra que tu amigo miente. Sugerencia: cada vértice de un poliedro convexo debe bordear al menos tres caras.

Demuestre la fórmula de Euler usando inducción sobre el número de aristas en la gráfica.

Prueba .

Sea (P (n) ) la declaración, “cada grafo plano conectado que contenga (n ) aristas satisface (v - n + f = 2 text <.> )” Mostraremos (P ( n) ) es cierto para todos (n ge 0 text <.> )

Caso base: solo hay un gráfico con aristas cero, es decir, un único vértice aislado. En este caso (v = 1 text <,> ) (f = 1 ) y (e = 0 text <,> ) por lo que la fórmula de Euler es válida.

Caso inductivo: suponga que (P (k) ) es verdadero para algunos (k ge 0 text <.> ) Arbitrarios. Ahora considere un gráfico arbitrario que contiene (k + 1 ) bordes (y (v ) vértices y (f ) caras). No importa cómo se vea este gráfico, podemos eliminar un solo borde para obtener un gráfico con (k ) bordes al que podemos aplicar la hipótesis inductiva.

Hay dos casos: o el gráfico contiene un ciclo o no. Si el gráfico contiene un ciclo, elija un borde que sea parte de este ciclo y elimínelo. Esto no desconectará el gráfico y disminuirá el número de caras en 1 (ya que el borde bordeaba dos caras distintas). Entonces, según la hipótesis inductiva, tendremos (v - k + f-1 = 2 text <.> ) Agregar el borde hacia atrás dará (v - (k + 1) + f = 2 ) según sea necesario.

Si la gráfica no contiene un ciclo, entonces es un árbol, por lo que tiene un vértice de grado 1. Entonces podemos elegir el borde para eliminarlo para que sea incidente a dicho vértice de grado 1. En este caso, elimine también ese vértice. La gráfica más pequeña ahora satisfará (v-1 - k + f = 2 ) por la hipótesis de inducción (eliminar el borde y el vértice no redujo el número de caras). Al agregar el borde y el vértice hacia atrás, se obtiene (v - (k + 1) + f = 2 text <,> ) según sea necesario.

Por lo tanto, según el principio de inducción matemática, la fórmula de Euler es válida para todas las gráficas planas.

Demuestre la fórmula de Euler usando inducción sobre el número de vértices en el gráfico.

La fórmula de Euler ( (v - e + f = 2 )) es válida para todos conectado gráficos planares. ¿Qué pasa si un gráfico no está conectado? Suponga que una gráfica plana tiene dos componentes. ¿Cuál es el valor de (v - e + f ) ahora? ¿Qué pasa si tiene (k ) componentes?

Demuestre que (abajo) no es plano.

¿Cuál es la duración del ciclo más corto? (Esta cantidad generalmente se llama la del gráfico).

Demuestra que cualquier grafo plano con vértices (v ) y aristas (e ) satisface (e le 3v - 6 text <.> )

Prueba .

Sabemos que en cualquier gráfico plano el número de caras (f ) satisface (3f le 2e ) ya que cada cara está delimitada por al menos tres aristas, pero cada arista limita con dos caras. Combine esto con la fórmula de Euler:


14: Gráficos planos

Un gráfico G es plano si se puede dibujar en el plano de tal manera que no se encuentren dos aristas excepto en un vértice al que inciden. Cualquier dibujo de este tipo se llama dibujo plano de G.

Por ejemplo, el gráfico K 4 es plano, ya que se puede dibujar en el plano sin que los bordes se crucen.

Los tres dibujos planos de K 4 son:

Los cinco gráficos platónicos son todos planos.

Por otro lado, el gráfico bipartito completo K 3,3 no es plana, ya que cada dibujo de K 3,3 contiene al menos un cruce. ¿Por qué? porque K 3,3 tiene un ciclo que debe aparecer en cualquier plano de dibujo.

Para estudiar gráficas planas, nos limitamos a gráficas simples.

  • Si un gráfico plano tiene múltiples aristas o bucles.
    • Contraiga los múltiples bordes en un solo borde.
    • Retire los bucles.

    Elimina bucles y bordes múltiples.

    Dibuja sin múltiples aristas.

    Inserte bucles y varios bordes.

    Si G es un gráfico plano, cualquier dibujo plano de G divide el plano en regiones, llamadas caras. Una de estas caras no tiene límites y se llama cara infinita. Si F es cualquier rostro, entonces el grado de F (denotado por grados F ) es el número de aristas que se encuentran al caminar alrededor del límite de la cara F . Si todas las caras tienen el mismo grado (g, digamos), la G es una cara regular de grado g.

    Por ejemplo, el siguiente gráfico G tiene cuatro caras, F4 siendo el rostro infinito.

    Es fácil ver en el gráfico anterior que grados f1= 3, grados f2= 4, grados f3= 9, grados f4=8.

    Tenga en cuenta que la suma de todos los grados de las caras es igual al doble del número de aristas en el gráfico, ya que cada arista bordea dos caras diferentes (como bg, cd y cf) u ocurre dos veces cuando camina alrededor de una sola cara (como ab y gh). La fórmula de Euler relaciona el número de vértices, aristas y caras de un gráfico plano. Si n, myf denotan el número de vértices, aristas y caras, respectivamente, de un grafo plano conectado, entonces obtenemos norte-metro+F = 2.

    La fórmula de Euler nos dice que todos los dibujos planos de un gráfico plano conectado tienen el mismo número de caras, a saber, 2+ m-norte.

    Teorema 1 (fórmula de Euler) Sea G un grafo plano conectado y sea norte, metro y F denotar, respectivamente, el número de vértices, aristas y caras en un dibujo plano de G. Entonces norte - m + f = 2 .

    Prueba Empleamos inducción matemática en aristas, m. La inducción es obvia para m = 0 ya que en este caso n = 1 y f = 1. Suponga que el resultado es verdadero para todas las gráficas planas conectadas con menos de m aristas, donde m es mayor o igual que 1, y suponga que G tiene m aristas. Si G es un árbol, entonces n = m + 1 yf = 1, por lo que sigue la fórmula deseada. Por otro lado, si G no es un árbol, sea e un borde de ciclo de G y considere G-e. El gráfico plano conectado G-e tiene n vértices, m-1 aristas y f-1 caras de modo que según la hipótesis inductiva,

    Podemos obtener una serie de resultados útiles utilizando la fórmula de Euler. (Un "corolario" es un teorema asociado con otro teorema del que se puede derivar fácilmente).

    Corolario 1 Sea G un grafo simple plano conectado con n vértices, donde n & # 8805 3 y m aristas. Entonces m & # 8804 3n - 6.

    Prueba Para el gráfico G con f caras, del lema del apretón de manos para el gráfico plano se deduce que 2metro ≥ 3 F (¿por qué?) porque el grado de cada cara de una gráfica simple es al menos 3), entonces f & # 8804 2/3 m.

    Combinando esto con la fórmula de Euler


    Dado que n - m + f = 2
    Obtenemos m - n + 2 & # 8804 2/3 m
    Por lo tanto m & # 8804 3n - 6.

    Como ejemplo del Corolario 1, demuestre que K 5 no es plano.

    Prueba Suponga que K 5 es un gráfico plano. Dado que K 5 tiene 5 vértices y 10 aristas, se sigue del Corolario 1 que 10 (3 5) - 6 = 9. Esta contradicción muestra que K 5 no es plano.

    Es importante señalar que K 3,3 tiene 6 vértices y 9 aristas, y es cierto que 9 & # 8804 (3 6) - 6 = 12. Este hecho simplemente muestra que no podemos usar el Corolario 1 para demostrar que K 3,3 no es plano. Esto nos lleva al siguiente corolario.

    Corolario 2 Sea G un gráfico simple plano conectado con n vértices y m aristas, y sin triángulos. Entonces m & # 8804 2n - 4 .

    Prueba Para gráfico GRAMO con F caras, se sigue del lema de apretón de manos para gráficas planas que 2metro & # 8805 4f (por qué porque el grado de cada cara de una gráfica simple sin triángulos es al menos 4), de modo que F ≤ 1/2 metro .

    Combinando esto con la fórmula de Euler


    Dado que n - m + f = 2
    Implica m -n + 2 = f
    Obtenemos m - n + 2 & # 8804 1 / 2m
    Por lo tanto m & # 8804 2n - 4

    Como ejemplo del Corolario 2, demuestre que K 3,3 no es plano.

    Prueba Suponga que K 3,3 es un gráfico plano. Dado que K 3,3 tiene 6 vértices y 9 aristas y no tiene triángulos, del Corolario 2 se sigue que 9 & # 8804 (2 6) - 4 = 8. Esta contradicción muestra que K 3,3 no es plano.

    Corolario 3 Sea G una gráfica simple plana conectada. Entonces G contiene al menos un vértice de grado 5 o menos.

    Prueba Del Corolario 1, obtenemos m & # 8804 3n-6. Suponga que cada vértice de G tiene un grado 6 o más. Entonces tenemos 2m & # 8805 6n (¿por qué? Porque 2m es la suma del grado del vértice), y por lo tanto m & # 88053n. Esta contradicción muestra que al menos un vértice tiene grado 5 o menos.

    Ahora mostraremos usando la fórmula de Euler que solo hay cinco poliedros convexos regulares, a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el isosaedro.

    Teorema 2 Solo hay 5 poliedros convexos regulares.

    Prueba Demostramos este teorema mostrando que solo hay 5 grafos planos conectados G con las siguientes propiedades.

    1. G es regular de grado d, donde d & # 88053.
    2. Cualquier dibujo plano de G tiene caras regulares de grado g donde g & # 88053.

    Sean n, myf los números de vértices, aristas y caras de tal grafo plano G. Entonces, a partir de las propiedades (i) y (ii), obtenemos

    Esto nos da n = 2 m / d y f = 2 m / g

    Aquí se cumple la fórmula de Euler (n - m + f = 2), ya que G es un gráfico plano.


    Que se puede escribir como 1 / d - 1/2 + 1 / g = 1 / m

    Dado que 1 / m & gt 0, se sigue que 1 / d + 1 / g & gt 1/2

    Tenga en cuenta que cada uno de dyg es al menos 3, por lo que cada uno de 1 / d y 1 / g es como máximo 1/3.
    Por lo tanto, 1 / d & gt 1/2 - 1/3 = 1/6 y 1 / g & gt 1/2 - 1/3 = 1/6.

    y llegamos a la conclusión de que d & lt 6 y g & lt 6.

    Esto significa que los únicos valores posibles de d y g son 3, 4 y 5. Sin embargo, si tanto d como g son mayores que 3, entonces

    lo cual es una contradicción. Esto nos deja con solo cinco casos:

    Caso 1: Cuando d = 3 y g = 3.
    obtenemos 1 / m = 1/3 - 1/2 + 1/3 = 1/6
    Por lo tanto m = 6
    De ello se deduce que n = 8 yf = 4 y esto da el tetraedro.

    Caso 2: Cuando d = 3 y g = 4.
    obtenemos 1 / m = 1/3 - 1/2 + 1/4 = 1/12
    Por lo tanto m = 12
    De ello se deduce que n = 8 yf = 6 y esto da el Cubo.

    Caso 3: Cuando d = 3 y g = 5.
    obtenemos 1 / m = 1/3 - 1/2 + 1/5 = 1/30
    Por lo tanto m = 30
    De ello se deduce que n = 20 yf = 12 y esto da el Dodecaedro.

    Caso 4: Cuando d = 4 y g = 3.
    obtenemos 1 / m = 1/4 - 1/2 + 1/3 = 1/12
    Por lo tanto m = 12
    De ello se deduce que n = 6 yf = 8 y esto da el Octaedro.

    Caso 5: Cuando d = 5 y g = 3.
    obtenemos 1 / m = 1/5 - 1/2 + 1/3 = 1/30
    Por lo tanto m = 30
    Se deduce que n = 12 yf = 20 y esto da el icosaedro.

    Y esto completa la prueba.

    Los Corolarios 1, 2 y su generalización suelen ser útiles para mostrar que el gráfico no es plano. Desafortunadamente, hay muchas gráficas que satisfacen estas desigualdades pero no son planas. Por lo tanto, necesitamos otra forma de decidir la planitud.

    Algunas observaciones importantes:

    • Observación 1
      • No todos los gráficos son planos.
      • Por ejemplo, conocemos K 5 y K 3,3 no son planas.
      • Si G es un gráfico plano, entonces cada subgráfico de G es plano
      • Por lo general, declaramos la observación 2 de la siguiente manera
      • Observación 2a
      • Si G contiene un gráfico no plano como subgráfico, entonces G no es plano. Por ejemplo, el siguiente gráfico no es plano
      • Dado que contiene K5 como subgrafo.
      • El siguiente gráfico también es no plano
      • Dado que contiene K 3,3 como un subgrafo.
      • Observación 3
        • Si G es un gráfico plano, entonces cada subdivisión de G es plana, por lo general declaramos la observación 3 de la siguiente manera.
        • Observación 3a
        • Si G es una subdivisión de un gráfico no plano, entonces G es no plano.
        • Por ejemplo, el siguiente gráfico no es plano,

        De las observaciones (2a) y (3a) se deduce que, si algún gráfico G contiene una subdivisión de K 5 y K 3,3 como subgrafo, G debe ser no plano.

        ¿Por qué estamos tan obsesionados con K? 5 y K 3,3 ? La razón es que todas las gráficas no planas se pueden obtener agregando vértices y aristas a una subdivisión de K 5 y K 3,3 .

        Cada gráfico no plano contiene K 5 o K 3,3 como un subgrafo.

        El siguiente resultado se debe al matemático polaco K. Kuratowski.

        Teorema 3 Un gráfico es plano si y solo si no contiene una subdivisión de K5 y K3,3 como un subgrafo.

        En la siguiente figura, la contradicción se realiza al traer el vértice w más y más cerca de v hasta w y v coincidir y luego fusionar varios bordes en un solo borde.

        Traer vértice w más cerca a v.

        Vértice coalescente v y vértice w.

        Finalmente, fusionamos múltiples aristas y tenemos

        Una contracción de un gráfico es el resultado de una secuencia de contracciones de bordes. Por ejemplo, K5 es una contracción del gráfico de Petersen

        Teorema 4 Un gráfico es plano si y solo si no contiene un subgráfico que tenga K5 y K3,3 como una contracción.

        La idea básica para probar la planaridad de la gráfica dada es si somos capaces de
        detectar un subgrafo que es una subdivisión de K5 o K3,3 o un subgrafo que
        contratos a K5 o K3,3 entonces una gráfica dada no es plana.

        Los teoremas 3 y 4 nos dan las condiciones necesarias y suficientes para que un gráfico sea plano en un sentido puramente teórico de gráficos (subgrafo, subdivisión, K3,3, etc.) en lugar del sentido geométrico (cruce, dibujo en el plano, etc.). Esta es la razón por la que no existe ningún algoritmo que utilice estos dos teoremas para probar la planaridad de un gráfico. Dado que esto implicaría mirar una gran cantidad de subgrafos y verificar que ninguno de ellos sea una subdivisión o contrato con K5 o K3,3.

        Dado un gráfico plano conectado G, construimos un gráfico dual G * en tres etapas.

        • Tome un dibujo de avión de G.
        • Elija un punto dentro de cada cara del plano del dibujo; estos puntos son los vértices de G *.
        • Para cada e del plano plano, dibuja una línea que conecte los vértices de G * a cada lado de e.

        Este procedimiento se ilustra como sigue:

        Tenga en cuenta que cada dibujo plano de G dio lugar a un solo gráfico dual G *.

        El siguiente teorema ilustra una relación simple entre el número de vértices, caras y aristas de un gráfico y su dual.

        Teorema 6 Si G es un gráfico plano conectado con n vértices, f caras y m aristas, entonces G * tiene f vértices, n caras y m aristas.

        En el ejemplo anterior, G tiene 5 vértices, 4 caras y 7 aristas, y G * tiene 4 caras, 5 caras y siete aristas.

        Tenga en cuenta que si G es un gráfico plano conectado, entonces G * también es un gráfico plano conectado.


        14: Gráficos planos

        1. Definiciones y gráficos perfectos

        Investigaremos algunos de los conceptos básicos de la teoría de grafos en esta sección.

        Un gráfico G es una colección, E, de pares desordenados distintos de elementos distintos de un conjunto V. Los elementos de V se llaman vértices o nodos, y TLos pares en E se llaman aristas o arcos. o el gráfico. (Si un par (w, v) puede ocurrir varias veces en E, llamamos a la estructura un multigraph. Si se permiten aristas como (v, v), que se denominan bucles, se denomina gráfico con bucles).

        Los gráficos son cosas que subyacen a muchas estructuras matemáticas y, de hecho, cualquier cosa que involucre pares de elementos, y esto incluye cualquier tipo de relación entre pares de individuos.

        A ruta en un gráfico desde el vértice v1 al vértice vk, es una secuencia de aristas tal que la primera contiene v1, y el último contiene vk, y cada par consecutivo en la secuencia tiene un vértice en común. La longitud del camino es el número de aristas en él.

        Por lo tanto, (v, w), (w, j), (j, z), (z, q) es un camino, y uno de longitud 4 de v a q.

        Se dice que una gráfica es conectado Si por cualesquiera dos vértices en V hay un camino de uno a otro.

        A subgrafo de un gráfico G que tiene un conjunto de vértices V y un conjunto de bordes E es un gráfico H que tiene un conjunto de bordes contenido en V y un conjunto de bordes contenido en E.

        Si el conjunto de aristas de H consta de todos aristas de G cuyos extremos se encuentran en G, entonces se dice que H es un subgrafo inducido de G.

        Por lo tanto, la arista (v, w) y los vértices v, wyj forman un subgrafo de la ruta descrita anteriormente. No es un subgrafo inducido, ya que el borde (w, j) es un borde de la ruta entre los vértices en este subgrafo que no es un borde del subgrafo.

        A partición de un conjunto es una colección de sus subconjuntos (llamados bloques) sin par de los cuales se superponen, de modo que la unión de todos los bloques es el conjunto completo.

        A partición de un gráfico G es una partición de sus aristas E y sus vértices V en subconjuntos <>j> y <>j> tal que Gj = [Vj,MIj] es un gráfico.

        Un partición de borde de un gráfico G es una partición de sus aristas E en subconjuntos <>j>. Podemos definir <>j> para ser el conjunto de extremos de aristas en <>j>. Entonces tenemos que [Vj,MIj] es un gráfico.

        Cualquier gráfico puede ser particionado en es máximo subgrafos conectados, que se llaman sus componentes conectados. (Esto solo es posible cuando no hay bordes que vayan entre los subgrafos, ya que de lo contrario estos bordes se perderán en la partición, no estando en ninguno de los subgrafos. Por supuesto, si queremos, podemos definir particiones de los bordes conjunto de un gráfico y deje que los conjuntos de vértices de los gráficos resultantes se superpongan).

        A ciclo en un gráfico hay un camino que comienza en el mismo vértice en el que termina. A acorde de un ciclo es una arista entre sus vértices que no forma parte del ciclo.

        Existe una notación estándar para varios tipos de gráficos que son de interés general. El gráfico Ck es un ciclo de k longitud, que consta de k vértices y k aristas que forman ciclos.

        Knorte is the symbol for a complete graph with n vertices, which is one having all (C(n,2) (which is n(n-1)/2) edges.

        A graph whose vertices can be partitioned into k subsets, such that all edges have at most one member in each subset is said to be k-partite, or k-colorable. Thus a bipartite or two colorable graph is one whose vertex set V can be split into two parts, and all edges contain one vertex from each part.

        Kn,mis the notation we use for a complete bipartite graph between vertex sets of size n and m. Thus it consists of all edges with one vertex among the m and the other among the n, and no edges within each of these two sets.

        A simple basic question is: under what circumstance is a graph bipartite, (that is, two-colorable)?

        We can give an excluded configuration condition for bipartness or two colorability.

        A graph will be two colorable if it has no odd length cycle.

        If a graph has an odd length cycle, then it cannot be two colorable.

        Suppose G has a cycle. If you start at a vertex v of color one of the cycle, if the graph were two colored then v s neighbors including its neighbor, w, on its right in the cycle would have to have the other color, w s neighbor on the right must have the first color and so on around the cycle. When you get back to where you start, v would have to have the opposite color than it had at first when the cycle has odd length, and this is a contradiction.

        We can use a similar argument to prove that any graph that has no odd length cycle is bipartite. We get a coloring instead of a contradiction by coloring neighbors oppositely to oneself.

        We can start anywhere by coloring one vertex v one color, v s neighbors the other, their neighbors the first color, their neighbors the second color, and so on until every vertex that can be reached by a path from v is colored.

        The absence of odd cycles means that each vertex reached will have the same color every time it is colored.

        In a similar vein, it is not possible to color the complete graph, Knorte, in fewer than n colors. In any coloring in fewer colors, two vertices must have the same color, but they will be in an edge, and this violates the condition on coloring that all edges contain vertices of different colors.

        The minimum number of colors needed to color the vertices of a graph G so that none of its edges have only one color is called the coloring number of G.

        A complete graph is often called a clique. The size of the largest clique that can be made up of edges and vertices of G is called the clique number of G.

        The last statement before these definitions can then be phrased as: the coloring number of a graph is at least its clique number.

        On the other hand, the coloring number of a graph G can be strictly greater than its clique number, as we have already seen for C2j+1 when j is 2 or more. Such a graph has clique number 2 (which means it contains no triangle) but coloring number 3.

        The part highlighted in red we're not doing in class.

        If the coloring number and clique number are the same for every induced subgraph of G, we call G a perfect graph.

        El complement of a graph G is the graph on the same vertex set V, whose edges are precisely those that are not in the edge set of G.

        Thus the edge set of G and of its complement include all the edges of the complete graph on V and the edges of G and its complement do not overlap at all.

        A famous result of graph theory is The Perfect Graph Theorem which reads:

        A graph is perfect if and only if its complement is perfect.

        By the way, the coloring number and clique number of the complement of G are parameters of interest by themselves.

        The complement of G has all possible edges not in G. Thus a clique in the complement of G is a set of vertices among which there are no edges of G,

        We call this an independent set of G, a set of vertices unrelated by any edge of G.

        The number of vertices in the largest possible independent set of G is called the independence number of G.

        Thus the clique number of the complement of G is the independence number of G.

        In these terms we can describe the coloring number of G as the smallest number k such that we can partition the vertices of G into k independent sets.

        Similarly, the coloring number of the complement of G is the smallest number k so that we can partition the vertices of G into k cliques.

        And the perfect graph theorem states that if for any induced subgraph H of G we can partition the vertices of H into a number of cliques given by the size of H s largest independent set, we can partition G (or any of its induced subgraphs) in into a number of independent sets given by the size of its largest clique.

        As we have already noted one way, it is impossible to partition the vertices of G into fewer of whatever. In any partition of V into cliques, since each vertex of an independent I set must end up in a clique that contains no other member of I, the total number of blocks of the partition must be at least the maximum size of any I. And the same remark holds with the words clique and independent set reversed.

        Notice that perfection and this theorem require in the premise that you can partition the vertices of any induced subgraph of G into a number of cliques given by the independence number of that subgraph. The statement of the perfect graph theorem would be false if you were to apply the condition to G alone and not to its induced subgraphs.

        We can see that by considering the graph Q, on 6 vertices, that can be described as a 5-cycle with another edge linking the sixth vertex to one vertex of the cycle.

        For this graph the independence number is 3 and it can be partitioned into three cliques. On the other hand the clique number is 2 and it cannot be partitioned into two independent sets.

        However, the induced subgraph on the five vertices that form the cycle has independence number 2 and clique number 2 and can only be partitioned into 3 cliques and 3 independent sets. Thus, neither Q nor its complement are perfect.

        Another way to state the perfect graph theorem is: If you cannot partition the vertices of G into a number of cliques given by the size of its largest independent set, then G has an induced subgraph H that cannot be partitioned into a number of independent sets given by H s clique number.

        Here is still another way to describe this theorem.

        We define a nice graph as follows:

        A graph G is nice if given any maximum size clique C whose size (or cardinality) is |C|, we can assign integers 1 to |C| to the vertices in C and can extend that assignment to all the vertices in V so that the vertices assigned the letter j form an independent set for each j.

        This is really the statement that G is nice when its clique number and coloring number are the same.

        A graph is c nice if its complement is nice, which means that its independence number and the smallest number of cliques that its vertices can be partitioned into are the same..

        A graph is very nice if both G and its complement are nice (equivalently, G is both nice and c nice.)

        In this terminology, the graph Q defined above (a 5-cycle with another vertex linked to one vertex of the cycle) is c nice, but not nice, and so not very nice.

        Notice that if G is very nice when we can assign an ordered pair (j,k) to each of its vertices such that those vertices with the same first component form an independent set and those with the same second component form a clique, and the number of first components is |C|, the size of the largest clique, and the number of second components is the size of the largest independent set.

        A minimally not nice graph is a graph that is not nice, but all its induced subgraphs are nice.

        The perfect graph theorem in these terms is the statement.

        Every minimal not very nice graph is not nice at all (neither it nor its complement is nice.)

        There is a stronger statement that has been a conjecture for about 40 years but has just recently been proven. As a matter of fact by a remarkable coincidence, there is a lecture this very afternoon by Paul Seymour, at 4:15 in 2-105 (good refreshments at 3:30 in 2-349) in which this result will be announced and described

        The statement is, the only minimally not very nice graphs are odd cycles of length 5 or more without chords, or the complements of these.

        Since you can easily prove that these graphs are not nice at all, the Perfect Graph Theorem is an immediate consequence of it, and it is (or will be) called The Strong Perfect Graph Theorem.

        And by the strong perfect graph theorem, a graph will be very nice unless it or its complement contains a chordless odd cycle.

        By the way very nice graphs, which include perfect graphs, have some occasionally useful properties. One is as follows.

        The cardinality of the vertex set of a very nice graph G is at most the product of its clique number and its independence number.

        This statement follows immediately from these two facts

        1. Each vertex can be assigned two numbers (a,b) with the first index having a number of possible entries given by the clique number of G and the second by the independence number of G, with the indices representing which clique and independent set they belong in partitions into cliques and independent sets.

        2. No two vertices can have the same assigned pair if they form an edge of G they cannot be in the same independent set, and if the do not form an edge, they cannot be in the same clique.

        The same idea used in this last result can be applied to an arbitrary set of N distinct points in the plane, each described by coordinates (a,b).

        We can ask, what can we say about the size (|I|or |D|) of the largest monotone increasing or decreasing subset of these N points?

        We can define a graph whose edges are the pairs such that the line between them has non-negative slope.

        A monotone increasing set will be a clique in this graph, and a decreasing one will be an independent set.

        We can conclude that N is at most |I||D|.

        To get this result (using the strong perfect graph theorem) we need only show that the graph here defined can contain no chordless odd cycle. (The same result will hold by symmetry for its complement.)

        Notice that two consecutive edges whose coordinates both increase or both decrease on the two length path they form will form two sides of a triangle. This means a chordless cycle must zig zag here, which is impossible if it has odd length of 5 or more: there must be two consecutive zigs or zags and therefore a chord.

        By the way, a common application of this statement is:

        A permutation of N integers contains either an increasing or decreasing sub permutation of length at least N 1/2 .

        14.3 Planarity of Graphs

        A graph so far is an abstract thing, a creation of your mind. It consists of a set of vertices and of edges.

        We define the degree of a vertex to be the number of edges that contain it as an endpoint.

        We can, given a graph, attempt to draw it on a piece of paper, representing its vertices by points and its edges by either straight lines, or nice curves.

        We then define a graph G to be planar, if it can be so drawn without any of the curves or lines representing its edges crossing one another or meeting any other vertex on its way from one vertex to the other.

        The first obvious question is: is there a convenient way to characterize planar graphs?

        Before discussing and proving it we make some remarks, which we will prove

        1. There are two fairly small graphs that are not planar, K5 and K3,3.

        2. We can add vertices in the middle of any of the edges of these two graphs as we like and that will not help to make them planar. (Adding a vertex in the middle of an edge here means replacing an edge (a,b) by two new edges (a,c) and (c,b))

        3. We can split a vertex apart in the following way, and that also will not help to make a graph planar. Take a vertex v that lies in edges a,b c ..z replace it by 2 vertices, v1 and v2, so that each edge containing v contains one of these, and there is an additional edge containing v1 and v2. Doing so will not make a non-planar graph planar.

        4. Every graph which contains either K5 or K3,3 or something obtained from these by adding vertices in the middle edges or splitting vertices as noted in any way to them cannot be planar.

        And the characterization is:

        A graph is planar if it does not contain a subgraph obtainable by adding vertices to or splitting vertices in K5 or K3,3 any number of times. This result is called Kuratowski s Theorem.

        We will now prove all these statements.

        The first follows from this remark

        If we take two drawing of either K5 (or more generally K2j+1) or K3,3 (more generally K2k+1,2j+1) in the plane (with no edge passing through any vertex not one of its endpoints), the number of crossings between edges whose vertex sets are disjoint has the same value mod 2 in each drawing (we count a point of tangency between two edges as either 2 or 0 crossings).

        It follows immediately from this statement that if we can find a drawing of either K5 or K3, 3 with an odd number of crossings, it cannot be drawn with no crossings.

        So let us prove the statement.

        We start with two drawings of the same graph, with vertex sets the same for each. We will take each edge of the first one at a time and move it slowly and continuously until it reaches the position of the same edge in the second drawing.

        When we are done the two drawings will have the same number of crossings between edges with disjoint endpoints, since they will become identical.

        To prove the result we notice that the number of such crossings of the moved edge with any other edge having different endpoints can never change, mod 2.

        How could it change? If the edge m being moved does not either become tangent to another edge q or cross over one of the endpoints of q, the number of crossings between m and q will not change in any way. The crossings if any will merely slide along q.

        When m and q become tangent and then cross, or become tangent and uncross, the number of crossings between m and q will change by 2 which is not at all mod 2.

        When m crosses over an endpoint, v, of q then the number of crossing between m and q will change by 1. v has even degree in K2j+1 and odd degree in K2j+1,2k+1.

        When m crosses over v, the number of crossings of m with every edge containing v as an endpoint will change by 1, either up or down.

        In the case of K2j+1, two of these crossings will involve edges which share endpoints with the two ends of m. The number of crossings not including these will therefore change by an even number when m passes over v, which is 0 mod 2.

        In the case of K2j+1,2k+1, when m crosses over v, exactly one of the edges coming out of v will share an endpoint with m, so that again the number of crossings between edges which don t share endpoints will change by 0 mod 2 upon m crossing over v.

        We conclude that the number of crossings in either case mod 2 can never change as the first drawing turns into the second one. So they must have been the same to begin with, which is what we set out to prove.

        We prove the third remark by noticing that if a graph has a split vertex v and is planar we can deform its drawing so as to make the edge between v1 and v2 shorter and shorter, until it entirely disappears, without introducing any crossing of edges. In the process we undo the vertex splitting

        The second and fourth remarks do not require proof, so we turn to the proof of Kuratowski s Theorem, which says that the absence of these two configurations or their subdivisions and vertex splittings as subgraphs, which as we have seen ruin planarity, is enough to ensure planarity.

        Suppose G is a graph that has no subgraph that is obtainable from K5 or K3,3 by adding or splitting vertices. And suppose G is the smallest such graph that perhaps cannot be drawn in the plane without edge crossings.

        Our proof uses the following outline.

        We first find a cycle C in G such that there are edges or vertices which cannot be linked by a path that does not pass through at least one vertex of C.

        If there is no such cycle then we can show that C is planar without much difficulty.

        The rest of the graph can then be divided into several bridges. A bridge is a set of edges or vertices and edges that that can be linked by paths of G not meeting C.

        The simplest kind of bridge is a chord of the cycle.

        We know by induction that the graph obtained from G by omitting any one bridge is planar, since G is a minimum graph whose planarity is in doubt.

        We next define a bridge graph. Its vertices are the bridges, and there is an edge containing any pair of bridges that cannot both be drawn inside the cycle without a crossing.

        For example, if the vertices of the cycle are, in order around the cycle , 1, 2 , 3, , then (1,4) and (2,5) are examples of chordal bridges which cannot both be drawn on the same side of the cycle without a crossing. These then form an edge of the bridge graph.

        If the bridge graph is bipartite, we can draw one part of it inside the cycle without crossings and the other outside it without crossings, and G is then planar.

        Thus, we will only get non-planarity if the bridge graph is not bipartite. But that means it has an odd cycle.

        We can then show that any odd cycle in the bridge graph requires a configuration in G that is obtained by vertex splitting or edge subdivision from K5 or by edge subdivision of K3,3.

        Suppose for example the bridge graph contains a triangle each bridge of which is a chord. The ends of the chords will then form a K3,3.

        The only way that you will remember how to find a K5 or a K3,3 here is if you find them yourself. Hence:

        Exercise:1. Draw pictures for three cycles in the bridge graph with more complicated bridges that do not contain paths as illustrated, and for five and seven cycles of chords that show how to unsplit vertices (squeeze together vertices linked by an edge) to produce a K5.

        2. Draw K5 and K3,3 in the plane with one crossing in each, thus completing the proof that they are not planar.


        14: Planar Graphs

        Prerequisite – Graph Theory Basics
        Consider an electronic circuit having several nodes with connections between them. Is it possible to print that circuit on a single board such that none of the connections cross each other i.e. they do not overlap or intersect?
        This question can be answered if we know about planarity of graphs.

        Planarity – “A graph is said to be planar if it can be drawn on a plane without any edges crossing. Such a drawing is called a planar representation of the graph.”

        • Example – Is the hypercube planar?
        • Solution – Yes, is planar. Its planar representation-

        Regions in Planar Graphs –

        The planar representation of a graph splits the plane into regions. These regions are bounded by the edges except for one region that is unbounded. For example, consider the following graph ”

        There are a total of 6 regions with 5 bounded regions and 1 unbounded region .
        All the planar representations of a graph split the plane in the same number of regions. Euler found out the number of regions in a planar graph as a function of the number of vertices and number of edges in the graph.

        • Example – What is the number of regions in a connected planar simple graph with 20 vertices each with a degree of 3?
        • Solution – Sum of degrees of edges = 20 * 3 = 60. By handshaking theorem, which gives .
          By Euler’s theorem, the number of regions = which gives 12 regions.

        An important result obtained by Euler’s formula is the following inequality –

        • Example – Is the graph planar?
        • Solution – Number of vertices and edges in is 5 and 10 respectively. Since 10 > 3*5 – 6, 10 > 9 the inequality is not satisfied. Thus the graph is not planar.

        Graph Coloring –

        If you ever decide to create a map and need to color the parts of it optimally, feel lucky because graph theory is by your side. What is the maximum number of colors required to color the regions of a map? This question along with other similar ones have generated a lot of results in graph theory.
        First, let us define the constraint of coloring in a formal way-

        Coloring – “A coloring of a simple graph is the assignment of a color to each vertex of the graph such that no two adjacent vertices are assigned the same color.”

        A simple solution to this problem is to color every vertex with a different color to get a total of colors. But in some cases, the actual number of colors required could be less than this.

        chromatic number –“The least number of colors required to color a graph is called its chromatic number. It is denoted by .”

        For planar graphs the finding the chromatic number is the same problem as finding the minimum number of colors required to color a planar graph.

        • Example 1 – What is the chromatic number of the following graphs?
        • Solution – In graph , the chromatic number is atleast three since the vertices , , and are connected to each other.
          The following color assignment satisfies the coloring constraint –
          – Red
          – Green
          – Blue
          – Red
          – Green
          – Blue
          – Red
          Therefore the chromatic number of is 3.
          In graph since y are also connected, therefore the chromatic number if 4.

        GATE CS Corner Questions

        Practicing the following questions will help you test your knowledge. All questions have been asked in GATE in previous years or in GATE Mock Tests. It is highly recommended that you practice them.

        Este artículo es una contribución de Chirag Manwani. Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando contrib.geeksforgeeks.org o enviar tu artículo por correo a [email protected] Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

        Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema discutido anteriormente.

        ¡Atención lector! Don & rsquot deje de aprender ahora. Practice GATE exam well before the actual exam with the subject-wise and overall quizzes available in GATE Test Series Course.


        No such simple graph can exist, the smallest 5-regular planar graph is the icosahedron and it has diameter 3 (the distance between the green and yellow vertex is 3). I proved that there are actually only two simple planar 5-regular graphs with diameter less than 4 in my paper in Ars Combinatoria (Volume CVI, July, 2012). See my webpage about extremal regular planar graphs for other examples of different degrees and diameters.

        We have $5n=2m$ since it is 5-regular and every face must be of size 3 or more if there are no multiple edges, so $2mgeq 3f$. Putting these together with Euler's formula we get $ frac<2m> <3>geq f = 2 + m - n = 2 + m - frac<2m> <5>$ Simplifying we see that $m geq 30$ and so $ngeq 12$.

        If you are allowing loops (not just multiple edges) then the best possible is 10 vertices, achieved by adding loops to the vertices of valency 3 in this graph:

        Any graph with more vertices would lead (upon removal of multiple edges or loops) to a simple planar graph of maximum degree at most 5 with diameter 2 but the largest such graph is proven by Yang, Yuansheng, Lin, Jianhua, Dai, Yongjie (J. Comput. Appl. Math. 144 (2002) 349-358) to have 10 vertices, such as the example above.

        Let's go through and decipher what each of these statements mean.

        Planar: embeddable in the plane without self-intersections. By Kuratowski and Wagner, this is equivalent to a graph not having $K_5$ or $K_<3,3>$ as a minor.

        5-regular: every node has exactly 5 edges.

        Diameter 2: the maximum length of path between any two nodes is 2 (note that it must be achieved- ie there must be two vertices at least two edges apart).

        Let's go through and attack this naively. If we need the maximum length of path between any two nodes to be 2, then we need at least 3 nodes. Can we do it with 3 nodes? No, because then we would have 15 as the total degree of the graph, which contradicts the handshaking lemma.

        Ok, let's try 4. Since every vertex has to be 2 away from each other vertex, this means we'll need to start with a square. Now, each vertex needs 3 other edges, and we have to add them in a way which keeps the graph planar: connect 3 edges from the top left to the bottom left, and 3 edges from the top right to the bottom right. So this gives us a planar, 5-regular graph of diameter 2.

        But now we should check that such a graph cannot be made with more than four nodes. This is a little more interesting than simply finding an example. By the same logic as used to rule out the three-vertex graph, we can rule out all graphs with an odd number of vertices. This means we're left with graphs with an even number of vertices which is at least 6. But in order for such a graph to have diameter 2, it must contain $K_<3,3>$ as a subgraph, and therefore it cannot be planar. Turns out this is false, examples exist as seen in comment.

        Thus, there is an example of 4 nodes in a planar, 5-regular, diameter 2 graph.


        14: Planar Graphs

        Corollary: In any graph, there are an even number of vertices of odd degree.

        4. Simple Graph :

          Some examples of simple graph
        • Complete graph with n vertices : K n (there is an edge between every pair of vertices.
        • Bipartite graph : The set of vertices consists of two disjoint sets V 1 and V 2 and all the edges are of the form (v 1 , v 2 ) with v 1 in V 1 and v 2 in V 2 .
        • Completer bipartite graph of m, n , K m,n

        5. Isomorphisms of Graphs

        Graphs G 1 and G 2 are isomorphic if there is a one-to-one, onto function f from the vertices of G 1 to the vertices of G 2 and a one-to-one , onto function g from the edges of G 1 to the edges of G 2 , so that an edge e is incident on v and w in G 1 if and only if the edge g(e) is incident on f(v) and f(w) in G 2 . The pair of functions f and g is called an isomorphism of G 1 onto G 2 .

        Theorem : Graphs G 1 and G 2 are isomorphic if and only if for some ordering of their vertices, their adjacency matrices are equal.

        Corollary : For simple graphs G 1 and G 2 , they are isomorphic if and only if there is a one-to-one, onto function f from the vertex set of G 1 to the vertex set of G 2 satisfying the following: Vertices v and w are adjacent in G 1 if and only if the vertices f(v) and f(w) are adjacent in G 2 .

        6. Planar Graph

        A graph is planar if it can be drawn in the plane without its edges crossing.

        Euler's Formula for Planar Graph
        for any planar graph G, we have :
        f = e - v + 2 where f = number of faces (contiguous region) ,
        e = number of edges and v = number of vertices .

        In any simple, connected, planar graph G , we always have e 3v - 6

        K 5 and K 3,3 are not planar.

        Kuratowski's Theorem : A graph G is planar if and only if G does not contain a subgraph homeomorphic to K 5 or K 3,3 .

        7. Dijkstra's Shortest-Path Algorithm

        Input : A connected weighted graph with positive weighted, vertice a and z
        Output : L(z) , the length of a shortest path from a to z .

        For input consisting of n-vertex, simple, connected, weighted graph,
        Dijkstra's Algorithm has worst-case run time Q (n 2 ) .

        A cycle (path) in a graph G that includes all of the edges (as a consequence, also includes all the vertices) is called an Euler cycle (path).

        The necessary and sufficient condition for a graph G to have a Euler cycle is

        The necessary and sufficient condition for a graph G to have a Euler path is

        A cycle in a graph G that contains each vertex in G exactly once, except for the starting and ending vertex that appears twice.

        A path in a graph G that contains each vertex in G exactly once is called a Hamiltonian path.

        There is no well-known necessary and sufficient condition for the exitence of a hamitonian cycle in a given graph G.

        Given a weighted graph G, find a minimum-length Hamiltonain cycle for G.

        8. Graph Traversal

          Follow a path until it ends, or until a cycle. Use a stack .

        Let G = (V, E) is a graph which is represented by an adjacency matrix Adj. Assume that nodes in a graph record visited/unvisited information.

          Visit nodes layer-by-layer. Use a queue .

        9. Graph Search

        • Two search methods corresponding to the two traversal schemes above: Depth-First Search (DFS) and Breadth-First Search (BFS).
        • Terminate search/traversal as soon as the item is found.

        10. Minimum Spanning Trees (MST)

        • A minimum spanning tree T of an undirected graph G is a subgraph of G that connects all the vertices in G at the lowest total cost .
        • Maintains ONE TREE throughout the algorithm, and make it grow by adding edge by edge.
        • The idea is to select the next edge
          • which is adjacent from any vertex/node in the tree built so far and
          • which has the lowest weight among alternatives (i.e., all edges connected from any vertex/node in the tree built so far).

          Let G = (V, E) which is represented by an adjacency list Adj . Some support data structures:

          • d is an array of size |V|. Each d[i] contains the shortest distance for vertex i
          • Q is a priority queue of UNKNOWN vertices.
          • p is an array of size |V|. Each P[i] contains the parent of vertex i.
          • s is the source vertex.

          Example (NOTE: v0 is the source vertex, and d[i] for each vertex i is also indicated in its circle):

          • The main idea is to
            • start with a set (called forest ) of singleton trees, and
            • merge two trees at a time, unless it creates a cycle in the merged tree, until the forest becomes one tree.

            Let G = (V, E) which is represented by an adjacency list Adj . Some support data structures:

            • F is the forest -- a set of all (partial) trees.
            • MST is the minimum spanning tree, represented by a set of edges .
            • Q is a priority queue of edges.

            NOTE: In the figure below, a number in a vertex indicates the vertex number (NOT any kind of value).


            Outer 1-Planar Graphs

            A graph is outer 1-planar (o1p) if it can be drawn in the plane such that all vertices are in the outer face and each edge is crossed at most once. o1p graphs generalize outerplanar graphs, which can be recognized in linear time, and specialize 1-planar graphs, whose recognition is () -hard. We explore o1p graphs. Our first main result is a linear-time algorithm that takes a graph as input and returns a positive or a negative witness for o1p. If a graph (G) is o1p, then the algorithm computes an embedding and can augment (G) to a maximal o1p graph. Otherwise, (G) includes one of six minors, which is detected by the recognition algorithm. Secondly, we establish structural properties of o1p graphs. o1p graphs are planar and are subgraphs of planar graphs with a Hamiltonian cycle. They are neither closed under edge contraction nor under subdivision. Several important graph parameters, such as treewidth, colorability, stack number, and queue number, increase by one from outerplanar to o1p graphs. Every o1p graph of size (n) has at most (frac<5> <2>n - 4) edges and there are maximal o1p graphs with (frac<11> <5>n - frac<18><5>) edges, and these bounds are tight. Finally, every o1p graph has a straight-line grid drawing in (fancyscript(n^2)) area with all vertices in the outer face, a planar visibility representation in (fancyscript(n log n)) area, and a 3D straight-line drawing in linear volume, and these drawings can be constructed in linear time.

            Esta es una vista previa del contenido de la suscripción, acceso a través de su institución.


            This is too long for a comment. So excuse me providing an answer.

            Your question is unclear to me. Whether a graph is planar is a function of the graph itself, not how it is drawn. "In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints." from http://en.wikipedia.org/wiki/Planar_graph).

            Do you need to work out/check if the graph is planar?

            Do you need to draw it in planar form?

            In the example you provide, why is the second drawing somehow more correct than the first drawing? Is it only because their are no intersecting edges?

            Assuming you need to do this with other graphs, what rule is used to determine whether some representation is better than some other, how does your diagram generalise to other graphs?

            ¿Por qué estás haciendo esto? What is the point? If its homework, what exactly is the problem statement? If its real-life, maybe an explanation of what you are really trying to do would help.

            rt/gdhandbook/chapters/straightline.pdf describes some algorithms to do this. Or simply Google "algorithm planar representation of graph". All of these algorithms are far more complicated than I would expect for a high school assignment. Isn't there some other project you can pick instead? &ndash Peter Webb Jan 4 '14 at 2:54

            There is an Eulers Theorem that applies to every planar graph.

            Definiton: A Planar Graph is a graph that can be drawn on the plane so that the edges do not cross each other. Any planar graph partitions the plane into a number of disjoint regions called the faces of the graph.

            Euler's Theorem: V-E+F=2 where:

            1. – V is the number of vertices,
            2. – E is the number of edges,
            3. – F is the number of faces

            However, I can not provide a solution in java since its not clear the way you want to implement that. For instance, if you want to transform a graph into planar graph visually, you might need a canvas and elements rearrangement, which will be kind of complicated to implement. In general think algorithmic wise, creating the solution first in pseudocode.

            For example, since we have Euler's theorem that applies to every planar graph, you need to find a way to apply this theorem to your existing non planar graph and then test it.


            Ver el vídeo: El plano gráfico (Noviembre 2021).