grafos

6 GRAFOS
Hemos considerado los árboles como una generalización del concepto de lista porque permiten que un elemento tenga más de un sucesor. Los grafos aparecen como una extensión del concepto deárbol, ya que en este nuevo tipo de estructuras cada elemento puede tener, además de más de un sucesor, varios elementos predecesores.
Esta propiedad hace a los grafos las estructuras más adecuadaspara representar situaciones donde la relación entre los elementos es completamente arbitraria, como pueden ser mapas de carreteras, sistemas de telecomunicaciones, circuitos impresos o redes deordenadores. Aunque hay estructuras más complejas que los grafos, no las veremos en este curso.
Los grafos se pueden clasificar en diferentes tipos dependiendo de cómo se defina la relación entre loselementos: podemos encontrar grafos dirigidos o no dirigidos y etiquetados o no etiquetados. También se pueden combinar ambas categorías.
6.1 Conceptos previos y terminología.
Formalmente, un grafo Gconsiste en dos conjuntos finitos N y A. N es el conjunto de elementos del grafo, también denominados vértices o nodos. A es el conjunto de arcos, que son las conexiones que se encargan de relacionar losnodos para formar el grafo. Los arcos también son llamados aristas o líneas.
Los nodos suelen usarse para representar objetos y los arcos para representar la relación entre ellos. Por ejemplo, losnodos pueden representar ciudades y los arcos la existencia de carreteras que las comunican.
Cada arco queda definido por un par de elementos n1, n2 ∈ N a los que conecta. Aunque habitualmente loselementos son distintos, permitiremos que sean el mismo nodo (n1 = n2). Representaremos gráficamente un arco como una línea que une los dos nodos asociados. ZaragozaMadridBarcelonaMálaga
Figura 6. 1.Grafo representativo de la conexión aérea de ciudades.
1
Tema 6: Grafos. T.A.D. 00/01
Si queremos representar mediante un grafo la red de vuelos de una compañía aérea entre diferentes ciudades,...