Часть 1: Древовидность (общее определение) в этой статье могут быть неточности или упрощения 1.1. Интуитивное представление: корень. Затем сориентируйте все ребра так, чтобы они смотрели наружу от корня, т. е. в направлении от корня...
Часть 1: Древовидность (общее определение)
в этой статье могут быть неточности или упрощения
1.1. Интуитивное представление:
Представьте себе обычное неориентированное дерево. Теперь назначим особую роль одной из его вершин — корню. Затем сориентируйте все края так, чтобы они были направлены наружу от корня, т. е. по направлению от корня к листьям. Полученная структура представляет собой древовидную структуру.
Простой пример — структура папок компьютера ⬇️
Корень — C:\ (или / в Linux)
Все папки создаются через «Новую папку»; нет ярлыков или ссылок.
У каждой папки есть ровно один «родитель» (папка, в которой она находится).
Подойти можно только к родителю. Это классическое дерево (древесность).
DAG с потенциальным древовидением (реальная система с mklink или .lnk):
Допустим, есть структура:
C:\Проекты\
├── СекретныеДанные\
└── CurrentProject\ <-- содержит ярлык «Данные» → C:\Projects\SecretData
Теперь это ДАГ, а не древовидение, потому что:
SecretData имеет двух «родителей»:
Прямой: C:\Projects\
Через ярлык: C:\Projects\CurrentProject\Data\
Условие ingrade = 1 для древовидности нарушено.
Но циклов нет — это DAG.
«Древовидность (DAG)» в этой аналогии:
Если это