Tema 4 rboles y Grafos.

Definiciones bsicas de teora de grafos.

Un grafo consta de un conjunto de nodos, un conjunto de aristas y una correspondencia f del conjunto de
aristas al conjunto de nodos.
Si una arista se corresponde con un par ordenado, entonces se dice que es una arista dirigida, en caso
contrario es una arista no dirigida.
Los pares de nodos que estn conectados por una arista dentro de un grafo se denominan nodos
adyacentes.
Un grafo en el que toda arista es dirigida se denomina digrafo o grafo dirigido.
Un grafo en el que todas las aristas son no dirigidas se denomina grafo no dirigido.
Si en un grafo hay aristas dirigidas y aristas no dirigidas se denomina mixta.
Sea G ( N , A) y sea e A una arista dirigida asociada al par ordenado de nodos (u,v). Se dice que la
arista e sale del nodo u o comienza en el nodo u y llega al nodo v o termina en el nodo v.
Tambin se dice que los nodos u y v son los nodos inicial y Terminal de la arista e.
Una arista e A que conecte los nodos u y v tanto si es dirigida como si no se dice que es incidente en los
nodos u y v.
Una arista que conecte un nodo consigo misma se denomina bucle o lazo.
En algunos grafos pueden existir ciertos pares de nodos que estn unidos por ms de una arista, se
denominan aristas paralelas.
Todo grafo que contenga aristas paralelas se denomina multigrafo.
Si no hay ms de una arista entre pares de nodos se denomina grafo sencillo.
Existen grafos en los que los nmeros de las aristas muestran los pesos de stas, se denominan grafos
ponderados.
En un grafo un nodo que no sea adyacente a ningn otro nodo se denominar nodo aislado.
Un grafo que contenga solamente nodos aislados se denomina grafo nulo.
En un grafo dirigido, para todo nodo v el nmero de aristas que tienen a v como nodo inicial se denomina
grado de salida del nodo v.
El nmero de aristas que tienen a v como nodo terminal es lo que se denomina grado de entrada.
La suma del ndice de entrada y el ndice de salida es lo que se denomina grado total del nodo v.
La suma de los grados de todos los nodos de un grafo debe de ser un nmero par que ser igual al doble
del nmero de aristas que haya en el grafo.

Sea N ( H ) el conjunto de nodos de un grafo H y sea N (G ) el conjunto de nodos un grafo G tales que
N ( H ) N (G ) . Si adems toda arista de H es tambin una arista de G, entonces se dice que el grafo H es
un subgrafo del grafo G y esto se expresa en la forma H G .
Un grafo G ( N , A) es completo si todos sus nodos son adyacentes a todos los nodos del grafo, se
denotan de la forma K n
Un grafo sencillo G ( N , A) se denomina grafo bipartito si N se puede descomponer en dos subconjuntos
V1 y V2 tales que no haya dos nodos de V1 que sean adyacentes ni tampoco dos nodos de V2 .
Sea G ( N , A) un digrafo sencillo, toda arista de A se puede expresar por medio de un par ordenado de
elementos de N, esto es A N N .
Cualquier subconjunto de N N define una relacin sobre N.

Caminos, accesibilidad y conexiones.

