| Klaus Wagner | |
|---|---|
| Němec Klaus Wagner | |
| Datum narození | 31. března 1910 |
| Místo narození | |
| Datum úmrtí | 6. února 2000 (ve věku 89 let) |
| Země | |
| Vědecká sféra | teorie a topologie grafů |
| Místo výkonu práce | |
| Alma mater | |
| vědecký poradce | Carl Dörge [d] [1] |
| Studenti | Rudolf Jeuck [d] [1] |
| Ocenění a ceny | čestný doktor University of Duisburg-Essen [d] ( 1997 ) |
| Mediální soubory na Wikimedia Commons | |
Klaus Wagner ( Němec : Klaus Wagner ; 31. března 1910 – 6. února 2000) byl německý matematik a teoretik grafů .
Wagner studoval topologii na univerzitě v Kolíně nad Rýnem u Karla Dörgeho., který byl žákem Isaie Shury . Wagner získal doktorát v roce 1937 disertační prací týkající se Jordanovy věty a věty o čtyřech barvách a sám řadu let učil v Kolíně nad Rýnem [2] . V roce 1970 se přestěhoval na University of Duisburg , kde učil až do svého odchodu do důchodu v roce 1978.
Wagner je známý svými příspěvky k teorii grafů a zejména k teorii grafových minorů , grafů, které lze vytvořit z většího grafu zmáčknutím a odstraněním hran.
Wagnerova věta charakterizuje rovinné grafy přesně jako ty grafy, které nemají ani úplný K 5 graf s pěti vrcholy, ani úplný K 3,3 bipartitní graf se třemi vrcholy v každé ze dvou částí jako vedlejší. To znamená, že tyto dva grafy jsou jediné minimální nerovinné grafy. Souvisí to s Kuratowského teorémem , který říká, že rovinné grafy jsou právě ty grafy, které neobsahují podgraf K 5 nebo K 3,3 jako podgraf, zatímco Wagnerova věta je slabší.
Dalším jeho výsledkem, také známým jako Wagnerův teorém, je to, že čtyřsouvislý graf je rovinný právě tehdy, když nemá K 5 moll . Z toho plyne charakterizace grafů bez K 5 moll jako konstruovaných z rovinných grafů a Wagnerova grafu (osmivertexový Möbiův žebříček ) pomocí klikových součtů , operací, které slepují podgrafy do klik až do tří vrcholů a poté z nich případně odebírají hrany. kliky. Tato charakterizace byla použita Wagnerem k tomu, aby ukázal, že případ k = 5 Hadwigerovy domněnky o chromatickém čísle grafu bez K k -minorů je ekvivalentní teorému o čtyřech barvách . Podobné charakterizace jiných rodin grafů z hlediska jejich klikových expanzí se od té doby staly standardem v teorii vedlejších grafů.
Wagner ve 30. letech 20. století (ač publikoval později) [3] navrhl , že v jakékoli nekonečné sadě grafů je jeden graf izomorfní k menšímu grafu jiného. Platnost této domněnky implikuje, že jakákoliv rodina grafů, které jsou uzavřeny operací pořizování nezletilých (například rovinné grafy), může být automaticky charakterizována konečným počtem zakázaných nezletilých , podobně jako Wagnerova věta charakterizující rovinné grafy. Neil Robertsona Paul Seymour zveřejnili důkaz tohoto tvrzení v roce 2004 a nyní je znám jako Robertson-Seymourova věta [4] .
V roce 1990 vydali Wagnerovi kolegové na jeho počest festfont [5] a v červnu 2000 bylo na kolínské univerzitě uspořádáno kolokvium na památku tohoto učitele [6] .
Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe" (nedostupný odkaz) , Mathematische Annalen , 114 : 570-590, doi: 10.1007/BF01594196