Топологическая теория графов: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правка
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.9
 
(не показано 11 промежуточных версий 8 участников)
Строка 1: Строка 1:
В [[Математика|математике]] '''топологическая теория графов''' — это ветвь [[Теория графов|теории графов]], изучающая [[вложение]] [[Граф (математика)|графов]] в [[Поверхность|поверхности]], [[Незацепленное вложение графа|пространственное вложение]] и графы как [[Топологическое пространство|топологические пространства]]{{sfn|Gross, Tucker|1987}}. В этой ветви изучаются также [[Погружение (топология)|погружения]] графов.
'''Топологическая теория графов''' — ветвь [[Теория графов|теории графов]], изучающая [[вложение]] [[Граф (математика)|графов]] в [[Поверхность|поверхности]], [[Незацепленное вложение графа|пространственное вложение]] и графы как [[Топологическое пространство|топологические пространства]]{{sfn|Gross, Tucker|1987}}. В этой ветви изучаются также [[Погружение (топология)|погружения]] графов.


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


== Графы как топологические пространства ==
== Графы как топологические пространства ==
Неориентированный граф можно рассматривать как {{не переведено 5|абстракный симплициальный комплекс|||abstract simplicial complex}} ''C'', где подмножествами являются одноэлементные множества (соответствуют вершинам) и двухэлементные множества (соответствуют рёбрам) <ref>[http://planetmath.org/?op=getobj&from=objects&id=4250 Graph topology], from [[PlanetMath]].</ref>. Геометрическая реализация комплекса |''C''| состоит из копий единичного интервала [0,1] для каждого ребра, при этом концы этих интервалов склеиваются в вершинах. С этой точки зрения вложение графа в поверхность или {{не переведено 5|Подразбиение (теория графов)|подразбиение||Subdivision (graph theory)}} другого графа являются частными случаями топологического вложения. {{не переведено 5|Гомеоморфизм (теория графов)|Гомеоморфизм||Homeomorphism (graph theory)}} графов — это просто специализация топологического [[гомеоморфизм]]а, понятие [[связный граф]] совпадает с [[Связное пространство|топологической связностью]], и связный граф является [[Дерево (теория графов)|деревом]] тогда и только тогда, когда его [[фундаментальная группа]] тривиальна.
Неориентированный граф можно рассматривать как {{не переведено 5|абстрактный симплициальный комплекс|||abstract simplicial complex}} ''C'', где подмножествами являются одноэлементные множества (соответствуют вершинам) и двухэлементные множества (соответствуют рёбрам)<ref>[http://planetmath.org/?op=getobj&from=objects&id=4250 Graph topology] {{Wayback|url=http://planetmath.org/?op=getobj&from=objects&id=4250 |date=20110514025048 }}, from [[PlanetMath]].</ref>. Геометрическая реализация комплекса |''C''| состоит из копий единичного интервала [0,1] для каждого ребра, при этом концы этих интервалов склеиваются в вершинах. С этой точки зрения вложение графа в поверхность или [[Гомеоморфизм_графов#Подразделение_и_исключение|подразделение]] другого графа являются частными случаями топологического вложения. [[Гомеоморфизм графов]] — это просто специализация топологического [[гомеоморфизм]]а, понятие [[связный граф]] совпадает с [[Связное пространство|топологической связностью]], и связный граф является [[Дерево (теория графов)|деревом]] тогда и только тогда, когда его [[фундаментальная группа]] тривиальна.


Другие симплициальные комплексы, связанные с графами, включают [[Флаговый комплекс|комплексы Уитни]] или ''кликовые комплексы'', где подмножествами являются [[Клика (теория графов)|клики]] графа, и ''комплексы паросочетаний'', где подмножествами служат [[Паросочетание|паросочетания]] графа (эквивалентно, кликовые комплексы дополнения [[Рёберный граф|рёберного графа]]). Комплекс паросочетаний [[Полный двудольный граф|полного двудольного графа]] называется ''комплексом шахматной доски'', так как его можно описать как комплекс множеств взаимно неатакующих ладей на шахматной доске.<ref>{{cite arXiv|author = John Shareshian, Michelle L. Wachs|title = Torsion in the matching complex and chessboard complex|year = 2004|eprint = math.CO/0409054 }}</ref>
Другие симплициальные комплексы, связанные с графами, включают [[Флаговый комплекс|комплексы Уитни]] или ''кликовые комплексы'', где подмножествами являются [[Клика (теория графов)|клики]] графа, и ''комплексы паросочетаний'', где подмножествами служат [[Паросочетание|паросочетания]] графа (эквивалентно, кликовые комплексы дополнения [[Рёберный граф|рёберного графа]]). Комплекс паросочетаний [[Полный двудольный граф|полного двудольного графа]] называется ''комплексом шахматной доски'', так как его можно описать как комплекс множеств взаимно неатакующих ладей на шахматной доске.<ref>{{cite arXiv|author = John Shareshian, Michelle L. Wachs|title = Torsion in the matching complex and chessboard complex|year = 2004|eprint = math.CO/0409054 }}</ref>


== Направления изучения ==
== Направления изучения ==
[[Хопкрофт, Джон|Джон Хопкрофт]] и [[Тарьян, Роберт|Роберт Тарьян]] {{sfn|Hopcroft, Tarjan|1974|с=549–568}} добились среднего времени {{не переведено 5|Проверка планарности|проверки планарности||planarity testing}} графа, линейного от числа рёбер. Их алгоритм делает это путём построения вложения графа, которое они называют «пальмой». Эффективность проверки на планарность имеет фундаментальное значение для [[Визуализация графов|визуализации графов]].
[[Хопкрофт, Джон|Джон Хопкрофт]] и [[Тарьян, Роберт|Роберт Тарьян]]{{sfn|Hopcroft, Tarjan|1974|с=549–568}} добились среднего времени [[Проверка планарности|проверки планарности]] графа, линейного от числа рёбер. Их алгоритм делает это путём построения вложения графа, которое они называют «пальмой». Эффективность проверки на планарность имеет фундаментальное значение для [[Визуализация графов|визуализации графов]].


Фан Чанг и др. {{sfn|Chung, Leighton, Rosenberg|1987}} изучали задачу [[Книжное вложение|книжного вложения графа]] с вершинами на прямой на корешке книги. Рёбра графа рисуются на разных страницах книги так, что лежащие на одной странице рёбра не пересекаются. Эта задача является абстракцией задачи разводки многослойных печатных плат.
Фан Чанг и др.{{sfn|Chung, Leighton, Rosenberg|1987}} изучали задачу [[Книжное вложение|книжного вложения графа]] с вершинами на прямой на корешке книги. Рёбра графа рисуются на разных страницах книги так, что лежащие на одной странице рёбра не пересекаются. Эта задача является абстракцией задачи разводки многослойных печатных плат.


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


== См. также ==
== См. также ==
*[[Число пересечений (теория графов)|Число пересечений]]
* [[Число пересечений (теория графов)|Число пересечений]]
*[[Род поверхности]]
* [[Род поверхности]]
*[[Планарный граф]]
* [[Планарный граф]]
*[[Тороидальный граф]]
* [[Тороидальный граф]]
*{{не переведено 5|Топологическая комбинаторика|||Topological combinatorics}}
* [[Топологическая комбинаторика]]
* [[Алгебраическая теория графов]]
* [[Перечисление графов]]
* [[Спектральная теория графов]]


== Примечания ==
== Примечания ==
{{примечания|2}}
{{примечания|2}}


==Литература ==
== Литература ==
* {{книга
* {{книга
|автор=J.L. Gross, T.W. Tucker
|автор=J.L. Gross, T.W. Tucker
Строка 35: Строка 38:
|isbn=0-471-04926-3
|isbn=0-471-04926-3
}}
}}
*{{статья
* {{статья
|заглавие = Efficient Planarity Testing
|заглавие = Efficient Planarity Testing
|издание = Journal of the ACM
|издание = Journal of the ACM
Строка 45: Строка 48:
|ref=Hopcroft, Tarjan
|ref=Hopcroft, Tarjan
}}
}}
*{{статья
* {{статья
|заглавие = Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
|заглавие = Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
|изданиеl = [[SIAM Journal on Algebraic and Discrete Methods]]
|изданиеl = [[SIAM Journal on Algebraic and Discrete Methods]]
Строка 54: Строка 57:
|ref=Chung, Leighton, Rosenberg
|ref=Chung, Leighton, Rosenberg
}}
}}
⚫
[[Категория:Топологическая теория графов]]


{{rq|checktranslate|style|grammar}}
{{rq|tex|checktranslate|style}}

⚫
[[Категория:Топологическая теория графов|*]]

Текущая версия от 18:55, 15 августа 2022

Топологическая теория графов — ветвь теории графов, изучающая вложение графов в поверхности, пространственное вложение и графы как топологические пространства[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.
Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Топологическая_теория_графов&oldid=124841191