Tändsticksgraf
| Harborth graf | |
|---|---|
 | |
| Vertices | 52 |
| Kanter | 104 |
| Radie | 6 |
| Diameter | 9 |
| Omkrets | 3 |
| Tabell över grafer och parametrar | |
| 3-vanlig omkrets-5 tändsticksdiagram | |
|---|---|
 | |
| Vertices | 54 |
| Kanter | 81 |
| Omkrets | 5 |
| Tabell över grafer och parametrar | |
Inom geometrisk grafteori , en gren av matematiken, är en tändsticksgraf en graf som kan ritas i planet på ett sådant sätt att dess kanter är linjesegment med en längd som inte korsar varandra. Det vill säga att det är en graf som har en inbäddning som samtidigt är en enhetsdistansgraf och en plan graf . Av denna anledning har tändsticksgrafer också kallats plana enhetsavståndsgrafer . Informellt kan tändsticksdiagram göras genom att placera icke-korsande tändstickor på en plan yta, därav namnet.
Vanliga tändsticksgrafer
Mycket av forskningen om tändsticksgrafer har gällt vanliga grafer , där varje vertex har samma antal grannar. Detta tal kallas graden av grafen.
Vanliga tändsticksgrafer kan ha grad 0, 1, 2, 3 eller 4. De kompletta graferna med en, två och tre hörn (en enda vertex, en enda kant och en triangel) är alla tändsticksgrafer och är 0-, 1- respektive 2-ordinarie. Den minsta 3-regelbundna tändsticksgrafen bildas av två kopior av diamantgrafen placerade på ett sådant sätt att motsvarande hörn är på enhetsavstånd från varandra; dess tvådelade dubbla lock är den 8-korsade prismagrafen.
1986 presenterade Heiko Harborth grafen som blev känd som Harborth Graph . Den har 104 kanter och 52 hörn, och är det minsta kända exemplet på en 4- regelbunden tändsticksgraf. Det är en stel graf .
Varje 4-vanlig tändsticksgraf innehåller minst 20 hörn. Exempel på 4-regelbundna tändsticksgrafer är för närvarande kända för alla antal hörn ≥ 52 förutom 53, 55, 56, 58, 59, 61 och 62. Graferna med 54, 57, 65, 67, 73, 74, 77 och 85 hörn publicerades första gången 2016. För 52, 54, 57, 60 och 64 hörn är bara ett exempel känt. Av dessa fem grafer är bara den med 60 hörn flexibel, de andra fyra är stela.
Det är inte möjligt för en vanlig tändsticksgraf att ha grader större än fyra. Mer starkt, varje -vertex matchstick-graf har hörn av grad fyra eller mindre. Den minsta 3-regelbundna tändsticksgrafen utan trianglar (omkrets ≥ 4) har 20 hörn, vilket bevisats av Kurz och Mazzuoccolo. Det minsta kända exemplet på en 3-regelbunden tändsticksgraf med omkrets 5 har 54 hörn och presenterades först av Mike Winkler 2019.
Beräkningskomplexitet
Det är NP-svårt att testa om en given oriktad plan graf kan realiseras som en tändsticksgraf. Mer exakt är detta problem komplett för den existentiella teorin om verkligheten . Kurz (2011) tillhandahåller några lätttestade nödvändiga kriterier för att en graf ska vara en tändsticksgraf, men dessa är inte heller tillräckliga kriterier: en graf kan klara Kurz tester och ändå inte vara en tändsticksgraf.
Det är också NP-komplett att avgöra om en tändsticksgraf har en Hamiltonsk cykel , även när grafens hörn alla har heltalskoordinater som ges som en del av inmatningen till problemet.
Kombinatorisk uppräkning
Antalet distinkta (icke-isomorfa) tändsticksdiagram är kända för 1, 2, 3, ... upp till tio kanter; dom är:
Till exempel de tre olika graferna som kan göras med tre tändstickor är en klo , en triangelgraf och en trekantsbana .
Särskilda klasser av grafer
Enhetlighet av kantlängder har länge setts som en önskvärd egenskap vid grafritning , och vissa specifika klasser av plana grafer kan alltid ritas med helt enhetliga kanter.
Varje träd kan ritas på ett sådant sätt att om trädets lövkanter ersattes av oändliga strålar, skulle ritningen dela upp planet i konvexa polygonala områden, utan några korsningar. För en sådan ritning, om längden på varje kant ändras godtyckligt, utan att ändra kantens lutning, kommer ritningen att förbli plan. I synnerhet är det möjligt att välja att alla kanter ska ha lika långa, vilket resulterar i en realisering av ett godtyckligt träd som en tändsticksgraf.
En liknande egenskap gäller för squaregraphs , de plana graferna som kan ritas i planet på ett sådant sätt att varje avgränsad yta är en fyrhörning och varje vertex antingen ligger på den obegränsade ytan eller har minst fyra grannar. Dessa grafer kan ritas med alla ytor parallellogram, på ett sådant sätt att om en delmängd av kanter som alla är parallella med varandra förlängs eller förkortas samtidigt så att de fortsätter att ha samma längd, så kan ingen korsning införas. I synnerhet är det möjligt att normalisera kanterna så att de alla har samma längd, och erhålla en realisering av vilken kvadratgraf som helst som en tändsticksgraf.
Relaterade klasser av grafer
Varje tändsticksgraf är en enhetsdistansgraf . Penny-grafer är de grafer som kan representeras av tangenser av icke-överlappande enhetscirklar. Varje penny-graf är en tändsticksgraf. Vissa tändsticksgrafer (som den kubiska tändsticksgrafen med åtta vertex i den första illustrationen) är dock inte pennygrafer, eftersom att realisera dem som en tändsticksgraf gör att vissa icke-intilliggande hörn är närmare varandra än enhetsavståndet.