Grafos

Grafos

1. son

   • Un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas o arcos).
     • Ejemplos de uso son:
       • Modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que se pueden obtener caminos óptimos para el trayecto
       • Administración de proyectos, utilizando técnicas como la técnica de revisión y evaluación de programas (PERT) en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.
       • Resolución de diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura.
       • Problemas de control de producción, para proyectar redes de ordenadores, para diseñar módulos electrónicos modernos y proyectar sistemas físicos con parámetros localizados (mecánicos, acústicos y eléctricos).
     • Algunos tipos de grafos:
       • Grafo simple: es aquel que acepta una sola una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo.
         • • Multigrafo. o pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.
       • Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha
         • • Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices.
       • Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.
         • • Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.
       • Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.
     • Siendo:
       • Las aristas o arcos una relación matemática que conecta dos vértices. Una arista dirigida es una arista de un dígrafo y tiene una dirección asociada consigo, esto es, posee un vértice inicial y un vértice final. Una arista no dirigida es una donde no se distingue un vértice inicial ni uno final.
       • Un vértice o nodo es la unidad fundamental de la que están formados los grafos.
       • La longitud de un camino es el número de aristas que usa dicho camino, contando aristas recorridas varias veces el mismo número de veces que las recorramos. En el ejemplo, (1, 2, 5, 1, 2, 3) es un camino con longitud 5, y (5, 2, 1) es un camino simple de longitud 2.
       • El factor de peso el valor que se puede asociar con un arco. Depende de lo que el grafo represente.
     • Operaciones con grafos:
       • Insertar vértice: La operación de inserción de un nuevo vértice es una operación muy sencilla, únicamente consiste en añadir una nueva entrada en la tabla de vértices (estructura de datos que almacena los vértices) para el nuevo nodo. A partir de ese momento el grafo tendrá un vértice más, inicialmente aislado, ya que ninguna arista llegará a él.
         • Insertar arista Esta operación es también muy sencilla. Cuando se inserte una nueva arista en el grafo, habrá que añadir un nuevo nodo a la lista de adyacencia (lista que almacena los nodos a los que un vértice puede acceder mediante una arista) del nodo origen, así si se añade la arista (A,C), se deberá incluir en la lista de adyacencia de A el vértice C como nuevo destino.
           • Eliminar vértice Esta operación es inversa a la inserción de vértice. En este caso el procedimiento a realizar es la eliminación de la tabla de vértices del vértice en sí. A continuación, habrá que eliminar las aristas que tuviesen al vértice borrado como origen o destino.
             • Eliminar arista Mediante esta operación se borra un arco del grafo. Para llevar a cabo esta acción es necesario eliminar de la lista de adyacencia del nodo origen el nodo correspondiente al nodo destino.
               • Las operaciones adicionales que puede incluir un grafo son muy variadas. Además de las clásicas de búsqueda de un elemento o recorrido del grafo, también podemos encontrarnos con ejecución de algoritmos que busquen caminos más cortos entre dos vértices, o recorridos del grafo que ejecuten alguna operación sobre todos los vértices visitados, por citar algunas operaciones de las más usuales.
       • Recorridos
         • La operación de recorrer una estructura de datos consiste en visitar (procesar) cada uno de los nodos a partir de uno dado. Así, para recorrer un árbol se parte del nodo raíz y según el orden se visitan todos los nodos. De igual forma, recorrer un grafo consiste en visitar todos los vértices alcanzables a partir de uno dado. Hay dos formas de recorrer un grafo: recorrido en profundidad y recorrido en anchura. Si el conjunto de nodos marcados se trata como una cola, entonces el recorrido es en anchura; si se trata como una pila, el recorrido es en profundidad.
           • El recorrido en anchura trabaja de la siguiente manera: 1. Se visita el nodo inicial. 2. Después de visitar el nodo inicial se visitan todos los sucesores. 3. Después los sucesores de los sucesores. 4. Se repiten los pasos 1 y 2 hasta encontrar un nodo sin arcos salientes o ya visitados. 5. Si después de visitar todos los descendientes del primer nodo, todavía quedan más nodos por visitar, se repite el proceso reiniciando.
           • La estrategia de recorrido en profundidad es la siguiente: 1. Se toma un nodo “s” como comienzo, y se marca. 2. A continuación se toma y se marca un nodo no marcado adyacente a “s”, y ese nodo pasa a ser el nuevo nodo de partida, dejando posiblemente por el momento al nodo inicial original con nodos no explorados. 3. La búsqueda continúa por el grafo hasta que el camino en curso finalice con un grafo de salida igual a cero, o bien en un nodo en que todos los nodos adyacentes estén marcados. 4. A continuación la búsqueda vuelve al último nodo que todavía tenga nodos adyacentes sin marcar, y continúa marcando todos los nodos de forma recursiva hasta que ya no queden nodos sin marcar.