Teoría de Grafos

Teoría de Grafos

1. Grafo

   • El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana.
     • algunos ejemplos podrían ser los siguientes: un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama),grafos matemáticos que representan las relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad.
       • En cada caso,es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos(vértices)con líneas conectándolos (arcos).

2. tipos de grafos

   • Grafos ponderados
     • Un grafo ponderado es aquel que  asocia un valor o peso a cada arista en el grafo. El peso de un camino en un grafo con pesos es la suma de los pesos de todas las aristas atravesadas.
   • Grafos bipartitos
     • Un grafo bipartito es cualquier grafo, cuyos vértices pueden ser divididos en dos conjuntos, tal que no haya aristas entre los vértices del mismo conjunto. Se ve que un grafo es bipartito si no hay ciclos de longitud impar
   • Grafo simple
     • Un grafo simple es un grafo o dígrafo que no tiene bucles, y que no es un multígrafo.
   • Grafos conexos
     • Decimos que es un grafo conexo, si es posible formar un camino desde cualquier vértice a cualquier otro en el grafo.
   • Grafos completos
     • Un grafo es completo si cada vértice tiene un grado igual a n-1, donde n es el número de vértice que compone el grafo. Además  es un grafo simple en el que cada vértice es adyacente a cualquier todo otro vértice.
   • Grafo plano
     • Un grafo plano es uno que es posible dibujar en el plano sin que ningún par de aristas se crucen entre sí.
   • Grafo no Simple
     • Grafo no dirigido que tiene lados paralelos y lazos.
   • Grafo trivial
     • Un grafo trivial es  aquel  grafo vacío con un único vértice
   • Grafo regular
     • Un grafo regular es un grafo cuyos vértices tienen el mismo grado.
   • Grafo nulo/vacío
     • El grafo nulo es el grafo cuyos conjuntos de aristas y de vértices son vacíos.
   • Grafo no dirigido
     • Son aquellos grafos  en los cuales los lados no están orientados (no son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas
   • Grafo dirigido
     • Es un conjunto de vértices V y un conjunto de aristas E tal que para cada arista perteneciente al conjunto de aristas E se asocia con dos vértices en forma ordenada.
   • Grafos bipartitos completos
     • Es el grafo que esta compuesto por dos conjuntos de vértices, uno de ellos A = {a1, a2, a3,..., an} y otro B = {b1, b2,..., bm], y en el que cada vértice de A esta unido con todos los vértices de B, pero entre los vértices de un mismo conjunto no existe arista que los una. El grafo bipartido completo se indica como Kn,m

3. representacion de grafos

   • Matriz
     • adyacencia
       • Una de las maneras más fáciles de implementar un grafo es usar una matriz bidimensional. En esta implementación de matriz, cada una de las filas y columnas representa un vértice en el grafo.
         • El valor que se almacena en la celda en la intersección de la fila v y la columna w indica si hay una arista desde el vértice v al vértice w. Cuando dos vértices están conectados por una arista, decimos que son adyacentes.
     • incidencia
       • En esta matriz se colocan los vértices del grafo como filas y las aristas como columnas.
         • Es posible representar lados paralelos. Al sumar los elementos de cada una de las filas se obtiene la valencia de los vértices, y Al sumar las columnas es posible distinguir cuando se trata de un lazo ya que su suma es 1, como ocurre con r3 y r8. Cuando no se trata de lazos, el resultado de la suma es 2.
   • Representación computacional
     • la forma mas fácil de representar un grafo en cuanto a la programación seria mediante de un arreglo
       • Tipo nombre del arreglo [][] = new tipo [][]
       • existen los arreglos unidimencionales y los bidemencionales

4. algoritmos de recorrido

   • Prim
     • Funciona diferente del de Kruskal.
       • Si hay un punto o nodo de inicio, se selecciona el borde con el peso más bajo adyacente a este punto de inicio. Se agregarán bordes y vértices a cada etapa. El borde agregado es el borde con el menor peso que conecta los vértices.
   • hamiltoniano
     • Camino
       • Un camino sin vértices repetidos que recorre todos los vértices del grafo se llama camino hamiltoniano. Un camino hamiltoniano que sea un circuito se llama circuito hamiltoniano. Un grafo que tiene un circuito hamiltoniano se llama grafo hamiltoniano. Para grafos dirigidos, o dígrafos, las definiciones correspondientes tienen en cuenta que las aristas están dirigidas. Un camino dirigido en un digrafo es camino dirigido hamiltoniano si visita todos los vértices del digrafo sin repetir ninguno.
     • Ciclo
       • Es un ciclo en un grafo que contiene/ recorre/pasa por cada vértice exactamente una sola vez, excepto el inicial y final.
   • Euleriano
     • Camino
       • Es aquel camino que recorre todos los vértices pasando por todas las aristas solamente una vez. Un camino de Euler deberá iniciar y terminar en vértices de valencia impar.
     • Ciclo
       • Es aquel ciclo que recorre todos los vértices pasando por todos los lados solamente una vez. Un grafo tiene circuito de Euler solamente si es conexo y todos su vértices tienen valencia par.
   • Kruskal
     • Los bordes del gráfico de conexión ponderado se comprueban uno por uno en el orden de peso de mayor a menor. Después de seleccionar el borde necesario con el menor peso, se permite que el borde alcance cualquier nodo; se obtendrá el gráfico con el menor peso.
   • Dijkstra
     • También conocido como el algoritmo de ruta mínima, este es un algoritmo que se utiliza para determinar la ruta más corta al resto de los vértices en la que cada vértice tiene un peso en el gráfico dado el vértice original.
       • Inicializar todas las distancias en D con un valor infinito relativo, ya que son desconocidas al principio, exceptuando la de x, que se debe colocar en 0, debido a que la distancia de x a x sería 0.
         • Sea a = x (Se toma a como nodo actual.)
           • Se recorren todos los nodos adyacentes de a, excepto los nodos marcados. Se les llamará nodos no marcados vi.
             • Para el nodo actual, se calcula la distancia tentativa desde dicho nodo hasta sus vecinos con la siguiente fórmula: dt(vi) = Da + d(a,vi). Es decir, la distancia tentativa del nodo ‘vi’ es la distancia que actualmente tiene el nodo en el vector D más la distancia desde dicho nodo ‘a’ (el actual) hasta el nodo vi. Si la distancia tentativa es menor que la distancia almacenada en el vector, entonces se actualiza el vector con esta distancia tentativa. Es decir, si dt(vi) < Dvi → Dvi = dt(vi)
               • Se marca como completo el nodo a.
                 • Se toma como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y se regresa al paso 3, mientras existan nodos no marcados.

5. algoritmos de busqueda

   • Recorrido en Anchura
     • Es un algoritmo de búsqueda ignorante que se utiliza para recorrer o buscar elementos en gráficos. De manera intuitiva, comienza en la raíz y analiza todos los vecinos de ese nodo. Luego, para cada vecino, se escanearán sus respectivos vecinos, y así sucesivamente, hasta que se atraviese todo el árbol.
       • Dado un vértice fuente s, Breadth-first search sistemáticamente explora los vértices de G para “descubrir” todos los vértices alcanzables desde s.
         • Calcula la distancia (menor número de vértices) desde s a todos los vértices alcanzables.
           • Después produce un árbol BF con raíz en s y que contiene a todos los vértices alcanzables.
             • El camino desde s a cada vértice en este recorrido contiene el mínimo número de vértices. Es el camino más corto medido en número de vértices.
               • Su nombre se debe a que expande uniformemente la frontera entre lo descubierto y lo no descubierto. Llega a los nodos de distancia k, sólo tras haber llegado a todos los nodos a distancia k-1.
   • Recorrido en Profundidad
     • Es un algoritmo que permite atravesar todos los nodos del gráfico. Es una generalización del camino predeterminado del árbol. La estrategia consiste en comenzar en un cierto vértice v y comenzar allí cuando se visita un nuevo vértice, explorando todos los caminos que lo abandonan. No puede comenzar hasta que termine de explorar un camino desde el siguiente.
       • El camino dejará de explorar cuando llegue al vértice visitado anteriormente. Si hay un vértice al que no se puede llegar desde v, la ruta está incompleta; entonces, debe seleccionar un vértice como un nuevo vértice inicial y repetir el proceso.

Imagens e arquivos do mapa