¿Es un árbol con nodos que tienen referencia a padre todavía un árbol?

8

Si hacemos referencia al padre para cada nodo en un árbol, ¿todavía tenemos un árbol (por definición)?

La definición de Wikipedia es:

En informática, un árbol es un tipo de datos abstractos (ADT) o estructura de datos ampliamente utilizado que implementa este ADT que simula una estructura de árbol jerárquica, con un valor raíz y subárboles de niños, representados como un conjunto de nodos vinculados.

ingrese la descripción de la imagen aquí

data-structures trees Mohsen
fuente
3
¿Qué te hace dudarlo?
2
Mientras los padres enlaces y los niños enlaces son distintos, se puede asumir que los niños enlaces hacen que el árbol y los padres enlaces son sólo un detalle de implementación.
Mouviciel

Respuestas:

16

Un árbol es un gráfico acíclico conectado. En el caso de que tengamos enlaces "primarios", esto sería un árbol no dirigido, pero definitivamente un árbol. Si tuviera que especificar que el ejemplo es un gráfico dirigido, no se consideraría un árbol (pero, por supuesto, no hay forma de distinguir el código que se pretendía).

Algunos "árboles" de informática incluirán, por ejemplo, enlaces desde cada nodo de regreso a la raíz, o enlaces a lo largo de cada nivel de un árbol B +. Un informático probablemente todavía llamaría a estas cosas árboles, un matemático no.

U2EF1
fuente
1
+1 para señalar que tener enlaces primarios (enlaces en ambas direcciones) hace que el gráfico sea equivalente a un gráfico no dirigido.
Giorgio el
¿Podemos decir que cualquier gráfico acíclico es un árbol?
Mohsen
44
@Mohsen Un gráfico acíclico (dirigido) que incluye un nodo con dos padres no es un árbol
Izkata
@Mohsen: También puede definir un árbol como un gráfico con un nodo raíz distinto de modo que exista una ruta única desde la raíz a cualquier otro nodo. Claramente, hay gráficos acíclicos que no cumplen con esta definición.
Giorgio
-2

Sigamos esta definición. Seguramente obtendrá los ans.

Un gráfico conectado G se llama árbol si la eliminación de cualquiera de sus bordes hace que G se desconecte. Entonces, como el gráfico dado anteriormente, no admite esta declaración, por lo que no podemos decir que el gráfico dado es un árbol.

Para más información puedes continuar este enlace.

http://win.ua.ac.be/~vanhoudt/graph/trees.pdf

inmersión
fuente
1
Estás utilizando el punto de vista del matemático aquí. Tenga en cuenta que U2EF1 dice en su respuesta: un informático probablemente todavía llamaría a estas cosas árboles, un matemático no lo haría. . Su respuesta es básicamente la misma que la de Uiquité a este respecto.
Martijn Pieters
El artículo citado supone gráficos no dirigidos. Esta definición de árboles no es apropiada para un gráfico dirigido, porque (a) tendría que mencionar que los DAG que incluyen árboles pueden estar débilmente conectados, y porque (b) permite múltiples nodos raíz. Ahora observe que el gráfico en la pregunta es un gráfico dirigido (aunque con vínculos de retroceso), y que todavía hay un concepto de nodo raíz (la jerarquía se denota por posición vertical). Una mejor definición para un árbol dirigido sería: "Un árbol (dirigido) está vacío o tiene exactamente un nodo raíz desde el cual se puede acceder a todos los nodos".
amon