WikiDer > Клаус Вагнер

Клаус Вагнер (справа) и Фрэнк Харари в Обервольфахе, 1972 г.

Клаус Вагнер (31 марта 1910 г. - 6 февраля 2000 г.) Немецкий математик известен своим вкладом в теория графов.

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

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

График миноров

В График Вагнера, восьмивершинник Лестница Мебиуса возникает в характеристике Вагнера K₅-свободные графики.

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

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

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

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

Признание

Вагнер был удостоен чести в 1990 г. фестивальный сбор по теории графов,^[4] а в июне 2000 года, после смерти Вагнера, в Кельнском университете был проведен фестиваль его памяти.^[5]

Избранные публикации

• Вагнер, К. (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen, 114: 570–590, Дои:10.1007 / BF01594196^{[постоянная мертвая ссылка]}.

Рекомендации