TEORÍA DE GRAFOS

TEORÍA DE GRAFOS

1. Un grafo es un par ordenado el cual está compuesto por un conjunto vértices y un conjunto de aristas, donde cada arista del grafo es un subconjunto de este, donde relaciona dos o más elementos del conjunto de vértices. Cada arista es un subconjunto {u,v } con u y v ∈ V, u ≠ v

   • Vértice
     • Son puntos o nodos con los que están conformado los grafos.
   • Aristas
     • Una arista es  una relación entre dos vértices de un grafo.
   • Lazo
     • Es aquella arista que sale de un vértice y regresa al mismo vértice.
   • Valencia de un vértice
     • Es el número de lados que salen o entran a un vértice
   • Peso de una arista
     • Si al arista e tiene la etiqueta k, decimos que el peso (valencia) de la arista e es k.
   • longitud de un camino
     • es la suma de los pesos de las aristas en el camino.
   • camino optimo
     • Un camino de longitud mínima que visite cada vértice exactamente una vez
   • • V(G) = {1; 2; 3; 4; 5; 6; 7}
     • E(G) = {(1; 2); (2; 4); (2; 7); (3; 5); (3; 6); (4; 5); (4; 6); (4; 7); (5; 6); (6; 7)}
     • Vertices = 7
     • Aristas = 10
     • Valencia o grado de vértices
       • V(1)=1 V(2)=2 V(3)=2 V(4)=4 V(5)=3 V(6)=4 V(7)=3
     • Lazos = {0}
     • Peso de aristas ={es un grafo no ponderado}
   • Grafos ponderados
     • Una grafica con números sobre las aristas se llama una grafica con pesos
   • Grafo dirigido
     • Si existe una única arista e asociada con el par ordenado (v,w) de vértices, escribimos e = (v,w) lo cual denota una arista de v a w.

2. Tipos de grafos

   • Grafo cíclico: Un grafo se dice cíclico si contiene algún ciclo simple.
   • Grafo bipartito: 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.
   • Grafo bipartido completo (Kn, m): Es el grafo que esta compuesto por dos conjuntos de vértices 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.
   • Grafo completo: 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.
   • Grafo conexo: Decimos que es un grafo conexo, si es posible formar un camino desde cualquier vértice a cualquier otro en el grafo.
   • Grafo denso: Un grafo denso es aquel grafo en el que el número de aristas está cercano al número de máximo de aristas.
   • 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.
   • Grafo nulo/vacío El grafo nulo es el grafo cuyos conjuntos de aristas y de vértices son vacíos.

3. Algoritmos de recorrido

   • PRIM
     • El algoritmo de Prim, dado un grafo conexo, no dirigido y ponderado, encuentra un árbol de expansión mínima. Es decir, es capaz de encontrar un subconjunto de las aristas que formen un árbol que incluya todos los vértices del grafo inicial, donde el peso total de las aristas del árbol es el mínimo posible.
   • Dijkstra
     • es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Este consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.
   • KRUSKAL
     • El algoritmo de Kruskal, dado un grafo conexo, no dirigido y ponderado, encuentra un árbol de expansión mínima. Es decir, es capaz de encontrar un subconjunto de las aristas que formen un árbol que incluya todos los vértices del grafo inicial, donde el peso total de las aristas del árbol es el mínimo posible 1. Se selecciona, de entre todas las aristas restantes, la de menor peso siempre que no cree ningún ciclo. 2. Se repite el paso 1 hasta que se hayan seleccionado |V| - 1 aristas.
   • Hamilton
     • ciclo
       • Un circuito hamiltoniano es un camino cerrado en un que utiliza cada vértice del grafo exactamente una vez, exceptuando el último que es igual al primero, es decir Vértice inicial= Vértice final, además todos los vértices son adyacentes
     • camino
       • Un camino hamiltoniano es un camino que visita cada vértice exactamente una vez. Vértice inicial ≠ Vértice final
   • Euler
     • 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.
     • camino
       • Será considerado camino euleriano si, y solo si, G tiene exactamente dos vértices de grado impar y todos los demás vértices son de grado par y además que atraviesa cada arista exactamente una vez, se comienza en uno de los vértices de grado impar y se terminar el camino el otro vértice de grado impar

4. Representación de grafos

   • Matrices
     • Adyacencia
       • Digamos que el conjunto de vértices es V = {v1,...,vn}. Ordenamos esos vértices de cierta manera, por ejemplo (v1,...,vn). Y ahora construimos la matriz n × n, cuyas filas y columnas van etiquetadas con esos vértices, y cuyas entradas, para cada 1 ≤ i, j ≤ n, llevan un 1 en la posición (vi, vj ) si {vi, vj} ∈ A, y un 0 en caso contrario, si en la posición (vi, vj ) aparece un 1 es porque {vi, vj} ∈ A;
     • Incidencia
       • La matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El número de unos que aparece en cada fila es igual al grado del vértice correspondiente. Una fila compuesta sólo por ceros corresponde a un vértice aislado.
   • representación computacional
     • Representación mediante matrices: La forma más fácil de guardar datos en nodos es mediante la utilización de un vector que indique los nodos, de manera que aristas entre los nodos se puedan ver como relaciones entre los índices.
       • Tipo_de_variable[ ][ ]… [ ] Nombre_del_array = new Tipo_de_variable[dimensión1][dimensión2]…[dimensiónN];
       • Arreglos unidimencionales
         • Es un arreglo que solo posee una dimensión, está formado por un conjunto de elementos del mismo tipo de datos que almacenan bajo un nombre y se diferencia por la posición de cada uno en el arreglo que inicia desde el 0.Estos pueden ser de 1 hasta n veces, donde n es un número de elementos del arreglo.
           • TipoDato nombre[]=new TipoDato[Total de elementos];

5. Algoritmos de busqueda

   • DFS o Depth First Search
     • La búsqueda en profundidad se avanza de vértice en vértice, marcando cada vértice visitado. La búsqueda siempre avanza hacia un vértice no marcado, internándose “profundamente” en el grafo sin repetir ningún vértice. Cuando se alcanza un vértice cuyos vecinos han sido marcados, se retrocede al anterior vértice visitado y se avanza desde éste. Si dado un grafo simple G, escogemos un vértice v para iniciar la exploración del grafo utilizando la búsqueda en profundidad, el árbol que se construye es un árbol generador de la componente conexa del grafo que contiene a v.
   • BFS - Breadth First Search
     • La búsqueda en anchura es otro procedimiento para visitar sistemáticamente todos los vértices de un grafo. Es adecuado especialmente para resolver problemas de optimización, en los que se deba elegir la mejor solución entre varias posibles. Al igual que en la búsqueda en profundidad se comienza en un vértice v (la raíz) que es el primer vértice activo. En el siguiente paso se etiquetan como visitados todos los vecinos del vértice activo que no han sido etiquetados. Se continúa etiquetando todos los vecinos de los hijos de v (que no hayan sido visitados aún). En este proceso nunca se visita un vértice dos veces por lo que se construye un grafo sin ciclos, que será un árbol generador de la componente conexa que contiene a v

Bilder und Dateien der Mindmap