Materia: #técnicas_y_diseños_de_algoritmos

Tags: Estructura, Grafos, Arboles binarios

Arboles

Llamamos árbol a un grafo conexco sin circuitos simples.

Una arista $e$ de un árbol $G$ es puente si $G-e$ tiene más componentes conexas que $G$. Por otro lado, un vértice $v$ de $G$ es un punto de corte o punto de articulación si $G-v$ tiene más componentes conexas que $G$.

También podría definirse un árbol, teniendo un grafo $G=(V,X)$ como:

• $G$ es un grafo sin circuitos simples, pero si se agrega una arista $e$ a $G$ resulta un grafo con exactamente un circuito simple, y ese circuito contiene a $e$.

• Existe exactamente un camino entre todo par de nodos.

• $G$ es conexo, pero si se quita cualquier arista a $G$ queda un grafo no conexo (es decir, toda arista es puente).

• $G$ es un grafo sin circuitos simples y $m=n-1$.

• $G$ es conexo y $m=n-1$

Llamamos hoja a los nodos de grado 1. Todo árbol no trivial tiene al menos dos hojas.

flowchart TD

name(Es un árbol)

id1(( ))
id2(( ))
id3(( ))
id4(( ))
id5(( ))
id6(( ))
id7(( ))
id8(( ))

id1 --- id2
id1 --- id3
id3 --- id4
id3 --- id5
id2 --- id6
id2 --- id7
id2 --- id8

flowchart LR

name(No es un árbol)

id1(( ))
id2(( ))
id3(( ))

id1 --- id2
id2 --- id3
id3 --- id1

Arboles enraizados

Un árbol enraizado es un árbol que tiene un vértice distinguido que llamamos raíz. Explícitamente queda definido un dígrafo.

El nivel de un vértice es la distancia de la raíz a ese vértice. La altura $h$ de un árbol es el máximo nivel de sus vértices. Los vértices internos de un árbol enraizado son aquellos que no son ni hojas ni la raíz.

Un árbol enraizado se dice $m-ario$ si todos sus vértices internos tienen grado a lo sumo $m+1$ y su raíz a lo sumo $m$. Un árbol enraizado pasa a ser exactamente $m-ario$ si todos sus vértices internos tienen grado $m+1$ y su raíz $m$.

flowchart TD

name(Árbol enraizado binario completo)

id1((R))
id2(( ))
id3(( ))
id4(( ))
id5(( ))
id6(( ))
id7(( ))

id1 --- id2
id1 --- id3
id3 --- id4
id3 --- id5
id2 --- id6
id2 --- id7

En el dibujo se ve un árbol enraizado binario (donde la raíz seria el nodo $R$) de altura 2.

Un árbol se dice balanceado si todas sus hojas están a nivel $h$ o $h-1$. A su vez, llamamos balanceado completo a los arboles en que todas sus hojas están a nivel $h$. El dibujo de antes, representa un árbol balanceado.

Decimos que dos vértices adyacentes tienen relación padre-hijo, siendo el padre el vértice de menor nivel.

Arboles generadores

Un árbol generador $AG$ de un grafo $G$ es un subgrafo generador (que tiene el mismo conjunto de vértices) de $G$ que es un árbol. Todo grafo conexo tiene (al menos) un árbol generador.

flowchart TD

name(Grafo)

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))

id1 --- id2
id1 --- id3
id3 --- id4
id3 --- id5
id2 --- id3
id1 --- id5

id6((1))
id7((2))
id8((3))
id9((4))
id0((5))

id6 --- id7
id6 --- id8
id8 --- id9
id8 --- id0

tree(Arbol generador)