Category: Matematica discreta
-
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…
-
Tema 6: Accesibilidad y conectividad (Sesión 30/11/2010)
Y comenzamos con el tema 6 de matemáticas 1: Accesibilidad y conectividad. ACCESIBILIDAD Sea G = {V,A} un grafo dirigido. 1. Sean xi y xj dos vértices dentro del conjunto de vértices de G, diremos que xi alcanza a xj, o que xj es alcanzable por xi, si existe un camino dirigido de xi a…
-
Tema 5: Representación matricial (Sesión 30/11/2010)
En este post vamos a ver como podemos representar un grafo mediante matrices de adyacencia e incidencia. MATRIZ DE ADYACENCIA Definición Sea G un grafo con n vértices {vi}i –> n = 1. Llamamos matriz de adyacencia a la matriz de orden n x n, de manera que cada elemento de la matriz es igual…
-
Tema 5: Caminos y conexión (Sesión 23/11/2010)
Según la disposición y dirección de las aristas y arcos, podemos obtener las siguientes definiciones basándonos en un grafo G: 1. Una cadena es una sucesión finita de vértices-aristas. W= v0e1v1…ekvk. 2. La longitud de una cadena es el numero de aristas|arcos que contiene. 3. Una cadena simple es una cadena con todas sus aristas…
-
Tema 5: Tipos de grafos (Sesión 09/11/2010 y 16/11/2010)
¿Un Grafo? ¿Y eso que es? Podemos clasificar los grafos en 2 tipos básicos, dirigidos y no dirigidos. 1. Los grafos dirigidos están formados por vértices y arcos. Los arcos son pares ordenados de vértices, es decir, A -> B, el vértice A es el primero y B el segundo, y esta unidos por un…
-
Hello world
Bueno, pues empezamos con la matemática discreta, ya que me convalidaron la parte de Lógica computacional con un 7,3 que tenia del 2005. Espero que este blog sirva para estudiar a quienes vengan detrás, porque me he dado cuenta que no hay mucho material de MD por internet.