Inom geometrisk grafteori, en gren inom matematiken, är en tändsticksgraf en graf som kan ritas i planet på ett sådant sätt att dess kanter är räta linjer med längden ett som inte korsar varandra. Det vill säga att det är en graf som samtidigt är en enhetsdistansgraf och en planär graf. Man kan informellt säga att en tändsticksgraf kan åstadkommas genom att lägga ut tändstickor på en plan yta, härav namnet.
Reguljära tändsticksgrafer Mycket av forskningen kring tändsticksgrafer har behandlat reguljära grafer, det vill säga grafer vars alla hörn har samma grad.
Man känner till reguljära tändsticksgrafer upp till grad 4. De kompletta graferna med ett, två och tre hörn (ett ensamt hörn, en ensam kant och en triangel) är alla tändsticksgrafer och är 0-, 1- respektive 2-reguljära. Den minsta 3-reguljära tändsticksgrafen byggs upp av två diamantgrafer placerade på ett sådant sätt att hörnen av grad två i vardera diamantgrafen ligger på avståndet ett från varandra och är förbundna med kanter (se figur).
År 1986 presenterade Heiko Harborth den graf som skulle komma att bära hans namn: Harborthgrafen. Med 52 hörn och 104 kanter är det den minsta kända 4-reguljära tändsticksgrafen.. As cited in: Det är en rigid graf.
Det är möjligt att en tändsticksgraf kan ha en grad som är högre än fyra..
Den minsta 3-reguljära tändsticksgrafen som saknar trianglar (minsta cykel ≥ 4) har 20 noder, vilket visats av Sascha Kurz och Giuseppe Mazzuoccolo,. som också presenterade det minsta kända exemplet på en 3-reguljär tändsticksgraf i vilka minsta cykeln har längden fem (180 hörn).
Beräkningskomplicitet Det är NP-svårt att avgöra huruvida en oriktad planär graf kan åstadkommas som en tändsticksgraf...
Kombinatorisk enumeration Antalet distinkta (ickeisomorfa) tändsticksgrafer är känt för 1, 2, 3, .... upp till nio kanter - dessa antal är:
1, 1, 3, 5, 12, 28, 74, 207, 633
Referenser
Kategori:Grafteori