Введение
В математике, и в частности в теории графов, корневой граф — это граф, в котором одна вершина выделена как корень. И направленные, и ненаправленные варианты корневых графов изучались, а также существуют различные определения, допускающие несколько корней. Корневые графы также могут называться (в зависимости от области применения) ориентированными графами или графами потоков. В некоторых применениях этих графов предъявляется дополнительное требование, чтобы из корневой вершины можно было достичь любой другой вершины графа.
Вариации
В топологической теории графов понятие коренистого графа может быть расширено для рассмотрения нескольких вершин или нескольких ребер в качестве корней. Первые иногда называют графами с вершинными корнями, чтобы отличать их от графов с реберными корнями в данном контексте. Графы с несколькими узлами, обозначенными как корни, также представляют интерес в комбинаторике, в частности, в области случайных графов. Эти графы также называют многократно коренистыми графами. Термины "укорененный ориентированный граф" или "укорененный диграф" также имеют различные трактовки. Естественным расширением является рассмотрение диграфа, укорененного путем обозначения конкретного узла как корня. Однако в информатике эти термины обычно относятся к более узкому понятию: укорененный ориентированный граф – это диграф с выделенным узлом r, таким, что существует ориентированный путь из r в любой другой узел. Авторы, использующие более общее определение, могут называть графы, удовлетворяющие более узкому определению, связными укорененными диграфами.
Графики потоков
В информатике, коренистые графы, в которых корневая вершина может достигать всех остальных вершин, называются графами потока или потоковыми графами. Иногда добавляется дополнительное ограничение, требующее, чтобы граф потока имел единственную выходную (стоковую) вершину. Графы потока можно рассматривать как абстракции блок-схем, с удалением неструктурных элементов (содержимого и типов узлов). Вероятно, наиболее известным подклассом графов потока являются графы управления потоком, используемые в компиляторах и анализе программ. Произвольный граф потока может быть преобразован в граф управления потоком путем сжатия ребер для каждого ребра, являющегося единственным исходящим ребром из его источника и единственным входящим ребром в его цель. Другим часто используемым типом графа потока является граф вызовов, в котором узлы соответствуют целым подпрограммам. Однако этот же термин также использовался для обозначения только графов управления потоком. Графы потока также называют немаркированными графами потока и собственно графами потока. Если требуется наличие единственного выхода, графы потока обладают двумя свойствами, не свойственными общим ориентированным графам: графы потока могут быть вложены, что эквивалентно вызову подпрограммы (хотя понятие передачи параметров отсутствует), и графы потока могут быть секвенированы, что эквивалентно последовательному выполнению двух фрагментов кода. Простые графы потока определяются как графы потока, которые нельзя разложить посредством вложения или секвенирования, используя выбранный шаблон подграфов, например, примитивы структурированного программирования. Теоретически изучались вопросы определения, например, доли простых графов потока при заданном наборе графов.
Теория множеств
Питер Ацзель использовал корневые ориентированные графы, в которых каждая вершина достижима из корня (которые он называет доступными ориентированными графами), чтобы сформулировать аксиому антифундамента Ацзеля в нехорошо обоснованной теории множеств. В этом контексте каждая вершина доступного ориентированного графа моделирует (нехорошо обоснованное) множество в теории множеств Ацзеля (нехорошо обоснованной), а дуга от вершины v к вершине w моделирует, что v является элементом w. Аксиома антифундамента Ацзеля утверждает, что каждый доступный ориентированный граф моделирует семейство (нехорошо обоснованных) множеств таким образом.
Комбинаторная теория игр
Любую комбинаторную игру можно представить в виде ориентированного дерева, вершины которого соответствуют позициям в игре, рёбра — возможным ходам, а корень — начальной позиции игры. Этот граф играет важную роль в изучении сложности игры, где сложность пространства состояний определяется количеством вершин в этом графе.
Комбинационное перечисление
Количество корневых неориентированных графов для 1, 2, 3, 4, 5, 6 узлов равно 1, 2, 6, 20, 90, 544.
Связанные понятия
Особый интерес представляют корневые деревья, деревья с выделенной корневой вершиной. Если направленные пути от корня в укорененном ориентированном графе дополнительно ограничены условием единственности, то полученное понятие называется (укорененным) арборесценцией — ориентированным графом, эквивалентным укорененному дереву. Укорененные графы могут быть объединены посредством укорененного произведения графов.