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

Rooted graph

В математика, и, в частности, в теория графов, а корневой граф это график в каком вершина был выделен как корень.[1][2] Обе направленный и ненаправленный были изучены версии корневых графов, а также существуют определения вариантов, допускающие множественные корни.

Графы с корневым доступом также могут быть известны (в зависимости от их применения) как точечные графы или же графы потока. В некоторых приложениях этих графов есть дополнительное требование, чтобы весь граф был достижимый из корневой вершины.

Вариации

В топологическая теория графов, понятие корневого графа можно расширить, чтобы рассматривать несколько вершин или несколько ребер в качестве корней. Первые иногда называют графами с вершинным корнем, чтобы отличать их от графов с реберным корнем в этом контексте.[3] Графы с несколькими узлами, обозначенными как корни, также представляют определенный интерес. комбинаторика, в районе случайные графы.[4] Эти графики также называют многокорневые графы.[5]

Условия укорененный ориентированный граф или же корневой орграф также см. различия в определениях. Очевидная трансплантация состоит в том, чтобы рассматривать орграф с корнем, идентифицируя определенный узел как корневой.[6][7] Однако в Информатика, эти термины обычно относятся к более узкому понятию, а именно, ориентированный граф с корнем - это орграф с выделенным узлом р, такая, что есть направленный путь от р к любому узлу кроме р.[8][9][10][11] Авторы, дающие более общее определение, могут называть их связаны (или же 1-связный) корневые орграфы.[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: 445–463, Дои: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. ^ Харари (1955 г., п. 455).
  6. ^ а б Бьёрнер, Андерс; Циглер, Гюнтер М. (1992), «8. Введение в гридоиды», в White, Neil (ed.), Приложения Matroid, Энциклопедия математики и ее приложений, 40, Кембридж: Издательство Кембриджского университета, стр.284–357, Дои:10.1017 / CBO9780511662041.009, ISBN 0-521-38165-7, МИСТЕР 1165537, Zbl 0772.05026CS1 maint: ref = harv (связь). См., В частности, стр. 307.
  7. ^ а б Гордон, Гэри; МакМэхон, Элизабет (1989), "Гридоидный полином, который различает корневые древовидные образования", Труды Американского математического общества, 107 (2): 287–287, Дои:10.1090 / s0002-9939-1989-0967486-0
  8. ^ Рамачандран, Виджая (1988), "Быстрые параллельные алгоритмы для приводимых потоковых графов", Параллельные вычисления: 117–138, Дои:10.1007/978-1-4684-5511-3_8. См., В частности, стр. 122.
  9. ^ Окамото, Ёсио (2003), "Запрещенная второстепенная характеристика антиматроидов поиска по линии корневых диграфов", Дискретная прикладная математика, 131 (2): 523–533, Дои:10.1016 / S0166-218X (02) 00471-7. См., В частности, стр. 524.
  10. ^ Джайн, Абхинандан (2010), Робот и многотельная динамика: анализ и алгоритмы, Springer Science & Business Media, стр. 136, ISBN 978-1-4419-7267-5
  11. ^ Чен, Сюйцзинь (2004 г.), "Эффективный алгоритм для поиска максимального количества циклов в сводимых графах потока", Конспект лекций по информатике: 306–317, Дои:10.1007/978-3-540-30551-4_28, HDL:10722/48600. См., В частности, стр. 308.
  12. ^ Кнут, Дональд (1997), Искусство программирования, Том 1, 3 / E, Pearson Education, стр. 372, ISBN 0-201-89683-4
  13. ^ Гросс, Йеллен и Чжан (2013 г.), п. 1372).
  14. ^ Фентон, Норман Эллиотт; Хилл, Джиллиан А. (1993), Построение и анализ систем: математическая и логическая основа, Макгроу-Хилл, стр. 319, ISBN 978-0-07-707431-9.
  15. ^ а б c Цузе, Хорст (1998), Структура измерения программного обеспечения, Вальтер де Грюйтер, стр. 32–33, ISBN 978-3-11-080730-1
  16. ^ Самару, Анджелина; Томпсон, Джефф; Уильямс, Питер (2010), Тестирование программного обеспечения: Руководство ISTQB-ISEB Foundation, BCS, Королевский институт, стр. 108, ISBN 978-1-906124-76-2
  17. ^ Tarr, Peri L .; Вольф, Александр Л. (2011), Разработка программного обеспечения: постоянный вклад Леона Дж. Остервейла, Springer Science & Business Media, стр. 58, ISBN 978-3-642-19823-6
  18. ^ а б Джалоте, Панкадж (1997), Комплексный подход к разработке программного обеспечения, Springer Science & Business Media, стр.372, ISBN 978-0-387-94899-7
  19. ^ Thulasiraman, K .; Свами, М. Н. С. (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. ^ Beineke, Lowell W .; Уилсон, Робин Дж. (1997), Связи графов: взаимосвязь между теорией графов и другими разделами математики, Clarendon Press, стр.237, ISBN 978-0-19-851497-8
  22. ^ Фентон и Хилл (1993, п. 323).
  23. ^ Фентон и Хилл (1993, п. 339).
  24. ^ Купер, К. (2008), "Асимптотическое перечисление потоковых графов предикатов", Комбинаторика, теория вероятностей и вычисления, 5 (3): 215, Дои:10.1017 / S0963548300001991
  25. ^ Aczel, Питер (1988), Необоснованные наборы., Лекционные заметки CSLI, 14, Стэнфорд, Калифорния: Стэнфордский университет, Центр изучения языка и информации, ISBN 0-937073-22-9, МИСТЕР 0940014
  26. ^ Дрешер, Мэтью; Ветта, Адриан (2010), "Алгоритм аппроксимации для задачи максимальной древовидности с растяжением листьев", ACM Trans. Алгоритмы, 6 (3): 46:1–46:18, Дои:10.1145/1798596.1798599.
  27. ^ Годсил, К. Д.; Маккей, Б.Д. (1978), «Новый графический продукт и его спектр» (PDF), Бык. Austral. Математика. Soc., 18 (1): 21–28, Дои:10.1017 / S0004972700007760, МИСТЕР 0494910

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

  • МакМэхон, Элизабет В. (1993), "О гридоидном полиноме для корневых графов и корневых орграфов", Журнал теории графов, 17 (3): 433–442, Дои:10.1002 / jgt.3190170316
  • Гордон, Гэри (2001), "Характеристический многочлен для корневых графов и корневых орграфов", Дискретная математика, 232 (1–3): 19–33, Дои:10.1016 / S0012-365X (00) 00186-2

внешняя ссылка