Árboles y Conjuntos De Corte

Árboles y Conjuntos De Corte
Arboles
Definición:
Un árbol es un grafo no dirigido conexo que no contiene circuitos
Ejemplos:




Definición:
Una Colección de árboles disjuntos se llamabosque. Un vértice de Grado 1 en un árbol se le llama hoja o nodo terminal y un vértice de grado mayor que 1 recibe el nombre de nodo rama o nodo interno.
Ejemplo:
En el árbol i)
B, c, d, f, g, i, sonnodos hoja
A, e, h, son nodos rama.
Existen algunas propiedades que señalaremos con relación a los arboles.
1) Existen un único paseo entre dos vértices cualesquiera en un árbol.
2) El número devértices es mayor que el numero de aristas en un árbol.
3) Un árbol con dos o mas vértices tiene al menos una hoja.
Existen además otros resultados sobre la caracterización de arboles.
1) Un grafoen el cual existe un único paseo entre cada par de vértices es un arbol.
2) Un grafo con e=v-1 que no tiene circuitos es un arbol.
3) Un grafo conexo con e=v-1 es un arbol.



ARBOLES CONTERMINAL (ENRAIZADOS
Definicion:
Diremos que un grafo dirigido es un arbol dirigido si se convierte en un arbol cuando se ignoran las direcciones de sus aristas.
Ejemplo:






Definicion:
Unarbol dirigido es un arbol enraizado si existe exactamente un vértice cuyo grado de entrada sea 0 y los grados de entrada de los otros vértices sea 1.- El vértice con grado de entrada 0 es llamadoraíz del arbol enraizado.
Ejemplo:











Definicion:
En un arbol enraizado, un vértice cuyo grado de salida sea 0 se llama nodo hoja o nodo terminal , y un vértice cuyo grado desalidas sea diferentes de 0 se llama nodo rama o nodo interno.
Ejemplo:
Sea el sgte arbol dirigido












Entonces:
Los nodos a,b,c,f,,h son nodos rama y los nodos d,e,g,i,j,k,l sonnodos hojas.

Definicion:
Sea a un nodo de rama en un arbol enraizado .- Diremos que un vértice b es un hijo de a si existe una arista de “a” a “b”.- Ademas se dice que el vértice “a”...