Penny graf
I geometrisk grafteori är en penny graph en kontaktgraf av enhetscirklar . Den bildas av en samling enhetscirklar som inte korsar varandra, genom att skapa en vertex för varje cirkel och en kant för varje par av tangentcirklar . Cirklarna kan representeras fysiskt av pennies , arrangerade utan överlappning på en plan yta, med en spets för varje penny och en kant för varje två pennies som berör.
Penny-grafer har också kallats enhetsmyntgrafer , eftersom de är myntgrafer som bildas av enhetscirklar. Om varje vertex representeras av en punkt i mitten av sin cirkel, kommer två hörn att ligga intill om och endast om deras avstånd är det minsta avståndet mellan alla par av punkter. Därför har penny-grafer också kallats grafer för minimiavstånd , grafer för minsta avstånd , eller grafer för närmaste par . På liknande sätt, i en ömsesidig närmaste granne-graf som länkar ihop par av punkter i planet som är varandras närmaste grannar , är varje ansluten komponent en penny-graf, även om kanter i olika komponenter kan ha olika längd.
Varje penny-graf är en enhetsskiva-graf och en tändsticksgraf . Liksom plana grafer mer allmänt lyder de fyrafärgssatsen , men denna sats är lättare att bevisa för penny-grafer. Att testa om en graf är en penny-graf, eller hitta dess maximala oberoende uppsättning , är NP-svårt ; dock är både övre och nedre gränser kända för storleken på den maximala oberoende uppsättningen, högre än de gränser som är möjliga för godtyckliga plana grafer.
Egenskaper
Antal kanter
Varje vertex i en penny-graf har högst sex angränsande hörn; här är siffran sex kysstalet för cirklar i planet. Pengarna på gränsen till det konvexa skrovet har dock färre grannar. Räkna mer exakt denna minskning av grannar för gränspenningar leder till en exakt gräns för antalet kanter i en penny-graf: en penny-graf med n hörn har som mest
Vad är det maximala antalet kanter i en triangelfri penny-graf?
Genom att ordna slantarna i ett fyrkantigt rutnät , eller i form av vissa kvadratgrafer , kan man bilda triangelfria penny-grafer vars antal kanter är minst
Färg
Varje penny-graf innehåller en vertex med högst tre grannar. Till exempel kan en sådan vertex hittas i ett av hörnen av det konvexa skrovet av cirkelcentrum. Därför har penny grafer degeneration högst tre. Baserat på detta kan man bevisa att deras graffärger kräver högst fyra färger, mycket lättare än beviset för den mer allmänna fyrfärgssatsen . Men trots deras begränsade struktur finns det penny-grafer som fortfarande kräver fyra färger.
Analogt är degenerationen för varje triangelfri penny-graf högst två. Varje sådan graf innehåller en vertex med högst två grannar, även om det inte alltid är möjligt att hitta denna vertex på det konvexa skrovet. Utifrån detta kan man bevisa att de kräver högst tre färger, lättare än beviset för den mer allmänna Grötzschs sats att triangelfria plana grafer är 3-färgbara.
Oberoende uppsättningar
En maximal oberoende uppsättning i en penny-graf är en delmängd av pennies, varav inte två berör varandra. Att hitta maximala oberoende uppsättningar är NP-svårt för godtyckliga grafer och förblir NP-hårt på penny-grafer. Det är ett exempel på maximal disjunkt uppsättning , där man måste hitta stora delmängder av icke-överlappande områden i planet. Men som med plana grafer mer allmänt, ger Bakers teknik ett polynom-tidsapproximationsschema för detta problem.
Vilken är den största så att varje -vertex penny-graf har en oberoende uppsättning storlek ?
1983 bad Paul Erdős om det största antalet c så att varje n -vertex penny-graf har en oberoende uppsättning av åtminstone cn- hörn. Det vill säga, om vi placerar n pennies på en plan yta bör det finnas en delmängd av cn av penniesna som inte berör varandra. Genom fyrfärgssatsen, c ≥ 1/4 , och den förbättrade bundna c ≥ 8/31 ≈ 0,258 bevisades av Swanepoel. I den andra riktningen bevisade Pach och Tóth att c ≤ 5/16 = 0,3125 . Från och med 2013 förblev dessa de bästa gränserna kända för detta problem.
Beräkningskomplexitet
Att konstruera en penny-graf från platserna för dess n cirklar kan utföras som en instans av det närmaste paret av poängproblem , med värsta tänkbara tid O ( n log n ) eller (med slumpmässig tid och med användning av golvfunktionen ) förväntad tid O ( n ) . En alternativ metod med samma värsta tänkbara tid är att konstruera Delaunay-trianguleringen eller närmaste granngrafen för cirkelcentrumen (som båda innehåller penny-grafen som en subgraf) och sedan testa vilka kanter som motsvarar cirkeltangenser.
Men om en graf ges utan geometriska positioner för dess hörn, är det NP-svårt att testa om den kan representeras som en penny-graf . Den förblir NP-hård även när den givna grafen är ett träd . På liknande sätt är det NP-svårt att testa om en graf kan representeras som en tredimensionell ömsesidig närmaste granne.
Det är möjligt att utföra vissa beräkningsuppgifter på riktade penny-grafer, som att testa om en vertex kan nå en annan, i polynomtid och väsentligt mindre än linjärt rymd, givet en inmatning som representerar dess cirklar i en form som tillåter grundläggande beräkningsuppgifter som att testa angränsande och hitta skärningspunkter för cirklarna med axelparallella linjer.
Relaterade graffamiljer
Penny-grafer är ett specialfall av myntgraferna (grafer som kan representeras av tangenser av icke-korsande cirklar med godtyckliga radier). Eftersom myntgraferna är desamma som de plana graferna är alla pennygrafer plana. Penny-graferna är också enhetsskivor ( enhetscirklarnas skärningsdiagram ), enhetsavståndsgrafer (grafer som kan ritas med alla kanter lika långa, vilket tillåter korsningar) och tändsticksgrafer (grafer som kan ritas i planet med lika långa raka kanter och inga kantkorsningar).