43 votos

¿Por qué son grafos planares tan excepcional?

En comparación a las clases de gráficos embebidos en otras superficies.

Algunas de las maneras en que son excepcionales:

  1. Mac Lane y Whitney criterios algebraicos son las caracterizaciones de los grafos planares. (Bien, sobre todo algebraicas en el caso anterior.) Antes de escribir esta pregunta, yo no sabía si generalizaciones, gráficos incrustados en otras superficies existido, pero algunos afortunados Google-fu subido algunas referencias -- en particular, no parece ser una generalización de Whitney criterio debido a Jack Edmonds general de las superficies, aunque frustrante no puedo encontrar el papel, y la principal referencia que encontré implica que puede haber un pequeño problema en la botella de Klein. Alguien sabe si Edmonds' resultado es tan fácil de demostrar como Whitney?

  2. Kuratowski clásico de la caracterización de los grafos planares por prohibido que los menores de edad. Por supuesto, esto no generalizar a otras superficies, pero este resultado es tanto increíblemente profundo y difícil (en oposición a la prueba de Kuratowski, que no es en absoluto trivial, pero se puede obtener por una suficientemente dedicado licenciatura-en realidad, mi trabajo es como un ejercicio que es en gran parte lo que ha motivado la pregunta) y, en cierto sentido, "esencialmente " combinatoria" en el que se aplica a una categoría más amplia de familias que no son inherentemente topológicamente definido.

  3. En la otra dirección de la dificultad, de la cuatro-color teorema. Es, aparentemente, no es difícil demostrar (excepto para el avión) que lo que resulta ser el estrecho límite superior en el cromática número de un gráfico integrado en una superficie (otros que, por el motivo que sea, la botella de Klein) es, de hecho, un límite superior, el problema es que muestra opresión! Mientras que es bastante trivial demostrar que $K_4$ es planar (para ser justos, sin embargo, el ajuste es fácil de comprobar para superficies de pequeña género -- el problema en el caso general), pero los cuatro-color teorema requiere cantidades inhumanas de cálculo y muy diferentes, esencialmente ad-hoc métodos.

Me doy cuenta de que la esfera tiene género 0, lo que la hace única, y ha trivial grupo fundamental, que lo mismo, pero aunque me imagino que esta información es relativa a la excepcionalidad de que el avión/esfera, no es realmente tan satisfactorio como una respuesta. Así que, ¿por qué es que los métodos que funcionan en todas partes tienden a fallar en la esfera?

Preguntas relacionadas: razones-para-la-importancia-de-planaridad y colorabilidad

10voto

Doug Puntos 858

Como Gil Kalai notas del Teorema de Steinitz (Un grafo G es el vértice de borde de la gráfica de una convexo 3-dimensional poliedro, si y sólo si G es planar y 3-conectado) es muy potente. Esto significa que las propiedades combinatorias (circuitos hamiltonianos, elecciones, etc.) de algo 3-dimensional puede ser estudiado por mirar a un tipo especial de gráfico en 2-dimensiones. Nada completamente como esto ocurre para dimensiones superiores convexas polytopes. Del mismo modo, no sabemos cómo estudiar todos "toroidal polytopes" el uso de una clase especial de gráficos en el toro.

