Árboles
Árboles. Árboles enraizados I Búsqueda en profundidad. Búsqueda en anchura I Árboles de expansión mínimos

3.2. Búsqueda en Profundidad. Búsqueda en anchura.

Definición 3.2.1. Dado un grafo G =(V, E), un árbol generador de G, es un subgrafo que es árbol y contiene a todos los vértices del grafo.

Ejemplo 3.2.2.

Proposición 3.2.3. Todo grafo conexo posee un árbol generador.

Proposición 3.2.4. El grafo completo Kn tiene árboles generadores diferentes).

 

Búsqueda en profundidad.

Muchos algoritmos de grafos necesitan visitar de un modo sistemático todos los vértices de un grafo. En la búsqueda en profundidad se avanza de vértice en vértice, marcando cada vértice visitado. La búsqueda siempre avanza hacia un vértice no marcado, internándose “profundamente” en el grafo sin repetir ningún vértice. Cuando se alcanza un vértice cuyos vecinos han sido marcados, se retrocede al anterior vértice visitado y  se avanza desde éste.

Si dado un grafo simple G, escogemos un vértice v para iniciar la exploración del grafo utilizando la búsqueda en profundidad, el árbol que se construye es un árbol generador de la componente conexa del grafo que contiene a v.

Sea G(V, E) un grafo conexo y v un vértice de V. El algoritmo de búsqueda en profundidad puede detallarse así:

1.      Se comienza en un vértice v (vértice activo) y se toma como la raíz del árbol generador T que se construirá. Se marca el vértice v.

2.      Se elige un vértice u, no marcado, entre los vecinos del vértice activo. Si no existe tal vértice, ir a 4.

3.      Se añade la arista (v, u) al árbol T.  Se marca el vértice u y se toma como activo. Ir al paso 2.

4.      Si se han alcanzado todos los vértices de G el algoritmo termina. En caso contrario, se toma  el vértice padre del vértice activo como nuevo vértice activo y se vuelve al paso 2.

La complejidad de este algoritmo es O(max{n, m})

 

Ejemplo 3.2.4. Hallar un árbol generador para el siguiente grafo aplicando el algoritmo de búsqueda en profundidad.

 

Si no se tuviera la certeza de que el grafo G es conexo, se necesita modificar el paso 4 para permitir la búsqueda en las componentes conexas que no contienen a v. Entonces este algoritmo servirá también para hallar todas las componentes conexas del grafo G, mediante la construcción de un árbol generador de cada componente conexa de G.

 

Ejemplo 3.2.5. Aplicar el algoritmo de búsqueda en profundidad al siguiente grafo.

La búsqueda en profundidad se puede implementar de forma recursiva. Debido al paso 4 del algoritmo descrito arriba, donde se regresa al padre del vértice activo, la búsqueda en profundidad es un algoritmo de retroceso o “backtracking”. Este tipo de algoritmo es de particular importancia en varios problemas de decisión, donde lo que se requiere es encontrar una solución o probar que no existe ninguna solución, por ejemplo, en el problema de la satisfacibilidad.

Sean X={x1, x2,…, xn} un conjunto de variables booleanas y C={C1,...,Cm} el conjunto de cláusulas que forma la fórmula cnf S.  El siguiente algoritmo de retroceso se puede utilizar para establecer si la fórmula S es satisfacible o no.   

PROCEDURE SAT(S)

BEGIN

       IF contradiccion THEN RETURN (falso);

       IF “todas las variables han sido evaluadas” THEN RETURN (verdadero)

       Sea x una variable no evaluada;

       S=reducir(S,x=1)

       RETURN  SAT(S)

       S=reducir(S,x=0)

       RETURN SAT(S)

END

Este algoritmo se ha implementado utilizando la función recursiva SAT. Aquí el procedimiento reducir devuelve la fórmula cnf reducida resultante de asignarle un valor a una de las variables de la formula original. Es un algoritmo de retroceso, pues retrocede al nivel anterior cuando se encuentra una contradicción. En este problema se produce un árbol de búsqueda binario. Cada vértice del árbol representa una fórmula obtenida al asignarle un valor a una variable presente en la fórmula que se encuentra en el nivel anterior, por tanto de cada vértice sólo pueden obtenerse dos hijos. Al asignarle valor a una nueva variable se avanza en profundidad. Al encontrar una contradicción se retrocede hasta llegar al nivel de una variable a la que solo se le ha asignado uno de sus dos valores posibles, asignándole el otro valor. Si en algún momento se logra asignarle valor a todas las variables sin que aparezca una contradicción el problema ha sido resuelto y la respuesta es satisfacible. Si se retorna al primer nivel para ambos valores de la primera variable, entonces la respuesta es no satisfacible. Debemos notar que en el caso peor, como tenemos n variables y cada una toma dos valores, el número de vértices del árbol binario será 2n y por tanto el algoritmo tendrá una complejidad exponencial.

Ejemplo 3.2.6. Aplicar el algoritmo anterior a las fórmulas cnf:

 

Búsqueda en anchura.

La búsqueda en anchura es otro procedimiento para visitar sistemáticamente todos los vértices de un grafo. Es adecuado especialmente para resolver problemas de optimización, en los que se deba elegir la mejor solución entre varias posibles. Al igual que en la búsqueda en profundidad se comienza en un vértice v (la raíz) que es el primer vértice activo. En el siguiente paso se etiquetan como visitados todos los vecinos del vértice activo que no han sido etiquetados. Se continúa etiquetando todos los vecinos de los hijos de v (que no hayan sido visitados aún). En este proceso nunca se visita un vértice dos veces por lo que se construye un grafo sin ciclos, que será un árbol generador de la componente conexa que contiene a v.

Sea G(V, E) un grafo conexo y v un vértice de V. El algoritmo de búsqueda en anchura puede detallarse así:

1.      Designamos a v como vértice activo y como raíz del árbol generador T que se construirá. Se le asigna a v la etiqueta 0.

2.      Sea i=0 y S={v}.

3.      Hallar el conjunto M de todos los vértices no etiquetados que son adyacentes a algún vértice de S.

4.      Si M es vacío el algoritmo termina. En caso contrario, se etiquetan todos los vértices de M con i+1, se añaden a T las aristas entre cada vértice de S  y su vecino en M y se hace S=M.

5.      i=i+1 y volver al paso 3.

Al terminar el proceso se habrá construido un árbol generador del grafo inicial. En caso de G no ser conexo, habría que modificar el algoritmo para encontrar un árbol generador de cada componente conexa de G. La complejidad de este algoritmo es O(max{n, m}).

Como podemos observar tanto el algoritmo de búsqueda en profundidad como el algoritmo de búsqueda en anchura pueden ser utilizados para verificar si un grafo simple es o no conexo. El problema de decisión consistente en determinar si un grafo simple es o no conexo, es entonces un problema de la clase P, pues hemos encontrado dos algoritmos de tiempo polinomial que resuelven este problema.

 

Enlaces de interés:

http://www.algoritmia.net/articles.php?id=18

 

DESCARGAR ESTE ARCHIVO EN PDF