COMPLETO
Un grafo no dirigido G= es COMPLETO si existe arista entre todo par de vértices
de V. Sea n=|V|, el número de aristas de un grafo completo no dirigido es
exactamente |E|=n.
(n-1)/2. Si se trata de un grafo dirigido entonces |E|=n.
(n-1).
GRAFOS EULERIANOS
Se dice que un grafo no dirigido G= es EULERIANO si existe un camino cerrado,
propio, simple (no se repiten aristas) pero no necesariamente elemental que
incluye todas las aristas de G.
Los siguientes lemas permiten determinar si un grafo dado es euleriano:
Lema 1: Un grafo no dirigido y conexo es euleriano si y sólo si el grado de todo
vértice es par.
Lema 2: Un grafo dirigido y fuertemente conexo es euleriano si y sólo si el grado de
todo vértice es cero.
Averiguar si un grafo no dirigido y conexo es euleriano tiene un coste de θ(n), si se
supone conocido el grado de cada vértice; gracias al lema 1 basta con recorrer el
conjunto de vértices y comprobar si el grado de cada uno de ellos es par o no lo es.
GRAFOS HAMILTONIANOS
Un grafo no dirigido G= es HAMILTONIANO si existe un camino cerrado y
elemental (no se repiten vértices) que contiene todos los vértices de G. Si existe, el
camino se llama circuito hamiltoniano.
Anàlisi i Disseny d’Algorismes – ADA Grafos
FIB – UPC, curs 2007/2008
María Teresa Abad 6
Departament Llenguatges i Sistemes Informàtics
En este caso no existe ninguna propiedad que permita determinar la existencia del
camino por lo que averiguar si existe tiene el mismo coste que calcular
directamente el camino (es un problema NP-C). La forma habitual de resolverlo es
aplicar el esquema de Vuelta Atrás que va construyendo todos los caminos posibles
y, para cada uno de ellos, comprueba si cumple la condición de hamiltoniano.
Ejemplo: Este vídeo no tiene lucro para esta pagina
No hay comentarios:
Publicar un comentario