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.
Cualesquiera
2 vértices están unidos por una única trayectoria
No hay comentarios:
Publicar un comentario