Grafos

Tema 6: Grafos.

T.A.D. 00/01

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 losgrafos las estructuras más adecuadas para 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 de ordenadores. 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ómose defina la relación entre los elementos: 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 G consiste 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 lasconexiones que se encargan de relacionar los nodos 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, los nodos 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 losque conecta. Aunque habitualmente los elementos 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.

Madrid

Málaga

Barcelona

Zaragoza

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 lared de vuelos de una compañía aérea entre diferentes ciudades, tendríamos el siguiente grafo G = {N, A}; N = {Málaga, Zaragoza, Madrid, Barcelona}; A = {(Madrid, Málaga), (Madrid, Barcelona), (Málaga, Barcelona), (Zaragoza, Barcelona)}. La representación gráfica sería la de la figura 6.1. Se dice que dos nodos son adyacentes o vecinos si hay un arco que los conecta. Los nodos adyacentes puedenser representados por pares (a, b). Un camino es una secuencia de nodos n1, n2, ..., nm tal que ∀i, 1 ≤ i ≤ (m-1), cada par de nodos (ni, ni+1) son adyacentes. Se dice que un camino es simple si cada uno de sus nodos, excepto tal vez el primero y el último, aparece sólo una vez en la secuencia. La longitud de un camino es el número de arcos de ese camino. Se puede considerar como caso especial unnodo por sí mismo como un camino de longitud 0. Un ciclo es un camino simple en el que el primer y último nodos son el mismo (n1 = nm). Si un camino desde un nodo a él mismo no contiene otros nodos entonces decimos que es un ciclo degenerado. Un grafo sin ciclos se dice acíclico. Si en un grafo G = {N,A}, N está formado por dos o más subconjuntos disjuntos de nodos (no hay arcos que conecten nodosde un subconjunto con nodos de otro subconjunto) entonces se dice que el grafo es desconectado o inconexo, en otro caso se dice que es conectado o conexo. 2 4 3 3 2 4

1

1

5 (a)

6

5 (b)

6

Figura 6. 2. Grafos (a) conexo y (b) inconexo.

6.1.1

Subgrafos.

Sea G = (N, A) un grafo con un conjunto de nodos N y un conjunto de arcos A. Un subgrafo de G es un grafo G’ = (N’, A’)tal que: 1. N’ es un subconjunto de N. 2. todos los elementos que aparecen en arcos de A’ pertenecen a N’. Si, además, A’ consta de todos los arcos (n, m) de A, tal que n y m están en N’, entonces G’ es un subgrafo inducido de G.

2

Tema 6: Grafos.

T.A.D. 00/01

6.1.2

Grafos dirigidos y no dirigidos.

Hasta ahora hemos supuesto que un arco conecta dos nodos en ambos sentidos...