Grafos

|Grafos |
|  |
|Definición|
|Un grafo es un objeto matemático que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computación, ya que |
|permiten resolver problemas muy complejos. |
|Imaginemos que disponemos de una serie deciudades y de carreteras que las unen. De cada ciudad saldrán varias carreteras, por lo que para ir de |
|una ciudad a otra se podrán tomar diversos caminos. Cada carretera tendrá un coste asociado (por ejemplo, la longitud de la misma). Gracias a la |
|representación por grafos podremos elegir el camino más corto que conecta dos ciudades, determinar si es posible llegar de una ciudad a otra,si |
|desde cualquier ciudad existe un camino que llegue a cualquier otra, etc. |
|El estudio de grafos es una rama de la algoritmia muy importante. Estudiaremos primero sus rasgos generales y sus recorridos fundamentales, para |
|tener una buena base que permita comprender los algoritmos que se pueden aplicar.|
|  |
|Glosario |
|Un grafo consta de vértices (onodos) y aristas. Los vértices son objetos que contienen información y las aristas son conexiones entre vértices. |
|Para representarlos, se suelen utilizar puntos para los vértices y líneas para las conexiones, aunque hay que recordar siempre que la definición de|
|un grafo no depende de su representación.|
|Un camino entre dos vértices es una lista de vértices en la que dos elementos sucesivos están conectados por una arista del grafo. Así, el camino |
|AJLOE es un camino que comienza en el vértice A y pasa por los vértices J,L y O (en ese orden) y al final va del O al E. El grafo será conexo si |
|existe un camino desde cualquier nodo del grafo hasta cualquier otro. Si no esconexo constará de varias componentes conexas. |
|Un camino simple es un camino desde un nodo a otro en el que ningún nodo se repite (no se pasa dos veces). Si el camino simple tiene como primer y |
|último elemento al mismo nodo se denomina ciclo. Cuando el grafo no tiene ciclos tenemos un árbol (ver árboles). Varios árboles independientes |
|forman un bosque. Un árbolde expansión de un grafo es una reducción del grafo en el que solo entran a formar parte el número mínimo de aristas que|
|forman un árbol y conectan a todos los nodos. |
|Según el número de aristas que contiene, un grafo es completo si cuenta con todas las aristas posibles (es decir, todos losnodos están conectados |
|con todos), disperso si tiene relativamente pocas aristas y denso si le faltan pocas para ser completo. |
|Las aristas son la mayor parte de las veces bidireccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido |
|hacia B como en sentido hacia A: estos son llamados grafos no...