Matemáticas discretas. Árboles

Matemática discreta. Árbol. Grafo conexo. Ciclos. Vértices. Raíz. Camino único. Hijos, subgrafos. Recorrido. Generadores minimales. Minimal

  • Enviado por: Alchemist
  • Idioma: castellano
  • País: Chile Chile
  • 7 páginas
publicidad
cursos destacados
Curso Superior en Dirección y Gestión de Proyectos
Universidad de Salamanca, Fundación General
- Elaboración de un Proyecto Real a través de las diferentes etapas de inicio y planificación mediante Plantillas y...
Solicita InformaciÓn

Master en Facility Management (Chile)
Structuralia
El Facility Management (gestión y mantenimiento de activos inmobiliarios) es una de las disciplinas de mayor...
Solicita InformaciÓn

publicidad

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:

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.

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.

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.

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.

Sea R= (V,A) un árbol con raíz r. Si R no tiene otros vértices, entonces la raíz misma constituye el recorrido en orden previo, simétrico y posterior de R. Si |V| > 1, sean R1, R2, R3, ...., Rk los subarboles de R según se va de izquierda a derecha.

  • El recorrido de orden previo de R comienza en r y después pasa por los vértices de R1 en orden previo, a continuación por los vértices de R2 en orden previo, y así sucesivamente hasta que se pasa por los vértices de Rk en orden previo.

  • El recorrido en orden simétrico de R primero, se pasa por los vértices de R1 en orden simétrico, después por la raíz r y a continuación por los vértices de los subarboles R2, R3,...., Rk en orden simétrico.

  • El recorrido en orden posterior de R pasa por los vértices de los subarboles R1, R2,...., Rk en orden posterior y a continuación por la 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.

    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 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.

    Vídeos relacionados