Download 1.- GRAFO PLANO En teoría de grafos, un grafo plano (o planar

1.- GRAFO PLANO
En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en
el plano sin que ninguna arista se interseque (una definición más formal puede ser que este grafo pueda ser
"embebido" en un plano). Un grafo no es plano si no puede ser dibujado sobre un plano sin que sus aristas se
intersequen. Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el
resto de los grafos no planos.
TEOREMA DE KURATOWSKI
El matemático polaco Kazimierz Kuratowski encontró una caracterización de los grafos planos,
conocida como el teorema de Kuratowski:
Un grafo es plano si y solo si no contiene un subgrafo que es una subdivisión elemental de K5 (el grafo
completo de 5 vértices) o K3,3 (el grafo bipartito completo de 6 vértices).
Una subdivisión elemental de un grafo resulta de insertar vértices en las aristas (por ejemplo, cambiando •—
—• por •—•—•). Una formulación equivalente a este teorema es: Un grafo es plano sí y solo sí no contiene
ningún subgrafo homeomorfo a K5 ó K3,3.
OTRO CRITERIO 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 e 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 n ≥ 3 entonces e ≤ 3n - 6
Teorema 2. Si n > 3 y no existen ciclos de longitud 3, entonces e ≤ 2n - 4
El grafo K3,3, por ejemplo, tiene 6 vértices, 9 aristas y ningún ciclo de longitud 3. Por el teorema 2, no
puede ser plano. Nótese que estos teoremas están construidos con una implicación unidireccional (si), y no
bicondicional (si y solo si) y por tanto, solamente pueden ser usados para probar que el grafo no es plano,
pero no que sea plano. Si ambos teoremas fallan, deben usarse otros métodos.
FÓRMULA DE EULER
La fórmula de Euler enuncia que si un grafo conexo, plano es dibujado sobre un plano sin intersección
de aristas, y siendo v el número de vértices, e el de aristas y f la cantidad de caras (regiones conectadas por
aristas, incluyendo la región externa e infinita), entonces: v − e + f = 2, Por ejemplo, la Característica de Euler
es 2. De manera más ilustrativa, en los ejemplos anteriores, en el primer grafo plano tenemos: v=6, e=7 y f=3.
Si el segundo grafo se redibuja sin las intersecciones de aristas, tenemos v=4, e=6 y f=4. La fórmula de Euler se
puede probar de la siguiente manera: si el grafo no es un árbol, entonces se elimina una arista que completa
un ciclo. Esto disminuye el valor de e y f en uno, dejando v − e + f constante. Repítase hasta llegar a un árbol.
Los árboles tienen v = e + 1 y f = 1, verificando la fórmula v - e + f = 2.
En un grafo simple, 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 e ≤ 3v - 6 si v ≥ 3.
Se le dice plano maximal al grafo que es plano pero al agregarle cualquier arista dejase de serlo. Todas las
regiones (incluso la externa) están conectadas por tres aristas, explicando la definición alternativa de
triangular para este tipo de grafos. Si un grafo triangular tiene v vértices con v > 2, entonces tiene
exactamente 3v - 6 aristas y 2v - 4 regiones.
Nótese que la fórmula de Euler también es válida para poliedros simples. No es una casualidad: cada poliedro
simple se puede ver como un grafo plano y conexo usando los vértices del poliedro como vértices del grafo, y
las aristas del poliedro como aristas del grafo. Las caras o regiones del grafo plano resultante corresponden a
las caras del poliedro. Por ejemplo, el segundo grafo plano del ejemplo corresponde a un tetraedro.
Alternativamente, no todos los grafos planos y simples corresponden a un poliedro (los árboles, por ejemplo).
Un teorema de Ernst Steinitz dice que los grafos planos formados a partir de poliedros convexos son
precisamente los grafos planos simples y triangulares.
2.- QUE ES UN ÁRBOL
En teoría de grafos, un árbol es un grafo en el que cualesquiera dos vértices están conectados por
exactamente un camino. Un bosque es una unión disjunta de árboles. Un árbol a veces recibe el nombre de
árbol libre.
Un árbol es un grafo simple unidireccional G que satisface alguna de las siguientes condiciones equivalentes:
 G es conexo y no tiene ciclos simples.
 G no tiene ciclos simples y, si se añade alguna arista se forma un ciclo simple.
 G es conexo y si se le quita alguna arista deja de ser conexo.
 G es conexo y el grafo completo de 3 vértices K3 no es un menor de G.
 Dos vértices cualesquiera de G están conectados por un único camino simple.
Si G tiene muchos vértices, n, entonces las definiciones anteriores son también equivalentes a cualquiera de
las siguientes condiciones:
 G es conexo y tiene n − 1 aristas.
 G no tiene aristas simples y tiene n − 1 aristas.
 La cantidad de hojas de un árbol siempre es mayor o igual a la mitad de la totalidad de los nodos.
En grafo unidireccional simple G recibe el nombre de bosque si no tiene ciclos simples.
Un árbol dirigido es un grafo dirigido que sería un árbol si no se consideraran las direcciones de las aristas.
Algunos autores restringen la frase al caso en el que todas las aristas se dirigen a un vértice particular, o todas
sus direcciones parten de un vértice particular.
Un árbol recibe el nombre de árbol con raíz si cada vértice ha sido designado raíz, en cuyo caso las
aristas tienen una orientación natural hacia o desde la raíz. Los árboles con raíz, a menudo con estructuras
adicionales como orden de los vecinos de cada vértice, son una estructura clave en informática; véase árbol
(programación).
Un árbol etiquetado es un árbol en el que cada vértice tiene una única etiqueta. Los vértices de un árbol
etiquetado de n vértices reciben normalmente las etiquetas {1,2,..., n}.
Un árbol regular (homogéneo) es un árbol en el que cada vértice tiene el mismo grado. Véase grafo regular.
EJEMPLO
En árbol de ejemplo mostrado a la derecha tiene 6 vértices y 6 − 1 = 5 aristas. El único camino simple
que conecta los vértices 2 y 6 es 2-4-5-6.
Un árbol etiquetado con 6 vértices y 5 aristas
PROPIEDADES
Todo árbol es a su vez un grafo bipartito. Todo árbol con sólo un conjunto numerable de vértices es además
un grafo plano.
Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas
aristas son aristas de G.
Dado n vértices etiquetados, hay n n−2 maneras diferentes de conectarlos para construir un grafo. El resultado
se llama fórmula de Cayley.
El número de árboles con n vértices de grado d1,d2,...,dn es:
Que es un coeficiente multinomial.
No se conoce fórmula para el número t(n) de árboles con n vértices de un isomorfismo de grafos. Sin embargo,
el comportamiento asintótico de t(n) se conoce; hay números α ≈ 3 y β ≈ 0.5 tales que:
ARBOL BINARIO O ENRAIZADO
En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo
siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre
"binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es
llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los
árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.
DEFINICIÓN DE TEORÍA DE GRAFOS
Un árbol binario sencillo de tamaño 9, 4 niveles y altura 3 (altura = máximo nivel - 1), con un nodo raíz cuyo
valor es 2.
En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, acíclico y no dirigido
tal que el grado de cada vértice no es mayor a 3». De esta forma sólo existe un camino entre un par de nodos.
Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no
mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si rehusamos el
requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a
esta última estructura un bosque.
TIPOS DE ÁRBOLES BINARIOS
 Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
 Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
 Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos)
