Propiedades De Los Arboles

Tema 3.7.1

{++ Cambiar ++]

Arboles

Son un tipo especial de grafo.

G es un grafo, no digrafo sin bucles. G es un arbol si es conexo y no tiene ciclos.

Arboles degenerados: Arbol con un solo vertice y sin lados.

Arbol maximal: T es un arbol maximal de un grafo G conexo, si es un arbol y contiene todos los vertices de G.

Teorema 1: Si a y b son dos vertices distintos de un arbol, entonces existe un unico camino elemental que conecta dichos vertices.

Teorema 2: T es un arbol cualquiera, entonces |v|=|E|+1.

Teorema 3: T es un arbol con |v|”2, se verifica que tiene almenos dos vertices terminales.