Transcript
Page 1: Grafos y Grafos Aplanables - 2

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