Топологическая теория графов - Topological graph theory

Эта статья посвящена изучению вложения графов. Графики на плоскости с перекрестками см. топологический граф.

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

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

Графы как топологические пространства

Смотрите также: Граф (топология) и Гомология графов

Неориентированному графу мы можем связать абстрактный симплициальный комплекс C с одноэлементным набором на вершину и двухэлементным набором на ребро.[2] Геометрическая реализация |C| комплекса состоит из копии единичного интервала [0,1] на ребро, с концами этих интервалы склеены в вершинах. С этой точки зрения вложения графов в поверхность или как подразделения других графов являются экземплярами топологического вложения, гомеоморфизм графов - это просто специализация топологических гомеоморфизм, понятие связный граф совпадает с топологическая связность, а связный граф - это дерево если и только если это фундаментальная группа тривиально.

Другие симплициальные комплексы, связанные с графами, включают Комплекс Уитни или кликовый комплекс, с набором на клика графика, а соответствующий комплекс, с набором на соответствие графа (эквивалентно кликовому комплексу дополнения к линейный график ). Соответствующий комплекс полный двудольный граф называется шахматный комплекс, так как его также можно описать как комплекс наборов не атакующих ладей на шахматной доске.[3]

Примеры исследований

Джон Хопкрофт и Роберт Тарджан[4] получил средство проверка планарности графа по времени, линейному количеству ребер. Их алгоритм делает это, строя вложение графа, которое они называют «пальмой». Эффективное тестирование планарности является фундаментальным рисунок графика.

Фань Чанг и другие.[5] изучил проблему встраивание графика в книгу с вершинами графа в линию вдоль корешка книги. Его края нарисованы на разных страницах таким образом, что края, находящиеся на одной странице, не пересекаются. Эта проблема абстрагирует проблемы компоновки, возникающие при разводке многослойных печатных плат.

Вложения графов также используются для доказательства структурных результатов о графах с помощью теория минор графов и теорема о структуре графа.

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

Заметки

  1. ^ Дж. Л. Гросс и T.W. Такер, Топологическая теория графов, Wiley Interscience, 1987
  2. ^ Топология графа, от PlanetMath.
  3. ^ Шарешян, Джон; Вакс, Мишель Л. (2004). «Кручение в согласующем комплексе и комплексе шахматной доски». arXiv:math.CO/0409054.CS1 maint: несколько имен: список авторов (ссылка на сайт)
  4. ^ Хопкрофт, Джон; Тарджан, Роберт Э. (1974). «Эффективное тестирование планарности» (PDF). Журнал ACM. 21 (4): 549–568. Дои:10.1145/321850.321852. HDL:1813/6011.
  5. ^ Чанг, Ф. Р. К.; Лейтон, Ф. Т.; Розенберг, А.Л. (1987). «Встраивание графиков в книги: проблема компоновки в приложениях к проектированию СБИС» (PDF). Журнал SIAM по алгебраическим и дискретным методам. 8 (1): 33–58. Дои:10.1137/0608002.