Топологическая теория графов: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Jumpow (обсуждение | вклад) Перевод с английского статьи "Topological graph theory" |
Луговкин (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
В [[Математика|математике]] '''топологическая теория графов''' — это ветвь [[Теория графов|теории графов]], изучающая [[вложение]] [[Граф (математика)|графов]] в [[Поверхность|поверхности]], [[Незацепленное вложение графа|пространственное вложение]] и графы как [[Топологическое пространство|топологические пространства]] |
В [[Математика|математике]] '''топологическая теория графов''' — это ветвь [[Теория графов|теории графов]], изучающая [[вложение]] [[Граф (математика)|графов]] в [[Поверхность|поверхности]], [[Незацепленное вложение графа|пространственное вложение]] и графы как [[Топологическое пространство|топологические пространства]]{{sfn|Gross, Tucker|1987}}. В этой ветви изучаются также [[Погружение (топология)|погружения]] графов. |
||
Вложение графа в поверхность означает, что мы хотим нарисовать граф на поверхности, например, на [[Сфера|сфере]], без пересечения [[Ребро (теория графов)|рёбер]]. Основная задача |
Вложение графа в поверхность означает, что мы хотим нарисовать граф на поверхности, например, на [[Сфера|сфере]], без пересечения [[Ребро (теория графов)|рёбер]]. Основная задача вложения, представленная в виде [[Математическая головоломка|математической головоломки]] — задача «[[Домики и колодцы]]». Более важные приложения можно найти в подготовке печатных [[Электронная схема|электронных схем]], где целью является развести (вложить) электронные цепи (граф) на [[Печатная плата|печатной плате]] (поверхности) без пересечения цепей во избежание [[Короткое замыкание|короткого замыкания]]. |
||
== Графы как топологические простанства == |
== Графы как топологические простанства == |
||
Версия от 06:22, 3 декабря 2016
В математике топологическая теория графов — это ветвь теории графов, изучающая вложение графов в поверхности, пространственное вложение и графы как топологические пространства[1]. В этой ветви изучаются также погружения графов.
Вложение графа в поверхность означает, что мы хотим нарисовать граф на поверхности, например, на сфере, без пересечения рёбер. Основная задача вложения, представленная в виде математической головоломки — задача «Домики и колодцы». Более важные приложения можно найти в подготовке печатных электронных схем, где целью является развести (вложить) электронные цепи (граф) на печатной плате (поверхности) без пересечения цепей во избежание короткого замыкания.
Графы как топологические простанства
Неориентированный граф можно рассматривать как абстракный симплициальный комплекс[англ.] C, где подмножествами являются одноэлементные множества (соответствуют вершинам) и двухэлементные множества (соответствуют рёбрам) [2]. Геометрическая реализация комплекса |C| состоит из копий единичного интервала [0,1] для каждого ребра, при этом концы этих интервалов склеиваются в вершинах. С этой точки зрения вложение графа в поверхность или подразбиение[англ.] другого графа являются частными случаями топологического вложения. Гомеоморфизм[англ.]* графов — это просто специализация топологического гомеоморфизма, понятие связный граф совпадает с топологической связностью, и связный граф является деревом тогда и только тогда, когда его фундаментальная группа тривиальна.
Другие симплициальные комплексы, связанные с графами, включают комплексы Уитни или кликовые комплексы, где подмножествами являются клики графа, и комплексы паросочетаний, где подмножествами служат паросочетания графа (эквивалентно, кликовые комплексы дополнения рёберного графа). Комплекс паросочетаний полного двудольного графа называется комплексом шахматной доски, так как его можно описать как комплекс множеств взаимно неатакующих ладей на шахматной доске [3]
Направления изучения
Джон Хопкрофт и Роберт Тарьян [4] добились среднего времени проверки планарности?! графа, линейного от числа рёбер. Их алгоритм делает это путём построения вложения графа, которое они называют «пальмой». Эффективность проверки на планарность имеет фундаментальное значение для визуализации графов.
Фан Чанг и др. [5] изучали задачу книжного вложения графа с вершинами на прямой на корешке книги. Рёбра графа рисуются на разных страницах книги так, что лежащие на одной странице рёбра не пересекаются. Эта задача является абстракцией задачи разводки многослойных печатных плат.
Вложение графов используется также для доказательства структурных результатов на графах посредством теории миноров графа и структурной теоремы графов.
См. также
Примечания
- ↑ Gross, Tucker, 1987.
- ↑ Graph topology, from PlanetMath.
- ↑ John Shareshian, Michelle L. Wachs (2004). "Torsion in the matching complex and chessboard complex". arXiv:math.CO/0409054.
- ↑ Hopcroft, Tarjan, 1974, с. 549–568.
- ↑ 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.
 | Для улучшения этой статьи желательно:
|