Snark (grafteori)
Inom det matematiska området för grafteorin är en snark en oriktad graf med exakt tre kanter per vertex vars kanter inte kan färgas med endast tre färger. För att undvika triviala fall är snarks ofta begränsade till att ha ytterligare krav på deras anslutning och på längden på deras cykler . Oändligt många snarkar finns.
En av de ekvivalenta formerna av fyrafärgssatsen är att varje snark är en icke-plan graf . Forskning om snarks har sitt ursprung i Peter G. Taits arbete med fyrafärgssatsen 1880, men deras namn är mycket nyare, som de gavs av Martin Gardner 1976. Utöver färgning har snarkar också kopplingar till andra svåra problem inom grafteorin : Miroslav Chladný och Martin Škoviera skriver i Electronic Journal of Combinatorics att
I studiet av olika viktiga och svåra problem inom grafteorin (som cyklisk dubbeltäckningsförmodan och 5-flödesförmodan ) möter man en intressant men lite mystisk variation av grafer som kallas snarks. Trots deras enkla definition...och över ett sekel långa undersökningar är deras egenskaper och struktur i stort sett okända.
Förutom de problem de nämner, gäller WT Tuttes snark - förmodan förekomsten av Petersen-grafer som grafiska mindreeringar av snarks; dess bevis har tillkännagetts länge men förblir opublicerat, och skulle lösa ett specialfall av förekomsten av ingenstans noll 4-flöden .
Historia och exempel
Snarks hette så av den amerikanske matematikern Martin Gardner 1976, efter det mystiska och svårfångade föremålet i dikten The Hunting of the Snark av Lewis Carroll . Studien av denna klass av grafer är dock betydligt äldre än deras namn. Peter G. Tait inledde studiet av snarks 1880, när han bevisade att fyrafärgssatsen motsvarar påståendet att ingen snark är plan . Den första grafen som man vet var en snark var Petersen-grafen ; det visade sig vara ett snärt av Julius Petersen 1898, även om det redan hade studerats för ett annat syfte av Alfred Kempe 1886.
De nästa fyra kända snarkarna var
- Blanuša snarks (två med 18 hörn), upptäckte av Danilo Blanuša 1946,
- Descartes snark (210 hörn), upptäckt av Bill Tutte 1948, och
- Szekeres snark (50 hörn), upptäckt av George Szekeres 1973.
År 1975 generaliserade Rufus Isaacs Blanušas metod för att konstruera två oändliga familjer av snark: blomsnärkarna och Blanuša–Descartes–Szekeres snarkarna, en familj som inkluderar de två Blanuša snarkarna, Descartes snarkarna och Szekeres snarkarna. Isaacs upptäckte också en snark med 30 vertex som inte tillhör familjen Blanuša–Descartes–Szekeres och som inte är en blomsnark: dubbelstjärnans snark . Watkins snark med 50 vertex upptäcktes 1989.
En annan anmärkningsvärd kubisk, icke-trekantig färgbar graf är Tietzes graf , med 12 hörn; som Heinrich Franz Friedrich Tietze upptäckte 1910, utgör den gränsen för en underavdelning av Möbiusremsan som kräver sex färger. Men eftersom den innehåller en triangel, anses den i allmänhet inte vara en snark. Under strikta definitioner av snarks är de minsta snarks Petersen-grafen och Blanuša snarks, följt av sex olika 20-vertex snarks.
En lista över alla snarkar upp till 36 hörn (enligt en strikt definition) och upp till 34 hörn (under en svagare definition), genererades av Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund och Klas Markström 2012. Antalet av snarks för ett givet jämnt antal hörn växer åtminstone exponentiellt i antalet hörn. (Eftersom de har udda graders hörn, måste alla snarks ha ett jämnt antal hörn enligt handskakningslemma .) OEIS - sekvens A130315 innehåller antalet icke-triviala snarks av hörn för små värden på .
Definition
Den exakta definitionen av snarks varierar mellan författare, men hänvisar i allmänhet till kubiska grafer (med exakt tre kanter vid varje vertex) vars kanter inte kan färgas med endast tre färger. Enligt Vizings teorem är antalet färger som behövs för kanterna på en kubisk graf antingen tre ("klass ett"-grafer) eller fyra ("klass två"-grafer), så snarks är kubiska grafer av klass två. Men för att undvika fall där en snark är av klass två av triviala skäl, eller är konstruerad på ett trivialt sätt från mindre grafer, införs ofta ytterligare begränsningar för anslutningsmöjligheter och cykellängder. Särskilt:
- Om en kubisk graf har en bro , en kant vars borttagning skulle koppla bort den, kan den inte vara av klass ett. Genom handskakningslemma har subgraferna på vardera sidan av bron ett udda antal hörn vardera. Oavsett vilken av tre färger som väljs för bryggan, förhindrar deras udda antal hörn att dessa subgrafer täcks av cykler som växlar mellan de andra två färgerna, vilket skulle vara nödvändigt i en 3-kantsfärgning. Av denna anledning krävs i allmänhet att snarks är brolösa.
- En slinga (en kant som förbinder en vertex med sig själv) kan inte färgas utan att samma färg visas två gånger vid den vertexen, vilket bryter mot de vanliga kraven för grafkantsfärgning. Dessutom kan en cykel som består av två hörn sammankopplade med två kanter alltid ersättas av en enda kant som förbinder deras två andra grannar, vilket förenklar grafen utan att ändra dess trekantsfärgbarhet. Av dessa skäl är snarks i allmänhet begränsade till enkla grafer , grafer utan loopar eller flera angränsningar.
- Om en graf innehåller en triangel kan den återigen förenklas utan att ändra dess trekantsfärgbarhet genom att dra ihop triangelns tre hörn till en enda vertex. Därför förbjuder många definitioner av snarks trianglar. Men även om detta krav också angavs i Gardners arbete som ger namnet "snark" till dessa grafer, listar Gardner Tietzes graf , som innehåller en triangel, som en snark.
- Om en graf innehåller en cykel med fyra vertex kan den förenklas på två olika sätt genom att ta bort två motsatta kanter av cykeln och ersätta de resulterande banorna för två graders hörn med enstaka kanter. Den har en trekantsfärgning om och bara om minst en av dessa förenklingar gör det. Därför kräver Isaacs en "icke-trivial" kubisk klass två-graf för att undvika cykler med fyra vertex, och andra författare har följt efter och förbjudit dessa cykler. Kravet på att en snark ska undvika cykler med längd fyra eller mindre kan sammanfattas genom att ange att omkretsen på dessa grafer, längden på deras kortaste cykler, är minst fem.
- Starkare är definitionen som används av Brinkmann et al. (2012) kräver att snarks är cykliskt 4-kantsanslutna. Det betyder att det inte kan finnas någon delmängd av tre eller färre kanter, vars borttagning skulle koppla bort grafen till två subgrafer som var och en har minst en cykel. Brinkmann et al. definiera en snark som en kubisk och cykliskt 4-kants-ansluten graf med omkrets fem eller mer och klass två; de definierar en "svag snark" för att tillåta omkrets fyra.
Även om dessa definitioner endast tar hänsyn till begränsningar på omkretsen upp till fem, finns det snarks med godtyckligt stor omkrets.
Egenskaper
Arbete av Peter G. Tait fastställde att fyrfärgssatsen är sann om och bara om varje snark är icke-plan. Denna sats säger att varje plan graf har en graffärgning av sina hörn med fyra färger, men Tait visade hur man konverterar 4-vertexfärgningar av maximala plana grafer till 3-kantfärgningar av deras dubbla grafer , som är kubiska och plana , och vice versa. En plan snark skulle därför nödvändigtvis vara dubbel till ett motexempel till fyrfärgssatsen. Således visar det efterföljande beviset för fyrfärgssatsen också att alla snarkar är icke-plana.
Alla snarks är icke- hamiltonska : när en kubisk graf har en Hamiltonsk cykel är det alltid möjligt att trefärga dess kanter, genom att använda två färger omväxlande för cykeln och den tredje färgen för de återstående kanterna. Men många kända snarkar är nära att vara Hamiltonska, i den meningen att de är hypohamiltonska grafer : avlägsnandet av en enda vertex lämnar en Hamiltonsk subgraf. En hypohamiltonisk snark måste vara bikritisk : borttagandet av två hörn lämnar en trekantsfärgbar subgraf. Uddaheten i en kubisk graf definieras som det minsta antalet udda cykler, i alla system av cykler som täcker varje vertex en gång (en 2 -faktor ). Av samma anledning som de inte har några Hamiltonska cykler, har snarks positiva konstigheter: en helt jämn 2-faktor skulle leda till en 3-kantsfärgning och vice versa. Det är möjligt att konstruera oändliga familjer av snarkar vars uddahet växer linjärt med deras antal hörn.
Cykeldubbeltäckningsförmodan antyder att man i varje brolös graf kan hitta en samling cykler som täcker varje kant två gånger , eller motsvarande att grafen kan bäddas in på en yta på ett sådant sätt att alla ytor av inbäddningen är enkla cykler. När en kubisk graf har en 3-kantsfärgning, har den ett dubbelt cykelhölje som består av de cykler som bildas av varje färgpar. Därför, bland kubiska grafer, är snarkarna de enda möjliga motexemplen. Mer generellt är snarks det svåra fallet för denna gissning: om det är sant för snarks så är det sant för alla grafer. I detta sammanhang antog Branko Grünbaum att ingen snark kunde bäddas in på en yta på ett sådant sätt att alla ytor är enkla cykler och så att varannan sida antingen är osammanhängande eller bara delar en enda kant ; om någon snark hade en sådan inbäddning, skulle dess ansikten bilda ett cykeldubbelhölje. Ett motexempel till Grünbaums gissning hittades dock av Martin Kochol.
Att avgöra om en given cykliskt 5-kopplad kubikgraf är 3-kantsfärgbar är NP-komplett . Därför är det co-NP-komplett att avgöra om en graf är en snark .
Snark gissning
WT Tutte förmodade att varje snark har Petersen-grafen som en moll . Det vill säga, han förmodade att den minsta snarken, Petersen-grafen, kan bildas från vilken annan snark som helst genom att dra ihop vissa kanter och ta bort andra. På motsvarande sätt (eftersom Petersen-grafen har maximal grad tre) har varje snark en subgraf som kan bildas från Petersen-grafen genom att dela upp några av dess kanter . Denna gissning är en förstärkt form av fyrafärgssatsen , eftersom varje graf som innehåller Petersen-grafen som moll måste vara icke-plan. 1999 Neil Robertson , Daniel P. Sanders , Paul Seymour och Robin Thomas ett bevis på denna gissning. Steg mot detta resultat har publicerats, men från och med 2022 förblir det fullständiga beviset opublicerat. Se Hadwiger-förmodan för andra problem och resultat som relaterar graffärgning till grafiska mindreåriga.
Tutte antog också en generalisering till godtyckliga grafer: varje brolös graf utan Petersen-moll har ingenstans noll 4-flöde . Det vill säga, kanterna på grafen kan tilldelas en riktning och ett tal från mängden {1, 2, 3}, så att summan av de inkommande talen minus summan av de utgående talen vid varje vertex är delbar med fyra . Som Tutte visade, för kubiska grafer finns en sådan uppgift om och bara om kanterna kan färgas med tre färger, så gissningen skulle följa av snarkförmodan i detta fall. Att bevisa snarkförmodan skulle dock inte lösa frågan om förekomsten av 4-flöden för icke-kubiska grafer.