Клаус Вагнер (31 марта 1910 - 6 февраля 2000) был немецким математиком, известным своим вкладом в теорию графов .
Образование и карьера [ править ]
Вагнер изучал топологию в Кельнском университете под руководством Карла Дёрге который был учеником Иссая Шура . Вагнер получил докторскую степень. в 1937 г. защитил диссертацию по теореме о кривой Жордана и теореме о четырех цветах и сам много лет преподавал в Кельне. [1] В 1970 году он переехал в Дуйсбургский университет , где оставался до выхода на пенсию в 1978 году.
График миноры [ править ]
Вагнер известен своим вкладом в теорию графов и, в частности, в теорию миноров графов, графов, которые могут быть сформированы из большего графа путем сжатия и удаления ребер.
Теорема Вагнера характеризует плоские графы как в точности те графы, которые не имеют в качестве минора ни полного графа K 5 с пятью вершинами, ни полного двудольного графа K 3,3 с тремя вершинами на каждой стороне его двудольного разделения. То есть эти два графа - единственные минорно-минимальные неплоские графы. Оно тесно связано, но следует отличать от, теоремы Куратовского , в котором говорится , что планарные графы в точности те графики , которые не содержат в качестве подграфа в подразделение из K 5 или K 3,3 .
Другой его результат, также известный как теорема Вагнера, состоит в том, что четырехсвязный граф является плоским тогда и только тогда, когда он не имеет K 5 минор. Это подразумевает характеристику графов без минора K 5 как построенных из плоских графов и графа Вагнера (восьмивершинная лестница Мёбиуса ) с помощью клик-сумм , операций, которые склеивают подграфы в кликах до трех вершин и затем, возможно, удаляют края этих клик. Эта характеристика была использована Вагнером, чтобы показать, что случай k = 5 гипотезы Хадвигера о хроматическом числе K k-безминорные графы эквивалентны теореме о четырех цветах . Аналогичные характеристики других семейств графов в терминах слагаемых их разложений на клику с тех пор стали стандартом в теории миноров графов.
Вагнер предположил в 1930-х годах (хотя эта гипотеза была опубликована позже) [2], что в любом бесконечном множестве графов один граф изоморфен второстепенному другому. Справедливость этой гипотезы означает, что любое семейство графов, замкнутое относительно операции взятия миноров (как плоские графы), может автоматически характеризоваться конечным числом запрещенных миноров аналогично теореме Вагнера, характеризующей планарные графы. Нил Робертсон и Пол Сеймур наконец опубликовали доказательство гипотезы Вагнера в 2004 году, и теперь оно известно как теорема Робертсона – Сеймура . [3]
Признание [ править ]
Вагнер был удостоен награды в 1990 г. на фестивале по теории графов [4], а в июне 2000 г., после смерти Вагнера, Кельнский университет провел Фестколлоквиум в его память. [5]
Избранные публикации [ править ]
- Вагнер, К. (1937), "Убер Eigenschaft дер сделайте ebenen Komplexe" , Mathematische Annalen , 114 : 570-590, DOI : 10.1007 / BF01594196[ постоянная мертвая ссылка ] .
Ссылки [ править ]
- ↑ Клаус Вагнер в проекте « Математическая генеалогия»
- ^ Кассельман, Билл, Вариации на малом графике , Американское математическое общество.
- ^ Робертсон, Нил ; Seymour, Пол (2004), "Graph Несовершеннолетние XX: гипотеза Вагнера", Журнал комбинаторной теории, серии B , 92 (2): 325-357, DOI : 10.1016 / j.jctb.2004.08.001.
- ^ Бодендик, Райнер, изд. (1990), Современные методы в теории графов: в честь профессора доктора Клауса Вагнера , Мангейм: Bibliographisches Institut, Wissenschaftsverlag, ISBN 978-3-411-14301-6.
- ^ Festkolloquium в Памяти Клауса Вагнера
