В математике , топологическая теория графов является ветвью теории графов . Он изучает вложение из графиков в поверхностях , пространственных вложений графов и графов как топологические пространства . [1] Он также изучает погружения графов.
Встраивание графа в поверхность означает, что мы хотим нарисовать граф на поверхности, например, сфере , без пересечения двух ребер . Основная задача встраивания, часто представляемая в виде математической головоломки, - это задача трех коттеджей . Другие приложения могут быть найдены в печати электронных схем, где цель состоит в том, чтобы напечатать (встроить) схему (график) на печатную плату (поверхность) без того, чтобы два соединения пересекали друг друга и приводили к короткому замыканию .
Графы как топологические пространства [ править ]
С неориентированным графом мы можем связать абстрактный симплициальный комплекс C с одноэлементным набором для каждой вершины и двухэлементным набором для каждого ребра. [2] Геометрическая реализация | C | комплекса состоит из копии единичного интервала [0,1] на ребро, причем концы этих интервалов склеены в вершинах. С этой точки зрения вложения графов в поверхность или как подразделения других графов являются экземплярами топологического вложения, гомеоморфизм графов - это просто специализация топологического гомеоморфизма , понятие связного графа совпадает с топологической связностью, а связный граф является деревом тогда и только тогда, когда его фундаментальная группа тривиальна.
Другие симплициальные комплексы, связанные с графами, включают комплекс Уитни или кликовый комплекс , с набором для каждой клики графа, и соответствующий комплекс , с набором для каждого сопоставления графа (эквивалентно, кликовый комплекс дополнения линейного графа ) . Соответствующий комплекс полного двудольного графа называется комплексом шахматной доски , так как его также можно описать как комплекс наборов не атакующих ладей на шахматной доске. [3]
Примеры исследований [ править ]
Джон Хопкрофт и Роберт Тарьян [4] получили средство проверки планарности графа по времени, линейному по количеству ребер. Их алгоритм делает это путем построения графа, который они называют «пальмой». Эффективное тестирование планарности является фундаментальным для построения графиков .
Fan Chung et al. В [5] изучалась проблема вложения графа в книгу с вершинами графа в линию вдоль корешка книги. Его края нарисованы на разных страницах таким образом, что края, находящиеся на одной странице, не пересекаются. Эта проблема абстрагируется от проблем компоновки, возникающих при разводке многослойных печатных плат.
Вложения графов также используются для доказательства структурных результатов о графах с помощью теории минор графов и теоремы о структуре графов .
См. Также [ править ]
- Число пересечения (теория графов)
- Род
- Планарный график
- Настоящее дерево
- Тороидальный граф
- Топологическая комбинаторика
- График напряжения
Заметки [ править ]
- ^ JL Gross и TW Tucker , Топологическая теория графов, Wiley Interscience, 1987
- ^ Топология графа , от PlanetMath .
- ^ Шарешян, Джон; Вакс, Мишель Л. (2004). «Кручение в согласующем комплексе и комплексе шахматной доски». arXiv : math.CO/0409054 .CS1 maint: multiple names: authors list (link)
- ^ Хопкрофт, Джон ; Тарьян, Роберт Э. (1974). «Эффективное тестирование планарности» (PDF) . Журнал ACM . 21 (4): 549–568. DOI : 10.1145 / 321850.321852 . hdl : 1813/6011 . CS1 maint: discouraged parameter (link)
- ^ Чанг, ФРГ ; Leighton, FT ; Розенберг, А.Л. (1987). «Встраивание графиков в книги: проблема макета с приложениями к проектированию СБИС» (PDF) . Журнал СИАМ по алгебраическим и дискретным методам . 8 (1): 33–58. DOI : 10,1137 / 0608002 . CS1 maint: discouraged parameter (link)
