Странное обобщение деревьев?

Question

При работе с ориентированными графами дерево - это граф, в котором каждый узел, кроме одного (корня), имеет один входящий фронт? Существуют ли примеры древовидных структур, в которых каждый узел имеет не более некоторого постоянного числа входящих ребер; скажем, максимум два или максимум три? Я не встречал никаких графиков, специально описанных таким образом; Есть ли конкретное приложение, в котором они используются?

Answer 1

Наиболее распространенным обобщением дерева является «DAG» (направленный ациклический граф), который имеет тангенциальную связь, но не устанавливает максимальный размер соседних окрестностей (дуг, ведущих в вершину) и спецификацию одногоsource (вершины с пустыми соседями).

Из того, что я знаю, нет точного термина для того, что вы ищете.Вам нужно будет найти настоящего математика с глубоким интересом к теории графов, чтобы знать с уверенностью!

Answer 2

Решетки ( частично упорядоченные множества ) обладают этим свойством.

Answer 3

В теории графов дерево является связным ациклическим графом.Не требуется, чтобы у каждого узла был один входящий фронт.В области компьютерных наук мы часто имеем дело с корневыми деревьями, которые согласуются с вашим определением.

Вот одно описание дерева, в котором некоторые узлы имеют постоянное число входящих ребер: назначение проектов сотрудникам, гдекаждому сотруднику может быть назначено не более трех проектов.