Корневой граф

В математике , и, в частности, в теории графов , корневым графом называется граф , в котором одна вершина выделена как корень. ^[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

Внешние ссылки

Вайсштейн, Эрик В. , «Корневой граф» , MathWorld

[1] Цвиллингер, Дэниел (2011), Стандартные математические таблицы и формулы CRC, 32-е издание , CRC Press, стр. 150, ISBN 978-1-4398-3550-0

[2] Харари, Франк (1955), «Число линейных, направленных, корневых и связных графов», Transactions of the American Mathematical Society , 78 (2): 445–463, doi : 10.1090/S0002-9947-1955-0068198- 2 , МР 0068198 . См. стр. 454.

[3] Гросс, Джонатан Л.; Йеллен, Джей; Чжан, Пин (2013), Справочник по теории графов (2-е изд.), CRC Press, стр. 764–765, ISBN 978-1-4398-8018-0

[4] Спенсер, Джоэл (2001), Странная логика случайных графов , Springer Science & Business Media, глава 4, ISBN 978-3-540-41654-8

[5] III (1955 , стр. 455).

[greedintro-6] Перейти обратно: ^а ^б Бьёрнер, Андерс ; Циглер, Гюнтер М. (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.

[poly-7] Перейти обратно: ^а ^б Гордон, Гэри; МакМахон, Элизабет (февраль 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 . Таким образом, корневые ветвления в орграфах соответствуют корневым деревьям в неориентированных графах.

[8] Рамачандран, Виджая (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.

[9] Окамото, Ёсио; Накамура, Масатака (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.

[10] Джайн, Абхинандан (2010), Динамика роботов и многих тел: анализ и алгоритмы , Springer Science & Business Media, стр. 136, ISBN 978-1-4419-7267-5 орграф Корневой . — это связный орграф с единственным корневым узлом, который является предком всех остальных узлов в орграфе

[11] Чен, Сюйджин; Занг, Вэнан (2006), «Эффективный алгоритм поиска упаковок максимальных циклов в приводимых потоковых графах», Algorithmica , 44 (3): 195–211, doi : 10.1007/s00453-005-1174-x , hdl : 10722/48600 , МР 2199991 , S2CID 5235131

[12] Кнут, Дональд (1997), «2.3.4.2. Ориентированные деревья», Искусство компьютерного программирования , том. 1 (3-е изд.), Pearson Education, стр. 1. 372, ИСБН 0-201-89683-4 , Говорят, что он корневой, если существует хотя бы один корень, то есть хотя бы одна вершина R такая, что существует ориентированный путь из V в R для всех V ≠ R .

[13] Гросс, Йеллен и Чжан (2013 , стр. 1372).

[14] Фентон, Норман Эллиотт; Хилл, Джиллиан А. (1993), Построение и анализ систем: математическая и логическая основа , McGraw-Hill, с. 319, ISBN 978-0-07-707431-9 .

[Zuse1998-15] Перейти обратно: ^а ^б ^с Цузе, Хорст (1998), Структура измерения программного обеспечения , Вальтер де Грюйтер, стр. 32–33, ISBN 978-3-11-080730-1

[16] Самару, Анджелина; Томпсон, Джефф; Уильямс, Питер (2010), Тестирование программного обеспечения: Руководство по основам ISTQB-ISEB , BCS, The Chartered Institute, стр. 108, ISBN 978-1-906124-76-2

[17] Тарр, Пери Л.; Вольф, Александр Л. (2011), Разработка программного обеспечения: постоянный вклад Леона Дж. Остервейла , Springer Science & Business Media, стр. 58, ISBN 978-3-642-19823-6

[Jalote1997-18] Перейти обратно: ^а ^б Джалоте, Панкадж (1997), Интегрированный подход к разработке программного обеспечения , Springer Science & Business Media, стр. 372 , ISBN 978-0-387-94899-7

[19] Туласираман, К.; Свами, MNS (1992), Графы: теория и алгоритмы , John Wiley & Sons, с. 361, ISBN 978-0-471-51356-8

[20] Чечич, Алехандра; Пьяттини, Марио; Валлесилло, Антонио (2003), Качество программного обеспечения на основе компонентов: методы и методы , Springer Science & Business Media, стр. 105, ISBN 978-3-540-40503-0

[21] Бейнеке, Лоуэлл В.; Уилсон, Робин Дж. (1997), Связи графов: взаимосвязь между теорией графов и другими областями математики , Clarendon Press, стр. 237 , ISBN 978-0-19-851497-8

[22] Фентон и Хилл (1993 , стр. 323).

[23] Фентон и Хилл (1993 , стр. 339).

[24] Купер, К. (2008), «Асимптотическое перечисление потокограмм предикатов и соединений», Combinatorics, Probability and Computing , 5 (3): 215–226, doi : 10.1017/S0963548300001991 , S2CID 10313545

[25] Аксель, Питер (1988), Необоснованные наборы (PDF) , Конспекты лекций CSLI, том. 14, Стэнфорд, Калифорния: Стэнфордский университет, Центр изучения языка и информации, ISBN. 0-937073-22-9 , LCCN 87-17857 , MR 0940014 , заархивировано из оригинала (PDF) 26 марта 2015 г.

[26] Дрешер, Мэтью; Ветта, Адриан (2010), «Алгоритм аппроксимации для проблемы древовидности с максимальным размахом листьев» , ACM Trans. Алгоритмы , 6 (3): 46:1–46:18, doi : 10.1145/1798596.1798599 , S2CID 13987985 .

[27] Годсил, CD ; Маккей, Б.Д. (1978), «Новый графовый продукт и его спектр» (PDF) , Bull. Австрал. Математика. Соц. , 18 (1): 21–28, doi : 10.1017/S0004972700007760 , MR 0494910

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]