Revisión del 22:55 27 may 2016 editar AlfonsoERomero (discusión · contribs.) 1583 ediciones mSin resumen de edición Etiqueta: Edición visual ← Ir a diferencia anterior		Revisión del 11:57 17 dic 2016 editar deshacer Technopat (discusión · contribs.) Verificadores, Reversores 378 593 ediciones ortografía; mantenimiento Ir a siguiente diferencia →
Línea 10: \| valign="top" \| [[Archivo:Complete bipartite graph K3,3.svg\|thumb\|center\|100px\|''K''<sub>3,3</sub>]] \|} En [[teoría de grafos]], un '''grafo plano''' (o '''planar''' según referencias) es un [[grafo]] que puede ser dibujado en el [[Plano (geometría)\|plano]] sin que ninguna [[Arista (Teoría de grafos)\|arista]] se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un ~~[[Plano (geometría)\|~~plano]]). Los grafos ''K''<sub>5</sub> y el ''K''<sub>3,3</sub> son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos. Todo grafo plano puede ser dibujado sobre la [[Esfera\|esfera]], y viceversa. Una generalización de los grafos planos son grafos dibujados e incrustados sobre superficies de [[Género (matemáticas)\|~~genero~~género]] arbitrario. En esta terminología, los grafos planos tienen ~~genero~~género 0, por ser el plano y la esfera de género 0. == Teorema de Kuratowski == Línea 26: == Otros criterios para determinar si un grafo es plano == En la práctica, es difícil usar el teorema de Kuratowski para decidir rápidamente si un grafo es plano. Sin embargo, existe un algoritmo rápido para este problema: dado un grafo de ''n'' vértices y ''a'' el número de aristas, es posible determinar en tiempo '''O(n)''' (lineal) si el grafo es plano o no, utilizando los dos teoremas siguientes: {{teorema\|1=Si G es un grafo plano con ''n'' ≥ 3 vértices, entonces ''a'' ≤ 3''n'' - 6\|título=Teorema 1}} Línea 52 ⟶ 53: {{teorema\|1=Si un grafo simple plano conexo tiene ''v'' vértices, ''a'' aristas y ''c'' caras, entonces <br>''v'' − ''a'' + ''c'' = 2}} Por ejemplo, la [[~~Característica~~característica de Euler]] es 2. De manera más ilustrativa, en los ejemplos anteriores, en el primer grafo plano tenemos: ''v''=6, ''a''=7 y ''c''=3. Si el segundo grafo se redibuja sin las intersecciones de aristas, tenemos ''v''=4, ''a''=6 y ''c''=4. La fórmula de Euler se puede probar de la siguiente manera: si el grafo no es un [[Teoría de grafos#Árboles\|árbol]], entonces se elimina una arista que completa un [[Teoría de grafos#Ciclos y caminos hamiltonianos\|ciclo]]. Esto disminuye el valor de ''a'' y ''c'' en uno, dejando ''v'' − ''a'' + ''c'' constante. Repítase hasta llegar a un árbol. Los árboles tienen ''v'' = ''a'' + 1 y ''c'' = 1, verificando la fórmula ''v'' - ''a'' + ''c'' = 2. En un grafo [[Grafo\|simple]], [[Teoría de grafos#Grafos Conexos\|conexo]] y plano, cualquier región (posiblemente exceptuando la exterior) está conectada por al menos tres aristas y cada arista toca como mucho dos regiones. Usando la fórmula de Euler, se puede demostrar que estos grafos son ''escasos'' en el sentido que ''a'' ≤ 3''v'' - 6 si ''v'' ≥ 3. Línea 100 ⟶ 101: [[Categoría:Grafos planares\| ]] ~~<!--[[zh:平面圖]]-->~~

Diferencia entre revisiones de «Grafo plano»