Rangel Cortes Guadalupe 5v1A
!!! GRAFOS, VALENCIA, RECORRIDOS Y CAMINOS
GRAFO
Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (arcs en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
El grado o valencia
de un vértice es el número de aristas incidentes en él. Para un grafo con bucles, éstos son contados por dos.
TEOREMA DE EULER
En un grafo conexo podemos encontrar un circuito de Euler si solo si, cuando todas sus valencias son pares. Un grafo conexo tiene un camino de Euler si solo si todas sus valencias son pares, excepto dos.
EJEMPLO DE GRAFO PARA LOS RECORRIDOS Y CAMINOS
Recorrido:
Secuencia de aristas consecutivas.
(A,
Recorrido cerrado:
Si termina donde empieza.
(A, B), (B, E), (E, A)
Camino:
Recorrido que tiene aristas distintas.
(A, B), (B, C), (C, F), (F, B)
Camino cerrado:
Termina donde empieza.
(A, B), (B, E), (E, A)
Camino simple: Si no utiliza dos veces un mismo nodo, ni tampoco la misma arista.
CIRCUITO DE HAMILTON
Es un camino simple cerrado que utiliza todos los nodos.
(A, B), (B, C), (C, D), (D, G), (G, I), (I, F), (F, H), (H, E), (E, A)
Ejemplo de grafo para camino de Hamilton
CAMINO DE HAMILTON
Es un camino simple que utiliza todos los nodos.
(A, C), (C, E), (E, D), (D,B)