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

В математике , и, в частности, в теории графов , корневой граф — это граф , в котором одна вершина выделена как корень. [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 является элементом w . Аксиома антиоснования Ацеля утверждает, что каждый доступный точечный граф моделирует семейство (неполным основанием) множеств таким образом. [25]

Комбинаторная теория игр

Любая комбинаторная игра может быть связана с корневым ориентированным графом, вершины которого являются игровыми позициями, ребра — ходами, а корень — начальной позицией игры. Этот граф важен при изучении сложности игры , где сложность пространства состояний — это количество вершин в графе.

Комбинаторное перечисление

Число корневых неориентированных графов для узлов 1, 2, ... равно 1, 2, 6, 20, 90, 544, ... (последовательность A000666 в OEIS ).

Особый интерес представляют корневые деревья , деревья с выделенной корневой вершиной. Если направленные пути из корня в корневом орграфе дополнительно ограничены, чтобы быть уникальными, то полученное понятие является понятием (корневого) древовидного дерева — направленного графа, эквивалентного корневому дереву. [7] Корневой граф содержит древовидное дерево с тем же корнем тогда и только тогда, когда весь граф может быть достигнут из корня, и специалисты по информатике изучали алгоритмические проблемы поиска оптимальных древовидных деревьев. [26]

Корневые графы можно объединить, используя корневое произведение графов . [27]

Смотрите также

Ссылки

  1. ^ Цвиллингер, Дэниел (2011), Стандартные математические таблицы и формулы CRC, 32-е издание , CRC Press, стр. 150, ISBN 978-1-4398-3550-0
  2. ^ Харари, Фрэнк (1955), «Число линейных, направленных, корневых и связных графов», Труды Американского математического общества , 78 (2): 445–463, doi : 10.1090/S0002-9947-1955-0068198-2 , MR  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. ↑ Харари (1955, стр. 455).
  6. ^ ab Björner, Anders ; Ziegler, Günter M. (1992), "8. Введение в greedoids" (PDF) , в White, Neil (ред.), Matroid Applications, Encyclopedia of Mathematics and its Applications, т. 40, Кембридж: Cambridge University Press, стр. 284–357, doi : 10.1017/CBO9780511662041.009, ISBN 0-521-38165-7, MR  1165537, Zbl  0772.05026, В этом контексте корневой орграф Δ = ( V , E , r ) называется связным (или 1-связным ), если существует направленный путь из корня в каждую вершину.См. в частности стр. 307.
  7. ^ ab Gordon, Gary; McMahon, Elizabeth (февраль 1989), "A greedoid polynomial which differentes rooted arborescences" (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), «Быстрые параллельные алгоритмы для сокращаемых потоковых графов», Concurrent Computations : 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) , Дискретная прикладная математика , 131 (2): 523–533, doi : 10.1016/S0166-218X(02)00471-7 , Корневой орграф — это тройка G =( V , E , r ), где ( V ∪ { r }, E ) — орграф, а r — указанная вершина, называемая корнем, такая, что существует путь из r в каждую вершину V .. См. в частности стр. 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 , MR  2199991, S2CID  5235131
  12. ^ Кнут, Дональд (1997), "2.3.4.2. Ориентированные деревья", Искусство программирования , т. 1 (3-е изд.), Pearson Education, стр. 372, ISBN 0-201-89683-4Говорят , что он имеет корень, если существует хотя бы один корень, то есть хотя бы одна вершина R, такая что существует ориентированный путь из V в R для всех V ≠ R.
  13. ^ Гросс, Йеллен и Чжан (2013, стр. 1372).
  14. ^ Фентон, Норман Эллиотт; Хилл, Джиллиан А. (1993), Построение и анализ систем: математическая и логическая структура , McGraw-Hill, стр. 319, ISBN 978-0-07-707431-9.
  15. ^ abc Zuse, Хорст (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
  18. ^ ab Jalote, Pankaj (1997), Комплексный подход к программной инженерии , Springer Science & Business Media, стр. 372, ISBN 978-0-387-94899-7
  19. ^ Туласираман, К.; Свами, МНС (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), «Асимптотическое перечисление предикатно-соединительных потоковых графов», Комбинаторика, вероятность и вычисления , 5 (3): 215–226, doi :10.1017/S0963548300001991, S2CID  10313545
  25. ^ Aczel, Peter (1988), Не вполне обоснованные множества (PDF) , CSLI Lecture Notes, т. 14, Стэнфорд, Калифорния: Стэнфордский университет, Центр изучения языка и информации, ISBN 0-937073-22-9, LCCN  87-17857, MR  0940014, архивировано из оригинала (PDF) 2015-03-26
  26. ^ Дрешер, Мэтью; Ветта, Адриан (2010), «Аппроксимационный алгоритм для задачи максимального покрытия листьев», ACM Trans. Algorithms , 6 (3): 46:1–46:18, doi :10.1145/1798596.1798599, S2CID  13987985.
  27. ^ Godsil, CD ; McKay, BD (1978), "Новый граф-продукт и его спектр" (PDF) , Bull. Austral. Math. Soc. , 18 (1): 21–28, doi : 10.1017/S0004972700007760 , MR  0494910

Дальнейшее чтение

  • Макмахон, Элизабет В. (1993), «О многочлене гридоида для корневых графов и корневых орграфов», Журнал теории графов , 17 (3): 433–442, doi :10.1002/jgt.3190170316
  • Гордон, Гэри (2001), «Характеристический многочлен для корневых графов и корневых орграфов», Дискретная математика , 232 (1–3): 19–33, doi : 10.1016/S0012-365X(00)00186-2
Получено с "https://en.wikipedia.org/w/index.php?title=Rooted_graph&oldid=1222963149"