Arboles (matematicas discretas)
Enviado por Programa Chuletas y clasificado en Matemáticas
Escrito el en 
español con un tamaño de 3,51 KB
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.
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.
Podemos destacar que cuando un grafo G es un Arbol, se reemplaza G, por R.
En la figura mostrada G1 es un subgrafo de G2, en el que G1 contiene los vértices de G2 y es árbol, además lo llamaremos árbol abarcador, por que proporciona conexión minimal para el grafo y un esqueleto minimal que une los vértices.
Ejemplo de árbol raíz:
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.
V(n-1) es el padre de v(n).
V0, v1, ..., v(n-1) son los antepasados de v(n).
V(n) es el hijo de v(n-1).
Si x es un antepasado de y, entonces y es un descendiente de x.
Si x e y son hijos de z entonces x e y son hermanos.
Si x no tiene hijos entonces x es un vértice terminal.
Si x no es un vértice terminal, entonces x es un vértice interno.
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
Un árbol binario es uno con raíz en el cual cada vértice tiene un hijo a la derecha o un hijo a la izquierda, o viceversa, o bien ningún hijo. Un árbol binario completo es uno en el cual cada vértice tiene un hijo a la derecha y uno a la izquierda, o bien ningún hijo
.Arboles generadores:
Un árbol T es un árbol generador de un grafo G si T es un subgrafo de G que contiene todos los vértices de G.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es así como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
En general un grafo G tendrá varios árboles generadores ,como el del ejemplo 1 el cual tiene a lo menos dos arboles generadores T1 yT2.
Ej.
Algoritmos para hallar un árbol generador , que se base en el teorema de que el grafo G debe ser conexo, pueden ser los que se realizan a través de los métodos llamados buscar primero a lo ancho , buscar primero a lo largo y el de regreso al nivel anterior.
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.
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.
Podemos destacar que cuando un grafo G es un Arbol, se reemplaza G, por R.
En la figura mostrada G1 es un subgrafo de G2, en el que G1 contiene los vértices de G2 y es árbol, además lo llamaremos árbol abarcador, por que proporciona conexión minimal para el grafo y un esqueleto minimal que une los vértices.
Ejemplo de árbol raíz:
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.
V(n-1) es el padre de v(n).
V0, v1, ..., v(n-1) son los antepasados de v(n).
V(n) es el hijo de v(n-1).
Si x es un antepasado de y, entonces y es un descendiente de x.
Si x e y son hijos de z entonces x e y son hermanos.
Si x no tiene hijos entonces x es un vértice terminal.
Si x no es un vértice terminal, entonces x es un vértice interno.
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
Un árbol binario es uno con raíz en el cual cada vértice tiene un hijo a la derecha o un hijo a la izquierda, o viceversa, o bien ningún hijo. Un árbol binario completo es uno en el cual cada vértice tiene un hijo a la derecha y uno a la izquierda, o bien ningún hijo
.Arboles generadores:
Un árbol T es un árbol generador de un grafo G si T es un subgrafo de G que contiene todos los vértices de G.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es así como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
En general un grafo G tendrá varios árboles generadores ,como el del ejemplo 1 el cual tiene a lo menos dos arboles generadores T1 yT2.
Ej.
Algoritmos para hallar un árbol generador , que se base en el teorema de que el grafo G debe ser conexo, pueden ser los que se realizan a través de los métodos llamados buscar primero a lo ancho , buscar primero a lo largo y el de regreso al nivel anterior.