Grafos

Grafos

1. Tipos de grafos

   • Grafos simples
     • “Son aquellos grafos que no tienen lazos ni lados paralelos” (Jiménez, 2008, pág. 288)
   • Grafo completo de n vértices (Kn)
     • “Es un grafo en donde cada vértice está relacionado con todos los demás, sin lazos ni lados paralelos. Se indica como Kn, en donde n es el número de vértices del grafo” (Jiménez, 2008).
     • “La valencia en cada uno de los vértices de los grafos completos es (n-1). En donde n es el número de vértices del grafo(n-1))/2” (Jiménez, 2008, pág. 289).
   • Complemento de un grafo (G)
     • Grafo que le falta al grafo G para formar un grafo completo de n vértices. Este grafo no tine lazos ni ramas paralelas. (Jiménez, 2008, pág. 290)
   • Grafo bipartido
     • “Esta compuesto por dos conjuntos de vértices, A={a1,a2,a3,..,an} y B={b1, b2,…, bn}, en donde los elementos del conjunto A se relacionan con los del conjunto B, pero entre los vértices de un mismo conjunto no existe arista que los una” (Jiménez, 2008, pág. 291)
     • Nunca tiene un ciclo de longitud impar.
   • Grafo bipartido completo (Kn, m)
     • “Es el grafo que está compuesto por dos conjuntos de vértices, uno de ellos A={a1, a2,.., an} y otro B={b1,b2,…bm}, y en el que cada vértice de A stá 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 insica como Kn,m” (Jiménez, 2008, pág. 291)

2. Algoritmos de recorrido y búsqueda

   • Camino
     • “Es una sucesión de lados que van de un vértice x a un vértice w (dichos lados se pueden repetir)”. (Jiménez, 2008, pág. 294)
   • Circuito (ciclo)
     • “Es un camino del vértice w al vértice w, esto es, un camino que regresa al mismo vértice de donde salió”. (Jiménez, 2008, pág. 294)
   • Circuito simple de longitud n
     • “Es aquel camino del vértice w al vértice w que solamente tiene un ciclo en la ruta que sigue” (Jiménez, 2008, pág. 294)
   • Camino simple de longitud n
     • “Es una sucesión de lados que van de un vértice x a un vértive w, en donde los lados que componen dicho camino son distintos e iguales a n, Esto significa que no se puede pasar dos veces por una misma arista”. (Jiménez, 2008, pág. 294)
   • Camino de Euler
     • “Es aquel camino que recorre todos los vértices pasando por todas las ramas solamente una vez. Siempre comienzan y terminan en vértices que tienen valencia impar, por lo tanto es necesario que tenga solamente dos vértices de valencia impar”. (Jiménez, 2008, págs. 296-297)
   • Circuito de Euler
     • “Ciclo que recorre todos los vértices pasando por todos los lados solamente una vez. Este sólo sucede si el grafo es conexo y todos sus vértices tienen valencia par”. (Jiménez, 2008, pág. 297)
   • Circuito de Hamilton
     • “Similar al circuito de Euler, con la diferencia de que en lugar de pasar por todos los lados del grafo solamente una vez, en el circuito de Hamilton se para por cada vértice solamente una vez”. (Jiménez, 2008, pág. 301)
   • Camino más corto
     • “Encontrar un camino entre dos vértices (o nodos) tal manera que la suma de los pesos de sus bordes constituyentes se reduce al mínimo”. (Alejandro López, 2014)
       • Algoritmos
         • Dijkstra
         • Bellman-Ford
         • Floyd-Warshall
         • Jonhson
   • A lo ancho
     • Explora sistemáticamente todas las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices más cercanos a un nodo inicial. Utiliza memorización y la queue para enlistar los nodos no visitados. (Ariana Callejas, s.f)
       • Algoritmo: BFS
         • Sea G = (V, A) un grafo conexo, V' = V un conjunto de vértices, A' un vector de arcos inicialmente vacío y P un vector auxiliar inicialmente vacío: 1.-Se introduce el vértice inicial en P y se elimina del conjunto. 2.-Mientras V' no sea vacío repetir los puntos 3 y 4. En otro caso parar.3.- Se toma el primer elemento de P como vértice activo. 4.-Si el vértice activo tiene algún vértice adyacente que se encuentre en V': Se toma el de menor índice. Se inserta en P como último elemento. Se elimina de V'. Se inserta en A' el arco que le une con el vértice activo. Si el vértice activo no tiene adyacentes se elimina de P.
   • Profundidad
     • Explora sistemáticamente las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices adyacentes a los visitados más recientemente. De esta forma se va "profundizando" en el grafo, es decir, alejándose progresivamente del nodo inicial. Utiliza recursión, un contador global y un vector de enteros para marcar los vértices ya visitados (meorización) y almacenar el orden del recorrido. (Ariana Callejas, s.f)
       • Algoritmo: DFS
         • Sea G = (V, A) un grafo conexo, V' = V un conjunto de vértice, A'un vector de arcos inicialmente vacío y P un vector auxiliar inicialmente vacío:1.- Se introduce el vértice inicial en P y se elimina del conjunto V'. 2.-Mientras V' no sea vacío repetir los puntos 3 y 4. En otro caso parar.3.- Se toma el último elemento de P como vértice activo. 4.-Si el vértice activo tiene algún vértice adyacente que se encuentre en V': Se toma el de menor índice. Se inserta en P como último elemento. Se elimina de V'. Se inserta en A' el arco que le une con el vértice activo. Si el vértice activo no tiene adyacentes se elimina de P.

3. Aurora Pérez Calderón - 1er Semestre de Ing. Sistemas Computacionales

   • Matemáticas Discretas

Imagens e arquivos do mapa