Войти
В математике и, в частности, в теории графов, a корневой граф - это граф, в котором одна вершина была выделена как корневая. И направленный, и неориентированный версии корневых графов были изучены, а также существуют варианты определения, допускающие множественные корни.
Корневые графы могут также называться (в зависимости от их применения) как точечные графы или потоковые графы . В некоторых приложениях этих графов существует дополнительное требование, чтобы весь граф был доступен из корневой вершины.
В теории топологических графов понятие корневого графа может быть расширено для рассмотрения несколько вершин или несколько ребер в качестве корней. Первые иногда называют графами с вершинным корнем, чтобы отличать их от графов с реберным корнем в этом контексте. Графы с несколькими узлами, обозначенными как корни, также представляют определенный интерес в комбинаторике в области случайных графов. Эти графы также называются многокорневыми графами .
Термины корневой ориентированный граф или корневой орграф также видят различия в определениях. Очевидная трансплантация состоит в том, чтобы рассматривать орграф с корнем, идентифицируя определенный узел как корневой. Однако в информатике эти термины обычно относятся к более узкому понятию, а именно, ориентированный ориентированный граф - это орграф с выделенным узлом r, так что существует направленный путь от r к любому узлу, отличному от r.. Авторы, которые дают более общее определение, могут называть их связными (или односвязными) корневыми орграфами.
Искусство компьютерного программирования определяет корневые орграфы несколько шире, а именно ориентированный граф называется корневым, если он имеет хотя бы один узел, который может достичь всех остальных узлов; Кнут отмечает, что определенное таким образом понятие является своего рода промежуточным звеном между понятиями сильно связанного и связного орграфа.
In информатика, корневые графы, в которых корневая вершина может достигать всех остальных вершин, называются потоковыми графами или потоковыми графами . Иногда добавляется дополнительное ограничение, указывающее, что потоковый граф также должен иметь единственную вершину выхода (приемник ).
Поточные графы можно рассматривать как абстракции из блок-схемы с удалением неструктурных элементов (содержимого и типов узлов). Возможно, наиболее известным подклассом потоковых графов являются графы потоков управления, используемые в компиляторах и программном анализе. Произвольный потоковый граф может быть преобразован в потоковый граф управления путем выполнения сокращения ребер на каждом ребре, которое является единственным исходящим ребром от его источника и единственным входящим ребром в его цель. Другой тип обычно используемого потокового графа - это граф вызовов, в котором узлы соответствуют целым подпрограммам.
Общее понятие потокового графа было названо программным графом, но тот же термин также использовался для обозначения только графов потока управления. Поточные графы также называются немаркированными потоковыми графами и собственными потоковыми графами . Эти графы иногда используются в тестировании программного обеспечения..
Когда требуется иметь один выход, потоковые графы имеют два свойства, которые не используются совместно с ориентированными графами в целом. Потоковые графы могут быть вложенными, что эквивалентно вызову подпрограммы (хотя здесь нет понятия передачи параметров), а потоковые графы также могут быть последовательными, что эквивалентно последовательному выполнению двух частей кода. Простые потоковые графы определяются как потоковые графы, которые не могут быть разложены посредством вложенности или последовательности с использованием выбранного шаблона подграфов, например примитивов структурного программирования. Теоретические исследования были проведены по определению, например, доли потоковых графов простых чисел для выбранного набора графов.
Питер Акзель использовал ориентированные корневые графы, так что каждый узел достижимые из корня (который он называет доступными точечными графами ), чтобы сформулировать аксиому против основания Акзеля в недостаточно обоснованной теории множеств. В этом контексте каждая вершина доступного точечного графа моделирует (не обоснованное) множество в рамках теории множеств неосновательности Акзеля, а дуга от вершины v к вершине w моделирует, что v является элементом w. Антиосновная аксиома Акзеля гласит, что каждый доступный точечный граф моделирует семейство (недостаточно обоснованных) множеств таким образом.
Учитывая чисто комбинаторная игра, существует связанный ориентированный ориентированный граф, вершинами которого являются игровые позиции, а ребра - ходы, а обход графа, начиная с корня, используется для создать дерево игры. Если граф содержит направленных циклов, то позиция в игре может повторяться бесконечно много раз, и обычно необходимы правила, чтобы игра не продолжалась бесконечно. В противном случае граф является направленным ациклическим графом, и если это не корневое дерево, то игра имеет транспозиций. Этот граф и его топология важны при изучении сложности игры, где сложность пространства состояний - это количество вершин в графе, средняя игра длина - это среднее число вершин, пройденных от корня до вершины без прямых последователей, а средний коэффициент ветвления дерева игры - это средняя исходящая степень графа.
Количество корневых неориентированных графов для 1, 2,... узлов составляет 1, 2, 6, 20, 90, 544,... (последовательность A000666 в OEIS )
Особый интерес представляют корневые деревья, деревья с выделенной корневой вершиной. Если направленные пути от корня в корневом орграфе дополнительно ограничены, чтобы быть уникальными, то полученное понятие является понятием (корневого) древовидности - ориентированного графа, эквивалентного корневому дереву. Корневой граф содержит древовидность с одним и тем же корнем тогда и только тогда, когда весь граф может быть достигнут от корня, и компьютерщики изучили алгоритмические проблемы нахождения оптимальных древовидных образований.
Корневые графы могут быть объединены с помощью корневого продукта графов.
