Arboles 3

Arboles:
Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices.
Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos.
Arbolesy bosques:
Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos. Como ejemplo tenemos la siguiente figura.
Arboles con raíz:
Sea G un grafo dirigido, sedenomina “árbol dirigido” si el grafo no dirigido asociado con G es un árbol. Cuando G es un árbol dirigido, se denomina “árbol con raíz” si hay un único vértice r, la raíz.

Subárboles:
Son laramificacion de un arbol, o ,en otro termino,una parte desglozada del mismo.
Busqueda en profundidad:
La idea basica de la busqueda en profundidad es penetrar tan profundamente
como sea posible dentro de unarbol antes de desplegarse a otros
vertices. Esto se consigue al tomar el nuevo vertice adyacente al ultimo de
los posibles vertices anteriores.
Algoritmo DFS:
Entradaun grafo G y un vertice v de G,
Salida Un arbol generador de la componente conexa de v.
Iniciar L := {v}, W := {v}, B :=∅;
FinalSi
Final
Mientras
Escribir (W, B)
Busqueda en anchura:
La idea basica de la busqueda en anchura es desplegarse a tantos vertices
como sea posible antes de penetrar en profundidad dentro de unarbol. Esto
significa que visitaremos todos los vertices adyacentes a uno dado antes de
cambiar de nivel.
Algoritmo BFS:
Entrada un grafo G y un v´ertice v de G,
Salida Un arbol generador de lacomponente conexa de v.
Inciar L := {v}, W := {v}, B := ∅;
Final:Si
Final:Mientras
Escribir (W, B)
Notemos que un vertice no se elimina del conjunto L hasta que no se han
incorporado todos sus verticesadyacentes.
Recorrido de preorden:
Para recorrer un arbol binario no vacio en preorden, hay que realizar las siguientes opera- ciones recursivamente en cada nodo, comenzando con el nodo de raiz:
1.Visite...