Arboles

-------------------------------------------------
Árbol (teoría de grafos).
Árbol |

Árbol etiquetado con 6 vértices y 5 aristas. El único camino simple que conecta los vértices 2 y 6 es2-4-5-6. |
Vértices | v |
Aristas | v-1 |
Número cromático | 2 si v > 1 |
Propiedades | Bipartito, expandible y plano (si el conjunto de vértices en numerable) |
En teoría de grafos, un árbol esun grafo en el que cualesquiera dos vértices están conectados por exactamente un camino. Un bosque es una unión disjunta de árboles. Un árbol a veces recibe el nombre de árbol libre.-------------------------------------------------
Definiciones
Un árbol es un grafo simple unidireccional G que satisface alguna de las siguientes condiciones equivalentes:
* G es conexo y notiene ciclos simples.
* G no tiene ciclos simples y, si se añade alguna arista se forma un ciclo simple.
* G es conexo y si se le quita alguna arista deja de ser conexo.
* G es conexo y el grafo completo de3 vértices K3 no es un menor de G.
* Dos vértices cualquiera de G están conectados por un único camino simple.
Si G tiene muchos vértices, n, entonces las definiciones anteriores son tambiénequivalentes a cualquiera de las siguientes condiciones:
* G es conexo y tiene n − 1 aristas.
* G no tiene aristas simples y tiene n − 1 aristas.
* La cantidad de hojas de un árbol siempre esmayor o igual a la mitad de la totalidad de los nodos.

Un grafo unidireccional simple G es un bosque si no tiene ciclos simples.
Un árbol dirigido es un grafo dirigido que sería un árbol si no seconsideraran las direcciones de las aristas. Algunos autores restringen la frase al caso en el que todos las aristas se dirigen a un vértice particular, o todas sus direcciones parten de un vérticeparticular.
Un árbol recibe el nombre de árbol con raíz si cada vértice ha sido designado raíz, en cuyo caso las aristas tienen una orientación natural hacia o desde la raíz. Los árboles con raíz,...