6.4. ARBOLES
En teoría de grafos, un árbol es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino. 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 no tiene ciclos.
• G no tiene ciclos y, si se añade alguna arista se forma un ciclo.
• G es conexo y si se le quita alguna arista deja de ser conexo.
• G es conexo y el grafo completo de 3 vértices no es un menor de G.
• Dos vértices cual quiera de G están conectados por un único camino simple.
Si G tiene muchos vértices, n, entonces las definiciones anteriores son también equivalentes a cualquiera de las siguientes condiciones:
• G es conexo y tiene n - 1 aristas.
• G es conexo y sin ciclos.