OIA-Wiki

Grafos

Siempre que hablemos de árboles vamos a estar hablando en grafos conexos. Para que un grafo sea un árbol necesita ser conexo, entonces lo daremos por sentado.

Un árbol es un tipo de grafo particular. Una de las particularidades que tiene es que no tiene ciclos. Las siguientes características son equivalente, es decir, si un grafo (conexo) cumple una, cumple las demás:

• $E=V-1$ (la cantidad de aristas es uno menos que la cantidad de nodos)
• No tiene ciclos
• Al agregar una arista entre dos nodos no adyacentes, aparece un ciclo
• Al sacar cualquier arista existente, el grafo se desconecta
• Para cada par de nodos existe un único camino simple (que no repite vértices)

Dejo un grafo de este tipo para tener en la cabeza al seguir leyendo:

Algo interesante que podemos hacer en todos los árboles es establecer un nodo raíz. Si establecemos un nodo como raíz, por ejemplo si elegimos como raíz al nodo $1$ ó $2$ en el árbol de recién, convendría (y se suele) dibujarlos así respectivamente:

Es decir, se ubica la raíz arriba de todo, y luego los nodos se dibujan más abajo, en la medida en que están más lejos de la raíz.

Para un árbol con raíz, tienen sentido las siguiente definiciones:

Altura o Profundidad de un nodo: Es la longitud del camino entre el nodo y la raíz. En el árbol de raíz $1$, las profundidades de los nodos $1$, $5$, $3$ son $0$, $1$, $2$ respectivamente.

Hojas: Son los nodos desde los cuales es imposible ir a otro nodo más alejado de la raíz sin “subir” (acercarnos a la raíz). En el árbol de raíz $1$, las hojas son los nodos $3$, $4$ y $6$.

Padre de un nodo: Es el nodo que está inmediatamente arriba de él, es decir que es adyacente al nodo, y está en el camino entre el nodo y la raíz. La raíz no tiene padre. En el árbol de raíz $1$, el padre de $6$ es $5$ y el de $5$ es $1$.

Hijos de un nodo: Son los nodos adyacentes a él que tienen altura mayor a él. Las hojas no tienen hijos. En el árbol de raíz $1$, el único de $2$ es $3$, y los hijos de $1$ son $2$, $5$ y $4$.

Subárbol de un nodo dado: Es el árbol que queda formado por el nodo dado, sus hijos, los hijos de sus hijos, y así siguiendo hasta considerar todos los nodos posibles. La raíz del subárbol es el nodo dado. El subárbol de una hoja es simplemente ese mismo nodo. En el árbol de raíz $1$, el subárbol del nodo $5$ son sólo los nodos $5$ y $6$ con la arista que los une.

Desdenciente de un nodo $x$: es un nodo $y$ que forma parte del subárbol de $x$. A veces se suele considerar a un nodo descendiente de sí mismo.

Ancestro de un nodo $x$: es un nodo $y$ tal que $x$ es descendiente de $y$. A veces se suele considerar a un nodo ancestro de sí mismo.

Ancestro común de un conjunto de nodos: Es un nodo que es ancestro de todos los nodos dados. Es decir, todos los nodos del conjunto forman parte del subárbol del nodo que llamamos ancestro común. La raíz es siempre un ancestro común de cualquier conjunto de nodos. En general es interesante conocer el ancestro común más bajo de dos nodos, que se obtiene tomando, de todos los ancestros comunes, aquel que sea el “más bajo”, o sea el que está a mayor profundidad.

Bueno, una manera de recorrerlo es simplemente con BFS o DFS, marcando los visitados y todo igual a como hacíamos antes, ya que eso funciona para cualquier grafo.

Otra manera de recorrerlo es desde la raíz hacia abajo, con una función recursiva que se mueva a todos los vecinos del nodo excepto a su padre, que será un parámetro de la función. Entonces el código quedaría:

void recorrer(int nodo, int padre){
    for(int i=0; i<grafo[nodo].size(); i++){
        if(grafo[nodo][i]!=padre){
            // Codigo aca o despues de llamar a la funcion, que haga algo
            recorrer(grafo[nodo][i], nodo); // Ahora el padre del nodo al que vamos es el nodo actual
        }
    }
}
 
// Para empezar en la raíz sin que se evite ningún nodo, es común hacer:
recorrer(raiz, -1);