Клаус Вагнер (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]