están a la misma profundidad (distancia desde la raíz, también llamada altura).
 A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol
binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1,
para alguna n.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario
cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo
izquierdo y el nodo de la derecha como hijo derecho.
COLORACIÓN DE GRAFOS
Un vértice coloración propia del grafo de Petersen con 3 colores, el número mínimo posible.
En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de
etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices de un
grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente,
una arista coloración asigna colores a cada arista talque aristas adyacentes no compartan el mismo color, y
una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que
compartan una frontera común tengan colores diferentes.
El vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser
transformados a una versión con vértices. Por ejemplo, una arista coloración de un grafo es justamente una
vértice coloración del grafo línea respectivo, y una coloración de caras de un grafo plano es una vértice
coloración del grafo dual.
La convención de usar colores se origina de la coloración de países de un mapa, donde cada cara es
literalmente coloreada. Esto fue generalizado a la coloración de caras de grafos inmersos en el plano. En
representaciones matemáticas y computacionales es típicamente usado enteros no-negativos como colores.
En general se puede usar un conjunto finito como conjunto de colores. La naturaleza del problema de
coloración depende del número de colores pero no sobre cuáles son.
ARISTA COLORACIÓN
Una arista coloración de un grafo, es una coloración de las aristas, denotada como la asignación de colores a
aristas tal que aristas incidentes tengan un color distinto. Una arista coloración con k colores es llamada karista-coloración y es equivalente al problema de particionar el conjunto de aristas en k emparejamientos. El
menor número de colores necesarios para un arista coloración de un grafo G es el índice cromático o número
cromático de aristas. Una coloración Tait es una 3-arista-coloración de un grafo cúbico. El teorema de los
cuatro colores es equivalente a que cada grafo cúbico sin puentes admite una coloración Tait.