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