Терминология: недревесный граф?

Question

Я новичок в структурах данных и задал вопрос о терминологии. Есть ли термин для недревесных графов?

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

P.s .: Пожалуйста, не стесняйтесь взломать любой народный язык выше. Будут ли любить советы по соответствующей терминологии в целом в отношении структур данных.

Answer 1

Я не думаю, что существует единый универсальный термин для недревесного графа (кроме, пожалуй, самого «недревесного графа»).

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

Древовидный граф, который не полностью подключен, можно охарактеризовать как «лес». Лес имеет несколько корневых узлов, каждый из которых привязывает разделяемое поддерево.

Если у вас есть граф с несколькими корневыми узлами, но их потомки перекрываются (так что данный дочерний узел может иметь более одного родительского узла), у вас есть «multitree». Человеческое родословное дерево может быть многогранным, если между братьями или другими родственниками нет браков.

Следующим более общим термином является, вероятно, «directed acyclic graph» или «ДАГ». DAG является более общей, чем многопользовательская, поскольку узел-предка может быть связан с потомком узлом более чем на одном пути. Человеческие генеалогические деревья более правильны, хотя и в качестве DAG, поскольку достаточно дальним родственникам вообще разрешено выходить замуж и иметь детей (но никто не может быть их собственным предком). Существует множество алгоритмов, предназначенных для работы с DAG, поскольку запрещающие циклы обеспечивают лучшую производительность для многих полезных приложений (таких как поиск путей).

Еще более общий «directed graph» или «орграф», который расслабляет циклы ограничений. Общая структура данных орграфа - это список смежности (список дуг от одного узла к другому).

Я не думаю, что существует более общий термин помимо этого, кроме как только «график». Если у вас есть конкретное приложение для графа, может существовать специальный термин для типа графика, который вы будете использовать (и, возможно, алгоритмы или даже код библиотеки, чтобы идти вместе с ним), но вам нужно будет спросить об этом конкретно.