Tändsticksgraf
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.[1]
Reguljära tändsticksgrafer[redigera | redigera wikitext]
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.[2] Det är en rigid graf.[3]
Det är möjligt att en tändsticksgraf kan ha en grad som är högre än fyra.[4]
Den minsta 3-reguljära tändsticksgrafen som saknar trianglar (minsta cykel ≥ 4) har 20 noder, vilket visats av Sascha Kurz och Giuseppe Mazzuoccolo,[5] 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[redigera | redigera wikitext]
Det är NP-svårt att avgöra huruvida en oriktad planär graf kan åstadkommas som en tändsticksgraf.[6][7]
Kombinatorisk enumeration[redigera | redigera wikitext]
Antalet distinkta (ickeisomorfa) tändsticksgrafer är känt för 1, 2, 3, .... upp till nio kanter - dessa antal är:
Referenser[redigera | redigera wikitext]
- ^ Weisstein, Eric W., "Tändsticksgraf", MathWorld. (engelska)
- ^ Harborth, Heiko (1994), ”Match sticks in the plane”, i Guy, R. K.; Woodrow, R. E., The Lighter Side of Mathematics: Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics and its History, Calgary, Canada, 1986, Washington, D.C.: Mathematical Association of America, s. 281–288. As cited in: Weisstein, Eric W., "Tändsticksgraf", MathWorld. (engelska)
- ^ Gerbracht, E. H.-A. (2006), Minimal polynomials for the coordinates of the Harborth graph
- ^ Kurz, Sascha; Pinchasi, Rom (2011), ”Regular matchstick graphs”, American Mathematical Monthly 118 (3): 264–267, doi:.
- ^ Kurz, Sascha; Mazzuoccolo, Giuseppe (2010), ”3-regular matchstick graphs with given girth”, Geombinatorics 19: 156–175.
- ^ Eades, Peter; Wormald, Nicholas C. (1990), ”Fixed edge-length graph drawing is NP-hard”, Discrete Applied Mathematics 28 (2): 111–134, doi:.
- ^ Cabello, Sergio; Demaine, Erik D.; Rote, Günter (2007), ”Planar embeddings of graphs with specified edge lengths”, Journal of Graph Algorithms and Applications 11 (1): 259–276, doi:, http://www.cs.brown.edu/sites/jgaa/accepted/2007/CabelloDemaineRote2007.11.1.pdf.
- ^ Salvia, Raffaele (2013), A catalog for matchstick graphs