Hanani-Tuttes sats
I topologisk grafteori är Hanani -Tutte-satsen ett resultat av pariteten för kantkorsningar i en grafritning . Den anger att varje ritning i planet för en icke-plan graf innehåller ett par oberoende kanter (inte båda delar en slutpunkt) som korsar varandra ett udda antal gånger. På motsvarande sätt kan det formuleras som ett planaritetskriterium: en graf är plan om och endast om den har en ritning där varje par oberoende kanter korsar jämnt (eller inte alls).
Historia
Resultatet är uppkallat efter Haim Hanani , som bevisade 1934 att varje ritning av de två minimala icke-plana graferna K 5 och K 3,3 har ett par kanter med ett udda antal korsningar, och efter WT Tutte , som angav att fullständig sats uttryckligen 1970. En parallell utveckling av liknande idéer inom algebraisk topologi har tillskrivits Egbert van Kampen , Arnold S. Shapiro och Wu Wenjun .
Ansökningar
En konsekvens av satsen är att testet om en graf är plan kan formuleras som att lösa ett system av linjära ekvationer över det finita fältet av ordning två . Dessa ekvationer kan lösas i polynomtid , men de resulterande algoritmerna är mindre effektiva än andra kända planaritetstester.
Generaliseringar
För andra ytor S än planet kan en graf ritas på S utan korsningar om och endast om den kan ritas på ett sådant sätt att alla par av kanter korsar ett jämnt antal gånger; detta är känt som det svaga Hanani-Tuttes sats för S . Den starka Hanani-Tutte-satsen, känd för såväl det projektiva planet som för det euklidiska planet, säger att en graf kan ritas utan korsningar på S om och bara om den kan ritas på ett sådant sätt att alla oberoende par av kanter korsar ett jämnt antal gånger, utan hänsyn till antalet korsningar mellan kanter som delar en ändpunkt.
Samma tillvägagångssätt, där man visar att par av kanter med ett jämnt antal korsningar kan ignoreras eller elimineras i någon typ av grafritning och använder detta faktum för att sätta upp ett system av linjära ekvationer som beskriver förekomsten av en ritning, har varit tillämpas på flera andra grafritningsproblem, inklusive uppåtgående plana ritningar , ritningar som minimerar antalet okorsade kanter och klustrad planaritet .