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

Перейти к навигацииПерейти к поиску

Топологическая теория графов — ветвь теории графов, изучающая вложение графов в поверхности, пространственное вложение и графы как топологические пространства[1]. В этой ветви изучаются также погружения графов.

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

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

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

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

Направления изучения

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

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

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

См. также

Примечания

  1. ↑ Gross, Tucker, 1987.
  2. ↑ Graph topology Архивная копия от 14 мая 2011 на Wayback Machine, from PlanetMath.
  3. ↑ John Shareshian, Michelle L. Wachs (2004). "Torsion in the matching complex and chessboard complex". arXiv:math.CO/0409054.
  4. ↑ Hopcroft, Tarjan, 1974, с. 549–568.
  5. ↑ Chung, Leighton, Rosenberg, 1987.

Литература

  • J.L. Gross, T.W. Tucker. Topological graph theory. — Wiley Interscience, 1987. — (Wiley interscience series in discrete mathematics and optimization). — ISBN 0-471-04926-3.
  • John Hopcroft, Robert E. Tarjan. Efficient Planarity Testing // Journal of the ACM. — 1974. — Т. 21, вып. 4. — doi:10.1145/321850.321852.
  • F. R. K. Chung, F. T. Leighton, A. L. Rosenberg. Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design. — 1987. — Т. 8, вып. 1.