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