В математике топологическая теория графов является разделом теории графов . Он изучает вложение графов в поверхности , пространственные вложения графов и графы как топологические пространства . [1] Он также изучает погружения графов.
Встраивание графа в поверхность означает, что мы хотим нарисовать график на поверхности, например на сфере , без двух пересекающихся ребер . Основная проблема встраивания, которую часто представляют в виде математической головоломки, — это задача трех полезностей . Другие применения можно найти при печати электронных схем , где цель состоит в том, чтобы напечатать (встроить) схему (график) на печатную плату (поверхность) без двух соединений, пересекающих друг друга и приводящих к короткому замыканию .
Неориентированному графу мы можем связать абстрактный симплициальный комплекс C с одноэлементным набором на каждую вершину и двухэлементным набором на каждое ребро. Геометрическая реализация | С | комплекса состоит из копии единичного интервала [0,1] для каждого ребра, концы этих интервалов склеены в вершинах. С этой точки зрения, вложения графов в поверхность или в виде подразделений других графов являются случаями топологического вложения, гомеоморфизм графов — это просто специализация топологического гомеоморфизма , понятие связного графа совпадает с топологической связностью , а связный граф — это дерево тогда и только тогда, когда его фундаментальная группа тривиальна.
Другие симплициальные комплексы, связанные с графами, включают комплекс Уитни или комплекс клики с набором на клику графа и комплекс сопоставления с набором на сопоставление графа (эквивалентно комплексу клики дополнения линейного графа ). . Комплекс сопоставления полного двудольного графа называется комплексом шахматной доски , так как его также можно описать как комплекс наборов неатакующих ладей на шахматной доске. [2]
Джон Хопкрофт и Роберт Тарьян [3] разработали способ проверки планарности графа за время, линейное по количеству ребер. Их алгоритм делает это путем построения графа, который они называют «пальмой». Эффективное тестирование планарности имеет основополагающее значение для построения графиков .
Фан Чунг и др. [4] изучали проблему встраивания графа в книгу с вершинами графа, расположенными вдоль корешка книги. Его края рисуются на отдельных страницах таким образом, чтобы края, находящиеся на одной странице, не пересекались. Эта проблема абстрагирует проблемы компоновки, возникающие при разводке многослойных печатных плат.
Вложения графов также используются для доказательства структурных результатов о графах с помощью минорной теории графов и теоремы о структуре графа .