Вагнер, Клаус (математик)

В Википедии есть статьи о других людях с такой фамилией, см. Вагнер; Вагнер, Клаус.

Клаус Вагнер (нем. Klaus Wagner; 31 марта 1910 — 6 февраля 2000) — немецкий математик, специалист по теории графов.

Клаус Вагнер
нем. Klaus Wagner
Дата рождения	31 марта 1910(1910-03-31)
Место рождения	Кёльн, Рейнская провинция, Королевство Пруссия, Германская империя
Дата смерти	6 февраля 2000(2000-02-06) (89 лет)
Страна	Германия
Научная сфера	теория графов и топология
Место работы	Кёльнский университет
Альма-матер	Кёльнский университет
Научный руководитель	Карл Дёрге[d]
Ученики	Rudolf Jeuck[d]
Награды и премии	почётный доктор Университета Дуйсбурга — Эссена[d] (1997)
Медиафайлы на Викискладе

Образование и карьераПравить

Вагнер изучал топологию в Кёльнском университете под руководством Карла Дёрге  (нем.) (рус., который был студентом Исая Шура. Вагнер получил докторскую степень в 1937 году, защитив диссертацию, касающуюся теоремы Жордана и теоремы о четырёх красках, и преподавал в Кёльне в течение многих лет сам. В 1970 году он перешёл в Дуйсбургский университет, где преподавал вплоть до выхода на пенсию в 1978 году.

Научная деятельностьПравить

Вагнер известен своим вкладом в теорию графов и, в частности, в теорию миноров графов — графов, которые можно сформировать из более крупного графа путём сжатия и удаления ребёр.

Теорема Вагнера характеризует плоские графы как точно те графы, которые не имеют в качестве минора ни полного графа K₅ с пятью вершинами, ни полного двудольного графа K_3,3 с тремя вершинами в каждой из двух долей. То есть эти два графа являются единственными минимальными неплоскими графами. Она связана с теоремой Куратовского, которая гласит, что планарные графы — это именно те графы, которые не содержат в качестве подграфа подразделение K₅ или K_3,3, при этом теорема Вагнера слабее.

 

Граф Вагнера

Другой его результат, также известный как теорема Вагнера, состоит в том, что четырёхсвязный граф является плоским тогда и только тогда, когда он не имеет минора K₅. Из этого следует характеризация графов без минора K₅ как построенных из плоских графов и графа Вагнера (восьмивершинная лестница Мёбиуса) с помощью сумм по клике — операций, которые склеивают подграфы в кликах до трёх вершин и затем, возможно, удаляют рёбра из тех клик. Эта характеризация была использована Вагнером, чтобы показать, что случай k = 5 гипотезы Хадвигера о хроматическом числе графов без K_k-миноров эквивалентен теореме о четырёх красках. Аналогичные характеризации других семейств графов в терминах слагаемых их разложений по кликам стали с тех пор стандартными в теории минорных графов.

Вагнер предположил в 1930-х годах (хотя опубликовал позднее), что в любом бесконечном наборе графов один граф изоморфен минору другого. Справедливость этой гипотезы влечёт, что любое семейство графов, замкнутых относительно операции взятия миноров (например, плоские графы), может автоматически характеризоваться конечным числом запрещённых миноров, аналогично теореме Вагнера, характеризующей планарные графы. Нил Робертсон  (англ.) (рус. и Пол Сеймур опубликовали доказательство этого утверждения в 2004 году и теперь оно известно как теорема Робертсона – Сеймура.

ПризнаниеПравить

В 1990 году коллеги Вагнера опубликовали в честь него фестшрифт, а в июне 2000 года в Кёльнском университете в память об этом преподавателе был организован коллоквиум.

Избранные публикацииПравить

Wagner, K. (1937), «Über eine Eigenschaft der ebenen Komplexe» (недоступная ссылка), Mathematische Annalen, 114: 570—590, doi:10.1007/BF01594196