Twierdzenie Hananiego-Tutte'a
W teorii grafów topologicznych twierdzenie Hananiego – Tutte jest wynikiem parzystości przecięć krawędzi na rysunku wykresu . Stwierdza, że każdy rysunek na płaszczyźnie grafu niepłaskiego zawiera parę niezależnych krawędzi (nie obie mają wspólny punkt końcowy), które przecinają się nieparzystą liczbę razy. Równoważnie można to sformułować jako kryterium planarności: graf jest planarny wtedy i tylko wtedy, gdy ma rysunek, na którym każda para niezależnych krawędzi przecina się równomiernie (lub wcale).
Historia
Wynik został nazwany na cześć Haima Hananiego , który udowodnił w 1934 r., że każdy rysunek dwóch minimalnych grafów nieplanarnych K 5 i K 3,3 ma parę krawędzi o nieparzystej liczbie przecięć, oraz na cześć WT Tutte , który stwierdził, że pełne twierdzenie wyraźnie w 1970 r. Równoległy rozwój podobnych idei w topologii algebraicznej został przypisany Egbertowi van Kampenowi , Arnoldowi S. Shapiro i Wu Wenjunowi .
Aplikacje
Jedną z konsekwencji tego twierdzenia jest to, że sprawdzanie, czy graf jest planarny, można sformułować jako rozwiązanie układu równań liniowych nad polem skończonym rzędu drugiego . Równania te można rozwiązać w czasie wielomianowym , ale otrzymane algorytmy są mniej wydajne niż inne znane testy planarności.
Uogólnienia
Dla innych powierzchni S niż płaszczyzna, wykres można narysować na S bez przecięć wtedy i tylko wtedy, gdy można go narysować w taki sposób, że wszystkie pary krawędzi przecinają się parzystą liczbę razy; jest to znane jako słabe twierdzenie Hananiego – Tutte'a dla S . Silne twierdzenie Hananiego – Tutte'a, znane zarówno z płaszczyzny rzutowej , jak i euklidesowej, stwierdza, że graf można narysować bez przecięć na S wtedy i tylko wtedy, gdy można go narysować w taki sposób, że wszystkie niezależne pary krawędzi przecinają się parzystą liczbę razy, bez względu na liczbę przecięć między krawędziami, które mają wspólny punkt końcowy.
To samo podejście, w którym pokazano, że pary krawędzi o parzystej liczbie przecięć można pominąć lub wyeliminować w pewnym typie rysowania grafów i wykorzystać ten fakt do utworzenia układu równań liniowych opisujących istnienie rysunku, zostało zastosowane zastosowane do kilku innych problemów z rysowaniem wykresów, w tym rysunków planarnych skierowanych w górę , rysunków minimalizujących liczbę nieskrzyżowanych krawędzi i planarności skupionej .