Sea G ( N , A) un digrafo sencillo, se dice que una sucesin de aristas es un camino de G si y solo si el
nodo terminal de cada arista del camino es el nodo inicial de la prxima arista del camino, si lo hubiere.
Un camino recorre los nodos que aparecen en la sucesin, comenzando en el nodo inicial de la primera
arista y finalizando en el nodo terminal de la ltima arista de la sucesin.
El nmero de aristas que aparecen en la sucesin de un camino se denomina longitud del camino.
Un camino de un digrafo en el cual todas las aristas sean distintas se denomina camino sencillo.
Un camino en el que todos los nodos sean diferentes se denomina camino elemental.
Un camino se denomina sencillo si no se repiten aristas.
Un camino se denomina elemental si no se repite ningn nodo.
Un camino que comienza y acaba en el mismo nodo se denomina ciclo.
Un ciclo se denomina sencillo si ninguna arista del ciclo aparece ms de una vez en el camino.
Un ciclo se denomina elemental si no pasa por ningn nodo ms de una vez.
Un digrafo sencillo que no tenga ningn ciclo se denomina aclclico.
Sea G ( N , A) un digrafo sencillo, entonces se define la relacin de camino, C de G en la forma
C u , v existe un camino del nodo u al nodo v.
Si un nodo v resulta alcanzable desde el nodo u, entonces un camino de longitud mnima que vaya de u a v
se denomina camino de longitud mnima.
La longitud de un camino de longitud mnima del nodo u al nodo v se denomina distancia y se denota
como d(u,v). Se supone que d(u,u)=0 para todo nodo u.
La longitud de un camino de un grafo es el nmero de aristas que aparecen en la sucesin del camino.
La alcanzabilidad es una relacin binaria sobre el conjunto de los nodos de un digrafo sencillo.
La alcanzabilidad es reflexiva y transitiva, pero no necesariamente simtrica o antisimtrica.
La distancia d(u,v) desde un nodo u hasta un nodo v satisface las propiedades siguientes:
d (u , v) 0
d (u , u ) 0
d (u , v) d (v, w) d (u , w)

La ltima igualdad se llama desigualdad triangular. Si no puede alcanzarse v desde u se escribe d (u, u ) .
Si se puede alcanzar v desde u y u desde v entonces d (u, v) no es necesariamente igual a d (v, u ) .
En un digrafo sencillo la longitud de cualquier camino elemental es menor o igual que n-1, en donde n es
el nmero de nodos que haya en el grafo, similarmente la longitud de cualquier ciclo elemental no
sobrepasar n.
El nmero de nodos diferentes de cualquier camino elemental de longitud k es k+1.
En un grafo sencillo no dirigido, una sucesin v1 , v2 ,..., vd forma un camino si para i 1, 2,3..., d existe una
arista no dirigida vi 1 , vi . Se dice que la arista vi 1 , vi se encuentra en el camino.
La longitud del camino est dada por el nmero de aristas que haya en el camino y es d-1.
Si v1 vd entonces el camino forma un ciclo.
Un ciclo sencillo en un grafo no dirigido es un ciclo sencillo que tiene que tener al menos tres aristas
distintas y en donde solo se repite el nodo inicial y el nodo final de la sucesin.
2

Se dice que un grafo no dirigido es conexo si para cualquier pareja de nodos del grafo se puede llegar
hasta el otro nodo partiendo de cualquiera de ellos.
Un digrafo es conexo o dbilmente conexo si es conexo como grafo codirigido, despreciando los sentidos
de las aristas, es decir si se transforman las aristas dirigidas en aristas no dirigidas.
Un digrafo sencillo se dice unilateralmente conexo si para toda pareja de nodos del grafo al menos uno de
los nodos de esa pareja se puede alcanzar desde el otro.
Si para toda pareja de nodos del grafo los dos nodos de la pareja se pueden alcanzar uno desde el otro,
entonces se dice que el grafo es fuertemente conexo.

Fuertemente conexo

Dbilmente conexo

Unilateralmente conexo

No Unilateralmente conexo

No Fuertemente conexo

Sea G ( N , A) un digrafo sencillo, y sea X N , se dice que el subgrafo cuyos nodos estn dados por el
conjunto X y cuyas aristas son todas aquellas aristas de G que tengan sus nodos iniciales y finales en X es
el subgrafo inducido por X.
Un subgrafo G1 se denomina maximal con respecto a alguna propiedad si no hay ningn otro subgrafo
que tambin posea esa propiedad y que incluya a G1 .
Para un digrafo sencillo los subgrafos maximales fuertemente conexos se denominan componentes fuertes.
Un subgrafo maximal unilateralmente conexo o un subgrafo maximal dbilmente conexo se denominan
componente unilateral o componente dbil.
En un digrafo sencillo G ( N , A) , todo nodo del digrafo se encuentra exactamente en un componente
fuerte.

