Корневой граф
В математике , и, в частности, в теории графов , корневым графом называется граф , в котором одна вершина выделена как корень. [1] [2] Были изучены как ориентированные , так и неориентированные версии корневых графов, а также существуют варианты определений, допускающие множественные корни.
Корневые графы также могут быть известны (в зависимости от их применения) как точечные графы или потоковые графы . В некоторых приложениях этих графов существует дополнительное требование, чтобы весь граф был достижим из корневой вершины.
Вариации [ править ]
В топологической теории графов понятие корневого графа может быть расширено, чтобы рассматривать несколько вершин или несколько ребер как корни. Первые иногда называют графами с корнем вершин, чтобы отличить их от графов с корнем на ребрах в этом контексте. [3] Графы с множеством узлов, обозначенных как корни, также представляют некоторый интерес в комбинаторике , в области случайных графов . [4] Эти графы также называются многокорневыми графами . [5]
Термины «корневой ориентированный граф» или «корневой орграф» также имеют разные определения. Очевидный трансплантат — считать орграф корневым, идентифицируя конкретный узел как корень. [6] [7] Однако в информатике эти термины обычно относятся к более узкому понятию; а именно, корневой ориентированный граф — это орграф с выделенным узлом r , такой, что существует направленный путь от r до любого узла, отличного от r . [8] [9] [10] [11] Авторы, дающие более общее определение, могут называть графы, соответствующие более узкому определению, связными корневыми орграфами. [6] или доступные корневые графы (см. § Теорию множеств ).
Искусство компьютерного программирования определяет корневые орграфы несколько шире: ориентированный граф называется корневым, если у него есть хотя бы один узел, который может достигать всех остальных узлов. Кнут отмечает, что определенное таким образом понятие является своего рода промежуточным между понятиями сильно связного и связного орграфа . [12]
Приложения [ править ]
Графики потоков [ править ]
В информатике корневые графы, в которых корневая вершина может достигать всех остальных вершин, называются графами потоков или графами потоков . [13] Иногда добавляется дополнительное ограничение, определяющее, что граф потока должен иметь одну выходную ( стоковую ) вершину. [14]
Графические потоки можно рассматривать как абстракции блок -схем с удаленными неструктурными элементами (содержимым и типами узлов). [15] [16] Возможно, самым известным подклассом потоковых графов являются графы потока управления , используемые в компиляторах и анализе программ . Произвольный граф потока можно преобразовать в граф потока управления, выполняя сжатие ребра на каждом ребре, которое является единственным исходящим ребром из источника и единственным входящим ребром в цель. [17] Другой часто используемый тип графа потока — это граф вызовов , в котором узлы соответствуют целым подпрограммам . [18]
Общее понятие графа потока получило название графа программы . [19] но тот же термин также использовался для обозначения только графов потока управления. [20] Потоковые графы также называются неразмеченными потоковыми графами. [21] и правильные блок-схемы . [15] Эти графики иногда используются при тестировании программного обеспечения . [15] [18]
Когда требуется иметь один выход, графы потоков обладают двумя свойствами, которые обычно не свойственны ориентированным графам: графы потоков могут быть вложенными, что эквивалентно вызову подпрограммы (хотя здесь нет понятия передачи параметров), а графы потоков могут быть вложенными. также быть упорядоченным, что эквивалентно последовательному выполнению двух фрагментов кода. [22] Графы простых потоков определяются как графы потоков, которые нельзя разложить посредством вложения или упорядочивания с использованием выбранного шаблона подграфов, например, примитивов структурного программирования . [23] Были проведены теоретические исследования по определению, например, доли графов простых потоков в выбранном наборе графов. [24]
Теория множеств [ править ]
Питер Акзель использовал корневые ориентированные графы, в которых каждый узел достижим из корня (которые он называет доступными точечными графами ), чтобы сформулировать антифундаментальную аксиому Акселя в необоснованной теории множеств . В этом контексте каждая вершина доступного точечного графа моделирует (необоснованное) множество в рамках (необоснованной) теории множеств Акселя, а дуга от вершины v к вершине w моделирует, что v является элементом. из ш . Аксиома против фундамента Акселя утверждает, что каждый доступный точечный граф таким образом моделирует семейство (необоснованных) множеств. [25]
Комбинаторная теория игр [ править ]
Любая комбинаторная игра может быть связана с корневым ориентированным графом, вершины которого являются игровыми позициями, ребра — ходами, а корень — начальной позицией игры. Этот граф важен при изучении сложности игр , где сложность пространства состояний — это количество вершин в графе.
Комбинаторное перечисление [ править ]
Количество корневых неориентированных графов для 1, 2,... узлов равно 1, 2, 6, 20, 90, 544,... (последовательность A000666 в OEIS ).
Связанные понятия [ править ]
Особый случай представляют корневые деревья , деревья с выделенной корневой вершиной. Если направленные пути от корня в корневом орграфе дополнительно ограничены уникальностью, то получается понятие (корневой) древовидности - эквивалента корневого дерева в ориентированном графе. [7] Корневой граф содержит древовидность с тем же корнем тогда и только тогда, когда весь граф может быть достигнут из корня, и ученые-компьютерщики изучили алгоритмические проблемы поиска оптимальных древовидностей. [26]
Корневые графы можно комбинировать, используя корневое произведение графов . [27]
См. также [ править ]
Ссылки [ править ]
- ^ Цвиллингер, Дэниел (2011), Стандартные математические таблицы и формулы CRC, 32-е издание , CRC Press, стр. 150, ISBN 978-1-4398-3550-0
- ^ Харари, Франк (1955), «Число линейных, направленных, корневых и связных графов», Transactions of the American Mathematical Society , 78 (2): 445–463, doi : 10.1090/S0002-9947-1955-0068198- 2 , МР 0068198 . См. стр. 454.
- ^ Гросс, Джонатан Л.; Йеллен, Джей; Чжан, Пин (2013), Справочник по теории графов (2-е изд.), CRC Press, стр. 764–765, ISBN 978-1-4398-8018-0
- ^ Спенсер, Джоэл (2001), Странная логика случайных графов , Springer Science & Business Media, глава 4, ISBN 978-3-540-41654-8
- ^ III (1955 , стр. 455).
- ↑ Перейти обратно: Перейти обратно: а б Бьёрнер, Андерс ; Циглер, Гюнтер М. (1992), «8. Введение в гридоиды» (PDF) , в книге Уайт, Нил (ред.), Приложения Maroid , Энциклопедия математики и ее приложений, том. 40, Кембридж: Издательство Кембриджского университета, стр. 284–357 , номер документа : 10.1017/CBO9780511662041.009 , ISBN. 0-521-38165-7 , MR 1165537 , Zbl 0772.05026 ,
В этом контексте корневой орграф Δ = ( V , E , r ) называется связным (или 1-связным ), если существует направленный путь от корня до каждой вершины.
См., в частности, стр. 307. - ↑ Перейти обратно: Перейти обратно: а б Гордон, Гэри; МакМахон, Элизабет (февраль 1989 г.), «Гридоидный полином, который отличает корневые древовидные образования» (PDF) , Proceedings of the American Mathematical Society , 107 (2): 287, CiteSeerX 10.1.1.308.2526 , doi : 10.1090/s0002-9939- 1989-0967486-0 ,
Корневой подорграф F является корневым древом , если корневая вершина ∗ находится в F и для каждой вершины v в F существует единственный направленный путь в F от ∗ до v . Таким образом, корневые ветвления в орграфах соответствуют корневым деревьям в неориентированных графах.
- ^ Рамачандран, Виджая (1988), «Быстрые параллельные алгоритмы для приводимых потоковых графов», Параллельные вычисления : 117–138, doi : 10.1007/978-1-4684-5511-3_8 , ISBN 978-1-4684-5513-7 ,
Корневой ориентированный граф или граф потока G = ( V , A , r ) — это ориентированный граф с выделенной вершиной r существует направленный путь такой, что в G от r до каждой вершины v в V − r .
. См., в частности, стр. 122. - ^ Окамото, Ёсио; Накамура, Масатака (2003), «Запрещенная второстепенная характеристика антиматроидов линейного поиска корневых орграфов» (PDF) , Discrete Applied Mathematics , 131 (2): 523–533, doi : 10.1016/S0166-218X(02)00471- 7. называемая корнем ,
Корневой — заданная вершина , орграф — это тройка G = ( V , E , r ), где ( V ∪ { r }, E ) — орграф, а r такая, что существует путь от r до каждой вершины. В.
. См., в частности, стр. 524. - ^ Джайн, Абхинандан (2010), Динамика роботов и многих тел: анализ и алгоритмы , Springer Science & Business Media, стр. 136, ISBN 978-1-4419-7267-5 орграф
Корневой . — это связный орграф с единственным корневым узлом, который является предком всех остальных узлов в орграфе
- ^ Чен, Сюйджин; Занг, Вэнан (2006), «Эффективный алгоритм поиска упаковок максимальных циклов в приводимых потоковых графах», Algorithmica , 44 (3): 195–211, doi : 10.1007/s00453-005-1174-x , hdl : 10722/48600 , МР 2199991 , S2CID 5235131
- ^ Кнут, Дональд (1997), «2.3.4.2. Ориентированные деревья», Искусство компьютерного программирования , том. 1 (3-е изд.), Pearson Education, стр. 1. 372, ИСБН 0-201-89683-4 ,
Говорят, что он корневой, если существует хотя бы один корень, то есть хотя бы одна вершина R такая, что существует ориентированный путь из V в R для всех V ≠ R .
- ^ Гросс, Йеллен и Чжан (2013 , стр. 1372).
- ^ Фентон, Норман Эллиотт; Хилл, Джиллиан А. (1993), Построение и анализ систем: математическая и логическая основа , McGraw-Hill, с. 319, ISBN 978-0-07-707431-9 .
- ↑ Перейти обратно: Перейти обратно: а б с Цузе, Хорст (1998), Структура измерения программного обеспечения , Вальтер де Грюйтер, стр. 32–33, ISBN 978-3-11-080730-1
- ^ Самару, Анджелина; Томпсон, Джефф; Уильямс, Питер (2010), Тестирование программного обеспечения: Руководство по основам ISTQB-ISEB , BCS, The Chartered Institute, стр. 108, ISBN 978-1-906124-76-2
- ^ Тарр, Пери Л.; Вольф, Александр Л. (2011), Разработка программного обеспечения: постоянный вклад Леона Дж. Остервейла , Springer Science & Business Media, стр. 58, ISBN 978-3-642-19823-6
- ↑ Перейти обратно: Перейти обратно: а б Джалоте, Панкадж (1997), Интегрированный подход к разработке программного обеспечения , Springer Science & Business Media, стр. 372 , ISBN 978-0-387-94899-7
- ^ Туласираман, К.; Свами, MNS (1992), Графы: теория и алгоритмы , John Wiley & Sons, с. 361, ISBN 978-0-471-51356-8
- ^ Чечич, Алехандра; Пьяттини, Марио; Вальесильо, Антонио (2003), Качество программного обеспечения на основе компонентов: методы и методы , Springer Science & Business Media, стр. 105, ISBN 978-3-540-40503-0
- ^ Бейнеке, Лоуэлл В.; Уилсон, Робин Дж. (1997), Связи графов: взаимосвязь между теорией графов и другими областями математики , Clarendon Press, стр. 237 , ISBN 978-0-19-851497-8
- ^ Фентон и Хилл (1993 , стр. 323).
- ^ Фентон и Хилл (1993 , стр. 339).
- ^ Купер, К. (2008), «Асимптотическое перечисление потокограмм предикатов и соединений», Combinatorics, Probability and Computing , 5 (3): 215–226, doi : 10.1017/S0963548300001991 , S2CID 10313545
- ^ Аксель, Питер (1988), Необоснованные наборы (PDF) , Конспекты лекций CSLI, том. 14, Стэнфорд, Калифорния: Стэнфордский университет, Центр изучения языка и информации, ISBN. 0-937073-22-9 , LCCN 87-17857 , MR 0940014 , заархивировано из оригинала (PDF) 26 марта 2015 г.
- ^ Дрешер, Мэтью; Ветта, Адриан (2010), «Алгоритм аппроксимации для проблемы древовидности с максимальным размахом листьев» , ACM Trans. Алгоритмы , 6 (3): 46:1–46:18, doi : 10.1145/1798596.1798599 , S2CID 13987985 .
- ^ Годсил, CD ; Маккей, Б.Д. (1978), «Новый графовый продукт и его спектр» (PDF) , Bull. Австрал. Математика. Соц. , 18 (1): 21–28, doi : 10.1017/S0004972700007760 , MR 0494910
Дальнейшее чтение [ править ]
- МакМахон, Элизабет В. (1993), «О полиноме гридоида для корневых графов и корневых орграфов», Journal of Graph Theory , 17 (3): 433–442, doi : 10.1002/jgt.3190170316
- Гордон, Гэри (2001), «Характеристический полином для корневых графов и корневых орграфов», Discrete Mathematics , 232 (1–3): 19–33, doi : 10.1016/S0012-365X(00)00186-2