arboles y redes

Mere som dette

Operaciones básicas en viveros

af Maria del Pilar

Algoritmos y Estructura de Datos II

af Barker Malimba

ECUACIONES DIFERENCIALES ORDINARIAS LINEALES DE PRIMER ORDEN Y GRADO

af Daniel David Meza

Convención contra la Tortura y Otros Tratos o Penas Crueles, Inhumanos o Degradantes

af RUTH ROXANA NUÑEZ MONGE

arboles y redes

Teorema: Si T es un árbol binario completo con i vértices internos, entonces T tiene i + 1 vértices terminales y 2i + 1 vértices en total. Un árbol binario de búsqueda es un árbol binario T donde se han asociado datos a los vértices. Los datos se disponen de manera que para cualquier vértice v en T, cada dato en el subarbol a la izquierda de v es menor que el dato correspondiente a v.

Arboles con Raíz Sea G un grafo dirigido, se denomina “á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. Sea G un grafo con raíz V0. Supóngase que x, y, z son vértices en G y que (v0, v1, ..., vn), es un camino en G.

El subgrafo de G que consiste en x y todos sus descendientes, con x como raíz, es el subarbol de G que tiene a x como raíz.

Si x es un antepasado de y, entonces y es un descendiente de x.

V(n) es el hijo de v(n-1).

V0, v1, ..., v(n-1) son los antepasados de v(n).

V(n-1) es el padre de v(n).

Teorema: Sea G un grafo simple con v vértices, entonces se puede decir: G es un árbol. G es conexo y no contiene circuitos. G es conexo y tiene (n-1) lados. G no contiene circuitos y tiene (n-1) lados.

Teorema: En cualquier árbol R= (V,A), |V| = |A| + 1. Teorema: Para cualquier árbol R = (V,A), si |A| >= 2, entonces R tiene al menos dos vértices colgantes.

Ejemplo de árbol raíz: Para apoyar el entendimiento de las definiciones entregadas agregaremos algunos teoremas.

Teorema: Si a, b son vértices de un árbol R (V,A), entonces hay un camino único que conecta estos vértices.

Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz. Ejemplo de árbol: En la figura anterior G1 corresponde a lo que llamamos mediante la definición ARBOL, en el caso de G2, éste no corresponde debido a que contiene un ciclo.

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.