Clculo de caminos a partir de una representacin matricial de los grafos.

Sea G ( N , A) un digrafo sencillo, en el cual N v1 , v2 ,...vn y se supone que los nodos estn ordenados
desde v1 hasta vn. La matriz Ad, nxn, cuyos elementos aij estn dados por
1, si vi , v j E
aij
0, en caso contrario

Se denomina matriz de adyacencia del grafo G.

Toda matriz cuyos elementos sean o bien 0 o bien 1 se denomina matriz de bits o matriz booleana.
Sea Ad la matriz de adyacencia de un digrafo G, el elemento de la i-esima fila y j-esima columna de Adn,
con n>0 es igual al nmero de caminos de longitud n que van desde el i-esimo nodo hasta el j-esimo.
Sea G ( N , A) un digrafo simple, sean vi y vj dos nodos cualesquiera de G.
A partir de la matriz de adyacencia de Ad se puede determinar inmediatamente si existe o no una arista
desde vi hasta vj en G.
Adems, a partir de la matriz Ad r , en donde r es algn entero positivo, se puede establecer el nmero de
caminos existentes entre vi y vj.
Si sumamos las matrices Ad , Ad 2 , Ad 3 ,..., Ad r para obtener Br , entonces: Br Ad Ad 2 Ad 3 ... Ad r , ser
posible determinar el nmero de caminos de longitud r que van desde vi hasta vj.
Para saber si vj es alcanzable desde vi hay que considerar todos los Ad r , para r= 1,2,3
En un grafo sencillo de n nodos la longitud de un camino o ciclo elemental no puede superar el valor n.
Cualquier camino se puede transformar en un camino elemental eliminando los ciclos.
Para determinar si existe un camino que vaya desde vi hasta vj hay que examinar los caminos elementales
de longitud menor o igual que n-1.
Si vi = vj el camino es un ciclo.
Mediante Bn se cuentan todos los caminos y todos los ciclos, Bn Ad Ad 2 Ad 3 ... Ad n
El elemento de la i-esima fila y j-esima columna de Bn muestra el nmero de caminos de longitud n o
menor que existen entre vi y vj.
Si este elemento es no nulo entonces se puede alcanzar vj y vi.
Sea G ( N , A) un digrafo sencillo en el cual #N = n y se supone que los nodos de G estn ordenados. La
matriz P nxn cuyos elementos estn dados por
1, si existe un camino desde vi hasta v j
pij
0, en caso contrario

se denomina matriz de caminos (matriz de alcanzabilidad) del grafo G.

La entrada de la diagonal principal pii es igual a 1 si y solo si existe un camino que vaya desde vi hasta s
mismo.

Recorrido de grafos representados como listas de adyacencia.

La representacin del grafo en forma de lista de adyacencia suele ser preferible cuando el grafo es
disperso, es decir que para cada nodo hay tan solo unas pocas de aristas que incidan en l.
Resulta ms adecuada una matriz de adyacencia si el grafo es denso.
Para determinar si un grafo contiene una arista, en el caso que est almacenado en forma de matriz de
adyacencia en el peor de los casos hay que examinar n2 elementos donde n es el nmero de nodos.
Si se utiliza una lista de adyacencia en el peor caso requiere n comparaciones.

Bsqueda en amplitud.
La bsqueda en amplitud se puede utilizar para hallar la distancia ms corta entre algn nodo inicial y los
nodos restantes del grafo. La bsqueda comienza en el nodo inicial, a continuacin se visitan todos los
nodos adyacentes al nodo inicial, repitiendo este proceso hasta recorrer todos los nodos.
Durante una bsqueda en amplitud en un grafo, se sigue un rbol de camino mnimo o de expansin.
Los nodos del rbol se examinan por orden creciente de nmero de nivel y de izquierda a derecha.
El recorrido de los nodos se almacena en una estructura de cola o FIFO (First in Firt Out).
El anlisis temporal para el procedimiento est en O(n m) .