Lo que parece interesante es la interfaz entre la captura de "geométrica" de propiedades de los objetos de combinatoria (teoría de grafos) propiedades. Por ejemplo, durante algún tiempo he estado interesado en que en 3 dimensiones poliedros convexos, con todas sus caras en las que se triángulos se pueden realizar con los triángulos isósceles como caras. Una forma de atacar este es mirar el plano 3-conectado gráficos gráficos con al menos 4 vértices cuyas caras son triángulos (máxima grafos planares). Resulta que uno puede colorear los bordes de una gráfica con dos colores a y b de modo que cada cara tiene dos una borde y una b de borde. Ahora uno puede hacer la pregunta de si estos colorantes se pueden realizar con congruentes los triángulos isósceles, los colores a y b se utilizan para codificar las dos longitudes de los bordes de la congruencia de los triángulos isósceles. No es difícil mostrar que algunos máxima grafos planares no puede ser realizado con congruentes los triángulos isósceles pero diciendo exactamente lo que los gráficos pueden ser tan di cuenta de que parece mucho más difícil. También, la teoría de grafos hecho posible para mí para ver muchas maneras de darse cuenta de tales poliedros geométricamente, cuando tal realización es posible - en otras palabras de la misma combinatoria tipo a menudo puede ser realizado con congruentes los triángulos isósceles de muchas maneras) otra de las formas que tenía un montón de simetría. Si 4 divide el número de caras de un máximo de plano gráfico puede el color de sus bordes con dos colores a y b para que el número de a, a, b, triángulos y b, b, a los triángulos son iguales. Sin embargo, no he sido capaz de decirle explícitamente cuando estos colorantes se traducen en geométricas realizaciones. A grandes rasgos, la combinatoria preguntas parecer "fácil", mientras que el geométrica queridos parecen "duro". No sé si la máxima de grafos planares con al menos 4 vértices puede ser realizado por poliedros convexos con triángulos isósceles. (Supongo que sí). También hay preguntas interesantes cuando se permite que las mezclas de los triángulos isósceles y triángulos equiláteros. (Se sabe que hay exactamente 8 poliedros convexos con sólo triángulos equiláteros para los rostros.) Uno de los puntos de fricción de estas preguntas está tratando de decir cuando dos triángulos que comparten un borde en el gráfico se aplanan y se encuentran en un plano en la realización en el espacio de 3 dimensiones.

Mi punto es que aunque Steinitz del Teorema permitido el progreso en muchas preguntas y me animó a formular nuevas geométricas preguntas que no se me ocurrió otra cosa.

Mejor,

Joe Malkevitch

4voto

Zach Burlingame Puntos 7232

Otro (menos conocidas) de la caracterización de los grafos planares es Schnyder del teorema, que caracteriza a los grafos planares de acuerdo a orden de dimensión. Es decir, un grafo es planar si y sólo si su incidencia poset ha pedido dimensión en la mayoría de los 3.

También, sería negligente de mi parte no mencionar el hermoso (fuerte) Hanani-Tutte teorema:

Un grafo es planar si y sólo si tiene un dibujo en el plano de tal manera que cada dos bordes adyacentes de la cruza de una incluso el número de veces.

2voto

Pierre Spring Puntos 2398

(Creo que la pregunta de por qué grafos planares son excepcionales es importante. Se puede pedir no sólo en el contexto de los gráficos embebidos en otras superficies. Me dejó editar y elaborados, también el endeudamiento de las observaciones.)

Dualidad: tal vez la dualidad es la propiedad crucial de grafos planares. Hay un teorema afirma que el dual de un gráfico matroid M es un gráfico matroid si y sólo si M es el matroid de un plano gráfico. En este caso, el doble de M es la matroid del grafo dual de G. (Ver este artículo de la wikipedia). Esto significa que los circuitos de un plano gráfico están en correspondencia uno a uno con los recortes del grafo dual.

Una importante manifestación de la singularidad de los grafos planares (que creo que está relacionado con la dualidad) es Kasteleyn la fórmula para el número de perfecto elecciones y la conexión con el conteo de los árboles.

Robusto descripciones geométricas: Otra diferencia conceptual es que (3-conectado o máxima) grafos planares son los gráficos de estructuras en 3 dimensiones de polytopes y así tener más propiedades geométricas que las gráficas de las superficies de no compartir.

La definición geométrica de los grafos planares (a diferencia de varias generalizaciones) es muy robusto. Un grafo es planar si se puede dibujar en el plano de tal manera que los bordes no se cruzan en su interior y están representados por Jordania curvas; La clase de los grafos planares es también lo que tenemos, si reemplazamos "Jordania curvas" por "línea de intervalos," o si reemplazamos "no cruce" por "número de cruces". El Koebe-Andreev-Thurston teorema permite representar cada plano gráfico por la "tocar el gráfico" de que no se superpongan los círculos. Ambos (relativa) de las representaciones a través de convexo polytopes y por el círculo de envases, pueden respetar el grupo de automorfismos de la gráfica y su doble.

