Grafos eulerianos

Grafos eulerianos
Llamaremos camino euleriano a un camino que contiene a todas las aristas del grafo, apareciendo cada una exactamente una vez.
Un ciclo euleriano es un camino euleriano quecomienza y acaba en el mismo vértice.
Definición.- Un grafo que admite un ciclo euleriano diremos que es un grafo euleriano.
Teorema.- Un grafo conexo G= (V,A) es euleriano ( todo vértice tiene grado par.Proposición.- Un grafo conexo tiene un camino abierto euleriano ( tiene exactamente dos vértices de grado impar.
Caminos hamiltonianos. Un camino hamiltoniano es un camino que recorre todos losvértices de un grafo sin pasar dos veces por el mismo vértice. Si el camino es cerrado se dice un ciclo hamiltoniano.Un grafo G se dice hamiltoniano si tiene un ciclo hamiltoniano.
Nota.- A diferencia delos grafos eulerianos, no hay una caracterización de cuando un grafo tiene un ciclo o un camino hamiltoniano
Definición.- Un grafo se dice plano si admite una representación gráfica en el plano demodo que dos aristas pueden cortarse únicamente en un vértice.
Una representación gráfica de este tipo se llama un mapa.
Teorema ( de Kuratowski)
Un grafo G es plano ( no contiene ningún subgrafoisomorfo a una subdivisión de K5 o K3,3.
Formula Euler. En un grafo planar
V – L + C = 2 V= numero de vértices L= numero de lados C= numero de caras
Un árbol A = (V,E) es un grafo nodirigido, conexo y sin ciclos
Un poco de terminología
➢ Los vértices de un árbol se llaman nodos
➢ Los nodos descendientes inmediatos de un nodo son sus hijos, y el nodo superior es el padre
➢ A unasecuencia descendente de nodos se le llama rama
➢ Los nodos sin hijos se llaman hojas, y los que sí tienen hijos nodos internos
➢ Un conjunto de árboles es un bosque
➢ El grado de un nodo es elnúmero de hijos que tiene
➢ Se llama profundidad de un nodo a la longitud del camino desde la raíz a ese nodo.
➢ La altura de un árbol es la profundidad del nodo más profundo.
Ejemplos

[pic]...