grafos y grafos aplanables - 2
Post on 23-Oct-2015
109 Views
Preview:
TRANSCRIPT
1. GRAFOS Y GRAFOS APLANABLES
1.1. PASEOS CORTOS EN GRAFOS PESADOS
Grafo pesado, ponderado ó etiquetado.Un grafo es pesado cuando sus aristas contienen datos (etiquetas). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso.
1.2 PASES Y CIRCUITOS EULERIANOS (DE EULER)
Definición:Un paseo de Euler (Euleriano) es un camino que incluye todos los lados - y por lo tanto todos los vértices - de un grafo dado, una y solo una vez.
Definición:Un circuito de Euler (Euleriano) es un circuito que incluye todos los lados - y por lo tanto todos los vértices - de un grafo dado una y solo una vez.Condiciones para saber si un grafo dado tiene un paseo o circuito de Euler.
1) Un grafo no dirigido G tiene un paseo de Euler si y solo si tiene cero o dos vértices de valencia impar.
2) Si un grafo no dirigido G tiene un circuito de Euler entonces todo vértice de G tiene valencia par, además de ser conexo.
Ejemplos:
verificar si los siguientes grafos no dirigidos tienen u paseo o circuito de Euler
top related