Teoria de Grafos

Teoria de Grafos

1. 5.1 Elementos, características y componentes de los grafos.

   • Elementos
     • Vértice: son puntos o nodos con los que están conformado los  grafos. Llamaremos grado de un vértice, al número de aristas de las que es extremo. Se le dice vértice “par” o “impar” según sea su grado.
     • Aristas: Una arista es  una relación entre dos vértices de un grafo.
     • Aristas Adyacentes: estas son dos   aristas  que se dirigen en al mismo vértice y se juntan en él.
     • Aristas Paralelas: estas son dos aristas si el vértice inicial y el final son uno mismo.
     • Cruce: Son dos aristas que cruzan en un punto.
     • Grado o Valencia de un Vértice:   Es el número de aristas que inciden sobre un vértice.
     • Lazo: es una arista cuales extremos inciden sobre el mismo vértice.
     • Vértice Adyacente: los vértices son adyacentes si están unidos mediante una arista.
     • Vértice Aislado: Es un vértice de grado cero.
     • Vértice Terminal: Es un vértice de grado 1.
   • Caracteristicas
     • (no dirigido) consta de un conjunto V de vértices o nodos y un conjunto E de aristas (arcos o lados) tales que cada arista e Є E queda asociada a un par no ordenado de vértices.
     • (dirigido G) consta de un conjunto V de vértices o nodos y un conjunto E de aristas (arcos o lados) tales que cada arista e Є E se asociada a un par no ordenado de vértices.
     • Una arista e en una grafica (dirigida o no) asociada con el par de vértices v y w es incidente en v y w, y se dice que v y w son incidentes en e y que son vértices adyacentes.
   • Componentes
     • Cuando dos aristas e1 y e2 están asociadas con el mismo par de vértices {v1, v2}, se dice que las aristas son paralelas.
     • Una arista incidente en un único vértice es un lazo.
     • Un vértice que no es incidente en alguna arista es un vértice aislado.
     • Una grafica sin lazos es una grafica simple.
     • Una grafica con números sobre las aristas se llama una grafica con pesos.
     • Si al arista e tiene la etiqueta k, decimos que el peso (valencia) de la arista e es k.
     • En una grafica con pesos, la longitud de un camino es la suma de los pesos de las aristas en el camino.
     • Un camino de longitud mínima que visite cada vértice exactamente una vez representa el camino optimo.
     • Grado de un vértice es el número de aristas incidentes en el nodo o vértice
   • 5.1.1 Tipos de grafos
     • Grafo acíclico: Es aquel  grafo no contiene ningún ciclo simple.
     • 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. Se ve que un grafo es bipartito si no hay ciclos de longitud impar.
     • Grafo bipartido completo (Kn, m): 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.
     • 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. Además  es un grafo simple en el que cada vértice es adyacente a cualquier todo otro vértice.
     • 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 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 nulo/vacío: El grafo nulo es el grafo cuyos conjuntos de aristas y de vértices son vacíos.
     • 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 ponderado: 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.
     • Grafo regular: Un grafo regular es un grafo cuyos vértices tienen el mismo grado.
     • Grafo simple: Un grafo simple es un grafo o dígrafo que no tiene bucles, y que no es un multígrafo.
     • 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.

2. 5.2 Representación de los grafos

   • Matriz de adyacencia (Ma)
     • Es una matriz cuadrada en la cual los vértices del grafo se indican como filas y como columnas: el orden de los vértices es el mismo que guardan las filas y las columnas de la matriz. Se coloca un 1 como elemento de la matriz cuando existe una relación entre uno y otro vértice, o bien un 0 cuando no exista relación alguna.
   • Matriz de incidencia (Mi)
     • En esta matriz se colocan los vértices del grafo como filas y las aristas como columnas.

3. 5.3 Algoritmos de recorrido y búsqueda

   • 5.3.1 El camino más corto
     • El método mas utilizado para encontrar la ruta mas corta de un nodo cualquiera w a cualquier nodo de la red, es por medio del algoritmo de Dijkstra.
       • El algoritmo Dijkstra: Al inicio a cada vértice u de G se le da una etiqueta L(u), que indica la mejor estimación actual de la longitud de la ruta mas corta de a a u.
     • Algoritmo prim
       • Se tiene un punto o nodo de partida, se selecciona la arista de menor peso adyacente a este nodo de inicio.
     • Algoritmo Kuskal
       • En el algoritmo de Kruskal, las aristas de un grafo conexo pesado son examinadas una por una en orden creciente de peso.
   • 5.3.2 A lo ancho
     • Aplicable sólo a grafos dirigidos acíclicos.
     • Se comienza en un nodo que no tenga ningún predecesor o antecesor.
     • Un vértice sólo se visita si han sido visitados todos sus predecesores
       • En particular, al comenzar sólo se pueden visitar los nodos que no tienen ningún predecesor
     • Aplicación
       • Representación de las fases de un proyecto mediante un grafo dirigido acíclico: los vértices representan tareas y las aristas relaciones temporales entre ellas.
       • Evaluación de atributos en la fase semántica de un compilador.
   • 5.3.3 En profundida
     • Para grafos dirigidos
       • Para no dirigidos: considerar cada arista no dirigida como un par de aristas dirigidas.
     • Es una generalización del recorrido preorden de un árbol:
       • se comienza visitando un nodo cualquiera;
       • se recorre en profundidad el componente conexo que cuelga de cada sucesor (por ejemplo, se examinan los caminos hasta que se llega a nodos ya visitados o sin sucesores);
       • si después de haber visitado todos los sucesores transitivos del primer nodo (por ejemplo, él mismo, sus sucesores, los sucesores de sus sucesores, …) todavía quedan nodos por visitar, se repite el proceso a partir de cualquiera de estos nodos no visitados.
     • Terminología:
       • Predecesores transitivos: antecesores.
       • Sucesores transitivos de un nodo: descendientes.
     • No hay un único recorrido en profundidad de un grafo sino un conjunto de ellos.
     • Es necesario llevar la cuenta de los nodos visitados.

4. La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos (también llamadas gráficas, que no se debe confundir con las gráficas que tienen una acepción muy amplia) estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados que pueden ser orientados o no. Por ello, también se conoce como análisis de redes.

5. Uribe Gonzalez Alexis Daniel 20590941

Imagens e arquivos do mapa