Inductivas construcciones. Otra característica excepcional de la clase de los grafos planares es que los grafos planares puede ser construido por construcciones inductivas. (En este sentido son similares a los de la clase de los árboles, aunque el inductivo construcciones no son tan simples como para que los árboles). Esto no funciona para la mayoría de las generalizaciones de los grafos planares.

Una relacionada con la propiedad importante de los grafos planares, mapas, y las triangulaciones (con etiquetas de los vértices) es que pueden ser enumerados muy bien. Este es Tutte teoría. (Tiene profundas de las extensiones de las superficies.)

Es a menudo el caso de que los resultados sobre grafos planares extender a otras clases. Como ya he mencionado, Tutte teoría se extiende a las triangulaciones de otras superficies. Otro ejemplo es el fundamental Lipton-Tarjan separador teorema, que se extiende a todos los gráficos con una prohibido menor de edad.

El estudio de los grafos planares han llevado a importantes gráfica de conceptos teóricos Otra razón (de diferente naturaleza) ¿por qué grafos planares son excepcionales es que varios importantes de la teoría de grafos conceptos fueron disvovered mirando grafos planares (o grafos planares.) La noción de vértice para colorear de los gráficos de vino (al mejor de mi conocimiento) de los cuatro colores conjetura acerca de grafos planares. Del mismo modo, Hamilton caminos y ciclos fueron estudiados por primera vez por grafos planares.


Los gráficos en las superficies y otras nociones generalización de la planaridad. Teniendo en cuenta la clase de todos los gráficos que puede ser incrustado en una superficie dada es una natural y una importante ampliación de la planaridad. Pero, de hecho, por varias preguntas, gráficos embebidos en las superficies puede no ser la generalización de los grafos planares.

David Eppstein mencionó otra generalización a través del colin de Verdier invariante. Esto describe un hiearachy de gráficos donde la siguiente clase después de grafos planares son "linklessly embebido de gráficos". Esos son los gráficos que pueden ser embebidos en el espacio sin tener a dos disjuntos cyles geométricamente enlace. Como resultó esta también es una noción robusta y conduce a una hermosa clase de gráficos. (Todos ellos tienen en la mayoría de 4v-10 bordes, donde v es el número de vértices; El conocido caso de Hadwiger de la conjetura para los gráficos no tener K_6 menor implica que todos ellos son 5 engañosa.) Además de las clases en esta jerarquía son todavía muy misterioso. Otras extensiones de planaridad: 3) (no literalmente) los Gráficos no tener K_r como un menor de edad; 4;5) (Ambos muy problemática) Como Joe se mencionó, los gráficos de d-polytopes, y también los gráficos obtenidos a partir de la esfera de envases en dimensiones superiores; 6) (no gráficos) r-dimensional simplicial complejos que no pueden ser incrustados en el doble de la dimensión, 7) [Una idea que me promovido a través de los años:] los gráficos (y skeleta) de d-polytope a la desaparición de segundo (tóricas) g-número, y muchos más.

Prohibido a los menores de edad y colorear. Como para los elementos segundo y tercero en la pregunta. Acerca de la coloración no estoy seguro de si se deben considerar 4-colorear grafos planares y coloración de grafos en otras superficies como muy relacionados con los fenómenos. En relación prohibida a menores de edad. El teorema de Kuratowski en la superficie es un caso especial (y también un paso importante de la prueba) de una forma mucho más general resultado (Wagner conjetura demostrado por Robertson y Seymour) acerca de cualquier menor de edad-cerrado clase de gráficos. Este resultado puede ser considerado como extender el teorema de Kuratowski y también (y quizás más importante) la ampliación de Kruskal y Nash-Williams teorema de los árboles. De hecho Kuratoski del teorema se relaciona muy bien con el panorama más general de topológico de la obstrucción embeddibility. Si usted quisiera proponer una diferente (tal vez topológico) la comprensión de la extensión de Kuratowski del teorema de superficies, entonces tal vez debería empezar por el bien cuasi pedido teorema de los árboles.

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