Kuratowskis sætning - Kuratowski's theorem
I grafteori er Kuratowskis sætning en matematisk forbudt grafkarakterisering af plane grafer , opkaldt efter Kazimierz Kuratowski . Det hedder, at en endelig graf er plan, hvis og kun hvis den ikke indeholder en undergraf, der er en underopdeling af K 5 (den komplette graf på fem hjørner ) eller af K 3,3 ( komplet topartsgraf på seks hjørner, hvoraf tre oprette forbindelse til hver af de tre andre, også kendt som hjælpediagrammet ).
Udmelding
En plan graf er en graf, hvis hjørner kan repræsenteres af punkter i det euklidiske plan , og hvis kanter kan repræsenteres af enkle kurver i det samme plan, der forbinder de punkter, der repræsenterer deres slutpunkter, således at ingen to kurver krydser hinanden undtagen ved et fælles slutpunkt. Plangrafer er ofte tegnet med lige linjesegmenter, der repræsenterer deres kanter, men ved Fárys sætning gør det ingen forskel for deres grafteoretiske karakterisering.
En underinddeling af en graf er en graf dannet ved at opdele dens kanter i stier på en eller flere kanter. Kuratowski teorem anført, at et endeligt graf G er plan, hvis det ikke er muligt at underopdele kanter K 5 eller K 3,3 , og derefter eventuelt tilføje yderligere kanter og hjørner for at danne en graf isomorf til G . Tilsvarende er en endelig graf plan, hvis og kun hvis den ikke indeholder en undergraf, der er homomorf til K 5 eller K 3,3 .
Kuratowski undertegninger
Hvis G er en graf, der indeholder en delgraf H , der er en underafdeling af K 5 eller K 3,3 , derefter H er kendt som en Kuratowski delgraf af G . Med denne notation kan Kuratowskis sætning udtrykkes kortfattet: en graf er plan, hvis og kun hvis den ikke har en Kuratowski-undergraf.
De to grafer K 5 og K 3,3 er ikke-plane, som kan vises enten ved en case-analyse eller et argument involverer Eulers formel . Derudover kan underinddeling af en graf ikke omdanne en ikke-plan graf til en plan graf: hvis en underinddeling af en graf G har en plan tegning, dannes stierne for underinddelingen kurver, der kan bruges til at repræsentere kanterne af G selv. Derfor kan en graf, der indeholder en Kuratowski-undergraf, ikke være plan. Den sværere retning med at bevise Kuratowskis sætning er at vise, at hvis en graf er ikke-plan, skal den indeholde en Kuratowski-undergraf.
Algoritmiske implikationer
En Kuratowski-undergraf af en ikke-plan graf kan findes i lineær tid målt som størrelsen på inputgrafen. Dette gør det muligt at verificere rigtigheden af en planitetstestalgoritme for ikke-plane input, da det er ligetil at teste, om en given undergraf er en Kuratowski-undergraf eller ikke. Normalt indeholder ikke-plane grafer et stort antal Kuratowski-subgrafer. Ekstraktion af disse underbilleder er nødvendig, f.eks. I forgrenings- og snitalgoritmer til krydsningsminimering. Det er muligt at udtrække et stort antal Kuratowski-underbilleder i tide afhængigt af deres samlede størrelse.
Historie
Kazimierz Kuratowski offentliggjorde sin sætning i 1930. Teoremet blev uafhængigt bevist af Orrin Frink og Paul Smith , også i 1930, men deres bevis blev aldrig offentliggjort. Det specielle tilfælde af kubiske plane grafer (for hvilke den eneste minimale forbudte undergraf er K 3,3 ) blev også uafhængigt bevist af Karl Menger i 1930. Siden da er der opdaget flere nye beviser for sætningen.
I Sovjetunionen blev Kuratowskis sætning kendt som enten Pontryagin – Kuratowski sætning eller Kuratowski – Pontryagin sætning , da sætningen angiveligt blev bevist uafhængigt af Lev Pontryagin omkring 1927. Da Pontryagin aldrig offentliggjorde sit bevis, har denne brug ikke spredt sig til andre steder.
Relaterede resultater
Et nært beslægtet resultat, Wagners sætning , karakteriserer de plane grafer af deres mindreårige i form af de samme to forbudte grafer K 5 og K 3,3 . Hver Kuratowski-subgraf er et specielt tilfælde af en mindreårig af samme type, og selvom det omvendte ikke er sandt, er det ikke svært at finde en Kuratowski-subgraf (af den ene eller den anden type) fra en af disse to forbudte mindreårige; derfor er disse to sætninger ækvivalente.
En udvidelse er Robertson-Seymour-sætningen .
Se også
- Kelmans – Seymour formodning , at 5-forbundne ikke-plane grafer indeholder en underinddeling af K 5