Month: enero 2011
-
Tema 7: Grafos ponderados (Sesión 21/12/2010)
GRAFOS PONDERADOS En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así un grafo valuado o ponderado. Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; su interés previsible será minimizar la distancia recorrida (o…
-
Tema 6: Problemas de recorrido de vértices (Sesión 14/12/2010)
PROBLEMAS DE RECORRIDO DE VÉRTICES Definiciones: 1. Un camino Hamiltoniano es en grafo G es un camino que atraviesa cada vértice del grafo exactamente una vez. 2. Un cliclo Hamiltoniano en un grafo G es un ciclo que atraviesa cada vértice del grafo exactamente una vez. 3. Un grafo es Hamiltoniano si contiene un ciclo…
-
Tema 6: Problemas de recorrido de aristas (Sesión 14/12/2010)
PROBLEMAS DE RECORRIDO DE ARISTAS Primero vamos a ver varias definiciones: Siendo G un grafo conexo y, en general, no simple: 1. Llamaremos tour de G a una cadena cerrada que atraviesa cada arista de G al menos una vez. 2. Llamaremos tour euleriano de G a un tour de G que atraviesa cada arista…
-
Tema 6: Cálculo de componentes conexas (Sesión 30/11/2010)
CÁLCULO DE COMPONENTES CONEXAS Existen 2 métodos para calcular las componentes conexas de un grafo dirigido: MÉTODO 1 Paso 1 – Escogemos un vértice cualquiera, podemos empezar por el 1. Paso 2 – Vemos donde interseccionan R(v1) con Q(v1), es decir, si por ejemplo tenemos una matriz de accesibilidad, vamos a la fila 1, osea…