Топологическая теория графов
В математике топологическая теория графов является разделом теории графов . Он изучает вложение графов в поверхности , пространственные вложения графов и графы как топологические пространства . [1] Он также изучает погружения графов.
Встраивание графа в поверхность означает, что мы хотим нарисовать граф на поверхности, сфере например на ребер , без двух пересекающихся . Основная проблема встраивания, которую часто представляют в виде математической головоломки, — это задача трех полезностей . Другие применения можно найти при печати электронных схем , целью которых является напечатать (встроить) схему (график) на печатную плату (поверхность) без двух соединений, пересекающих друг друга и приводящих к короткому замыканию .
пространства топологические Графы как
Неориентированному графу мы можем связать абстрактный симплициальный комплекс C с одноэлементным набором на каждую вершину и двухэлементным набором на каждое ребро. Геометрическая реализация | С | комплекса состоит из копии единичного интервала [0,1] для каждого ребра, концы которых склеены в вершинах. С этой точки зрения, вложения графов в поверхность или в виде подразделений других графов являются случаями топологического вложения, гомеоморфизм графов — это просто специализация топологического гомеоморфизма , понятие связного графа совпадает с топологической связностью , а связный граф — это дерево его тогда и только тогда, когда фундаментальная группа тривиальна.
Другие симплициальные комплексы, связанные с графами, включают комплекс Уитни или комплекс клики с набором на клику графа и комплекс сопоставления с набором на сопоставление графа (эквивалентно комплексу клики дополнения линейного графа ). . Комплекс сопоставления полного двудольного графа называется комплексом шахматной доски , так как его также можно описать как комплекс наборов неатакующих ладей на шахматной доске. [2]
Примеры исследований [ править ]
Джон Хопкрофт и Роберт Тарджан [3] разработал способ проверки планарности графа за время, линейное от количества ребер. Их алгоритм делает это путем построения графа, который они называют «пальмой». Эффективное тестирование планарности имеет основополагающее значение для построения графиков .
Фан Чунг и др. [4] изучал проблему встраивания графа в книгу с вершинами графа, расположенными вдоль корешка книги. Его края рисуются на отдельных страницах таким образом, чтобы края, находящиеся на одной странице, не пересекались. Эта проблема абстрагирует проблемы компоновки, возникающие при разводке многослойных печатных плат.
Вложения графов также используются для доказательства структурных результатов о графах с помощью минорной теории графов и теоремы о структуре графа .
См. также [ править ]
- Число пересечений (теория графов)
- Род
- Планарный граф
- Настоящее дерево
- Тороидальный граф
- Топологическая комбинаторика
- График напряжения
Примечания [ править ]
- ^ Гросс, Дж.Л.; Такер, Т.В. (2012) [1987]. Топологическая теория графов . Дувр. ISBN 978-0-486-41741-7 .
- ^ Шарешян, Джон; Вакс, Мишель Л. (2007) [2004]. «Кручение в согласующем комплексе и шахматном комплексе» . Достижения в математике . 212 (2): 525–570. arXiv : math.CO/0409054 . CiteSeerX 10.1.1.499.1516 . дои : 10.1016/j.aim.2006.10.014 .
- ^ Хопкрофт, Джон ; Тарьян, Роберт Э. (1974). «Эффективное тестирование планарности» (PDF) . Журнал АКМ . 21 (4): 549–568. дои : 10.1145/321850.321852 . hdl : 1813/6011 . S2CID 6279825 .
- ^ Чанг, Франция ; Лейтон, Форт-Стрит ; Розенберг, Ал. (1987). «Встраивание графиков в книги: проблема компоновки приложений для проектирования СБИС» (PDF) . SIAM Journal по алгебраическим и дискретным методам . 8 (1): 33–58. дои : 10.1137/0608002 .