Bsqueda en profundidad.
Una Bsqueda en profundidad es un algoritmo que permite recorrer todos los nodos de un grafo de
manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de
los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan ms
nodos que visitar en dicho camino, de modo que repite el mismo proceso con cada uno de los hermanos
del nodo ya procesado. El recorrido de los nodos se almacena en una estructura de cola o FIFO (First in
Firt Out). El anlisis temporal en el peor caso para el procedimiento est en O(n m) .

El algoritmo de Dijkstra para la bsqueda de caminos mnimos.

El algoritmo de Dijkstra, tambin llamado algoritmo de caminos mnimos, es un algoritmo para la
determinacin del camino ms corto dado un vrtice origen al resto de vrtices en un grafo dirigido y con
pesos en cada arista.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos ms cortos que parten
del vrtice origen y que llevan a todos los dems vrtices; cuando se obtiene el camino ms corto desde el
vrtice origen, al resto de vrtices que componen el grafo, el algoritmo se detiene. El algoritmo es una
especializacin de la bsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo
negativo. El anlisis temporal en el peor caso para el procedimiento est en O(n 2 ) .

rboles de expansin.
rboles libres.
Un rbol libre es un grafo sencillo no dirigido que es a la vez conexo y acclico.
Todo rbol libre que contenga n nodos debe de tener n-1 aristas.

rboles de expansin.
Un rbol de expansin de un grafo conexo no dirigido G ( N , A) es un rbol libre con el conjunto de
nodos N que es un subgrafo de G, es decir un rbol de expansin conexo, acclico y tiene a todo N como
nodos y a parte de A como conjunto de aristas.
Todo rbol de expansin para un grafo de n nodos contiene siempre n-1 aristas.
Para la generacin de un rbol de expansin se selecciona una sucesin de n-1 aristas, una a una tal que en
cada paso el subgrafo actual sea acclico.
Tanto la bsqueda en amplitud como la bsqueda en profundidad utilizan este enfoque.

rboles de expansin mnima.

Un rbol de expansin de un grafo ponderado conexo y no dirigido en el cual la suma de los costes de sus
aristas sea mnima se denomina rbol de expansin mnima.

Algoritmo de Prim y Kruskal

Dado un grafo, debemos obtener un nuevo grafo que slo contenga las aristas imprescindibles para que
todos los nodos queden conectados y la suma de las longitudes de las aristas de del nuevo grafo debe ser
tan pequea como sea posible, se aplica a problemas que tienen que ver con distribuciones geogrficas
Hay dos algoritmos que podemos utilizar para resolver este tipo de problemas: Kruskal y Prim.
Los algoritmos de Prim y Kruskal calculan, de distintas formas, el rbol de expansin mnimo de un grafo.
El algoritmo de Kruskal tiene un tiempo a log n , siendo a el nmero de aristas. Si la densidad es alta

el nmero de aristas a tiende a ser n(n-1)/2, con lo que el tiempo pasara a n 2logn , y el algoritmo de

Prim podra implementarse de forma que fuera mejor. En el caso de un grafo disperso (pocas aristas) el
nmero de aristas tendera a n, siendo en este caso el tiempo nlogn , siendo mejor que algunas
implementaciones del algoritmo de Prim. Pero si implementamos el algoritmo de Prim utilizando
montculos el tiempo requerido ser de a log n (al igual que el algoritmo de Kruskal).
Difieren en la forma de crear el camino mnimo. En el caso de Prim la solucin es siempre un rbol de
recubrimiento mnimo y en el otro caso, lo son las componentes conexas cuando finaliza el algoritmo.
El resultado es el mismo, nicamente difiere la forma en que va evolucionando.
6