Вагнер, Клаус (математик)
| Клаус Вагнер | |
|---|---|
| нем. Klaus Wagner | |
 Клаус Вагнер (справа) и Фрэнк Харари в Обервольфахе, 1972 | |
| Дата рождения | 31 марта 1910 |
| Место рождения | |
| Дата смерти | 6 февраля 2000 (89 лет) |
| Страна | |
| Род деятельности | математик, тополог, преподаватель университета |
| Научная сфера | теория графов и топология |
| Место работы | |
| Альма-матер | |
| Научный руководитель | Карл Дёрге[вд][1] |
| Ученики | Rudolf Jeuck[вд][1] |
| Награды и премии | |
 Медиафайлы на Викискладе | |
Клаус Вагнер (нем. Klaus Wagner; 31 марта 1910 — 6 февраля 2000) — немецкий математик, специалист по теории графов.
Образование и карьера
[править | править код]Вагнер изучал топологию в Кёльнском университете под руководством Карла Дёрге[нем.], который был студентом Исая Шура. Вагнер получил докторскую степень в 1937 году, защитив диссертацию, касающуюся теоремы Жордана и теоремы о четырёх красках, и преподавал в Кёльне в течение многих лет сам[2]. В 1970 году он перешёл в Дуйсбургский университет, где преподавал вплоть до выхода на пенсию в 1978 году.
Научная деятельность
[править | править код]Вагнер известен своим вкладом в теорию графов и, в частности, в теорию миноров графов — графов, которые можно сформировать из более крупного графа путём сжатия и удаления ребёр.
Теорема Вагнера характеризует плоские графы как точно те графы, которые не имеют в качестве минора ни полного графа K5 с пятью вершинами, ни полного двудольного графа K3,3 с тремя вершинами в каждой из двух долей. То есть эти два графа являются единственными минимальными неплоскими графами. Она связана с теоремой Куратовского, которая гласит, что планарные графы — это именно те графы, которые не содержат в качестве подграфа подразделение K5 или K3,3, при этом теорема Вагнера слабее.
Другой его результат, также известный как теорема Вагнера, состоит в том, что четырёхсвязный граф является плоским тогда и только тогда, когда он не имеет минора K5. Из этого следует характеризация графов без минора K5 как построенных из плоских графов и графа Вагнера (восьмивершинная лестница Мёбиуса) с помощью сумм по клике — операций, которые склеивают подграфы в кликах до трёх вершин и затем, возможно, удаляют рёбра из тех клик. Эта характеризация была использована Вагнером, чтобы показать, что случай k = 5 гипотезы Хадвигера о хроматическом числе графов без Kk-миноров эквивалентен теореме о четырёх красках. Аналогичные характеризации других семейств графов в терминах слагаемых их разложений по кликам стали с тех пор стандартными в теории минорных графов.
Вагнер предположил в 1930-х годах (хотя опубликовал позднее)[3], что в любом бесконечном наборе графов один граф изоморфен минору другого. Справедливость этой гипотезы влечёт, что любое семейство графов, замкнутых относительно операции взятия миноров (например, плоские графы), может автоматически характеризоваться конечным числом запрещённых миноров, аналогично теореме Вагнера, характеризующей планарные графы. Нил Робертсон[англ.] и Пол Сеймур опубликовали доказательство этого утверждения в 2004 году и теперь оно известно как теорема Робертсона – Сеймура[4].
Признание
[править | править код]В 1990 году коллеги Вагнера опубликовали в честь него фестшрифт[5], а в июне 2000 года в Кёльнском университете в память об этом преподавателе был организован коллоквиум[6].
Избранные публикации
[править | править код]Wagner, K. (1937), «Über eine Eigenschaft der ebenen Komplexe» (недоступная ссылка), Mathematische Annalen, 114: 570—590, doi:10.1007/BF01594196
Примечания
[править | править код]- ↑ 1 2 3 Mathematics Genealogy Project (англ.) — 1997.
- ↑ Klaus Wagner (англ.) в проекте «Математическая генеалогия»
- ↑ Casselman, Bill, Variations on Graph Minor, American Mathematical Society, Архивировано 15 июля 2009, Дата обращения: 6 июня 2020 Источник. Дата обращения: 6 июня 2020. Архивировано 15 июля 2009 года..
- ↑ Robertson, Neil [in английский]; Seymour, Paul (2004), "Graph Minors XX: Wagner's Conjecture", Journal of Combinatorial Theory, Series B, 92 (2): 325—357, doi:10.1016/j.jctb.2004.08.001.
- ↑ Bodendieck, Rainer, ed. (1990), Contemporary Methods in Graph Theory: In honour of Prof. Dr. Klaus Wagner, Mannheim: Bibliographisches Institut, Wissenschaftsverlag, ISBN 978-3-411-14301-6.
- ↑ Festkolloquium in memoriam Klaus Wagner. Дата обращения: 6 августа 2020. Архивировано 6 августа 2020 года.