Gyufagráf

(Gyufaszálgráf szócikkből átirányítva)

A geometriai gráfelmélet területén a gyufaszálgráf vagy gyufagráf olyan gráf, ami síkba rajzolható olyan módon, hogy élei egység hosszúságú egyenes szakaszok, melyek nem metszik egymást. Tehát egy olyan gráf, ami egyszerre egységtávolsággráf és síkgráf. Informálisan, a gyufagráfok elkészíthetők gyufaszálak egymás mellé helyezésével egy sík asztallapon, innen is kapták nevüket.[1]

Harborth-gráf
Harborth graph vector.svg

Csúcsok száma 52
Élek száma 104
Sugár 6
Átmérő 9
Derékbőség 3
Automorfizmusok 4

Reguláris gyufaszálgráfokSzerkesztés

A gyufaszálgráfok kutatásának jelentős része a reguláris gráfokkal foglalkozott, melyeknél minden csúcsponthoz ugyanannyi él kapcsolódik, tehát a csúcsok fokszáma megegyezik – ezt ilyenkor a gráf fokszámának is hívják.

Ismertek reguláris gyufaszálgráfok egészen 4-es fokszámig. Az 1, 2, illetve 3 csúcsú teljes gráfok (egyetlen csúcspont, egyetlen él és egy háromszög) mind 0-, 1-, illetve 2-reguláris gyufaszálgráfok. A legkisebb 3-reguláris gyufaszálgráf előállítható két gyémántgráf(wd) egymáshoz illesztésével oly módon, hogy a megfelelő csúcspontok egységnyi távolságra legyenek egymástól.[1]

1986-ban Heiko Harborth bemutatta a nevét viselő Harborth-gráfot. A 104 éllel és 52 csúccsal rendelkező Harborth-gráf a legkisebb ismert 4-reguláris gyufaszálgráf.[2] Ez egy merev gráf.[3]

Az az erősen elfogadott feltételezés, hogy nem létezik négynél magasabb fokszámú reguláris gyufaszálgráf,[4] de az eddigi bizonyítások mindegyikében találtak hibát.

A legkisebb háromszögmentes (derékbőség ≥ 4) 3-reguláris gyufagráf 20 csúcspontú, amit Kurz és Mazzuoccolo igazoltak.[5] Ugyanők adták meg a legkisebb 5 derékbőségű 3-reguláris gyufagráfot (180 csúcsponttal).

 
A minimális 3-reguláris gyufagráf előállítása két gyémántgráf egymáshoz illesztésével

Számítási bonyolultságSzerkesztés

Annak eldöntése, hogy adott irányítatlan síkgráf lerajzolható-e gyufagráfként, NP-nehéz probléma.[6][7] Az ezt bizonyító referenciák azonban nem mutatják meg, hogy a probléma az NP-be tartozik-e, továbbá a síkba nem rajzolható egységtávolsággráfok felismerésének kapcsolódó problémája teljes az existential theory of the reals(wd) nagyobb osztályára nézve. Annak eldöntése, hogy a gyufagráfok felismerése az NP-hez tartozik (és akkor NP-teljes) vagy csak  -teljes, netán valahova a két szélsőérték közé esik, egyelőre nyitott kérdés.[8] (Kurz 2014) ad néhány gyorsan vizsgálható, szükséges feltételt a gráfok gyufagráfságának vizsgálatára, de ezek nem elégséges feltételek: egy gráf átmehet Kurz tesztjein és még mindig nem biztos, hogy gyufagráf.[9]

Annak eldöntése, hogy egy gyufagráf rendelkezik-e Hamilton-körrel szintén NP-teljes, még akkor is, ha a gráf csúcspontjainak egész számok a koordinátái, amiket megadunk a megoldáshoz.[10]

Kombinatorikai leszámlálásSzerkesztés

A különböző (nem izomorf) gyufagráfok számát sikerült meghatározni 1, 2, 3 … 10 élig; ezek:

1, 1, 3, 5, 12, 28, 74, 207, 633, 2008 (A066951 sorozat az OEIS-ben).[11][12]

Például a három gyufa segítségével előállítható három különböző gráf a karom (S3), a háromszöggráf (C3 vagy K3) és a háromélű útgráf (P3).

Gráfok speciális osztályaiSzerkesztés

A gráfábrázolás során az egyenlőre rajzolt élhosszúságokat régóta kedvezőnek tekintették,[13] és egyes specifikus síkgráfosztályokat minden esetben meg lehet rajzolni teljesen azonos élhosszúságokkal.

Például minden fa megrajzolható olyan módon, hogy ha a fa leveleihez vezető éleket végtelen félegyenessé hosszabbítanánk, a rajz a síkot konvex sokszög alakú régiókra osztaná, anélkül, hogy a sugarak egymást metszenék. Egy ilyen lerajzolásnál, ha az élek hosszát tetszőlegesen változtatjuk, de irányát nem, a rajzolás síkbéli marad. Így megtehetjük azt is, hogy az éleket azonos hosszúra rajzoljuk, ezzel megvalósítva a tetszőleges fa gyufagráffá alakítását.[14]

 
Négyszöggráf megrajzolása gyufagráfként

Hasonló tulajdonságúak a négyszöggráfok.[15]

FordításSzerkesztés

  • Ez a szócikk részben vagy egészben a Matchstick graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.

JegyzetekSzerkesztés

  1. a b Weisstein, Eric W.: {{{title}}} (angol nyelven). Wolfram MathWorld
  2. Harborth, Heiko (1994), "Match sticks in the plane", in 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, pp. 281–288. As cited in: Weisstein, Eric W.: {{{title}}} (angol nyelven). Wolfram MathWorld
  3. Gerbracht, E. H.-A. (2006), Minimal polynomials for the coordinates of the Harborth graph
  4. Kurz, Sascha & Pinchasi, Rom (2011), "Regular matchstick graphs", American Mathematical Monthly 118 (3): 264–267, DOI 10.4169/amer.math.monthly.118.03.264.
  5. Kurz, Sascha & Mazzuoccolo, Giuseppe (2010), "3-regular matchstick graphs with given girth", Geombinatorics 19: 156–175.
  6. Eades, Peter & Wormald, Nicholas C. (1990), "Fixed edge-length graph drawing is NP-hard", Discrete Applied Mathematics 28 (2): 111–134, DOI 10.1016/0166-218X(90)90110-X.
  7. 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:10.7155/jgaa.00145, <http://www.cs.brown.edu/sites/jgaa/accepted/2007/CabelloDemaineRote2007.11.1.pdf>.
  8. Schaefer, Marcus (2013), "Realizability of graphs and linkages", in Pach, János, Thirty Essays on Geometric Graph Theory, Springer, pp. 461–482, DOI 10.1007/978-1-4614-0110-0_24.
  9. Kurz, Sascha (2014), Fast recognition of planar non unit distance graphs.
  10. Itai, Alon; Papadimitriou, Christos H. & Szwarcfiter, Jayme Luiz (1982), "Hamilton paths in grid graphs", SIAM Journal on Computing 11 (4): 676–686, DOI 10.1137/0211056.
  11. Salvia, Raffaele (2013), A catalog for matchstick graphs
  12. Matchstick graphs with up to 10 edges, 2015
  13. Fruchterman, Thomas M. J. & Reingold, Edward M. (1991), "Graph Drawing by Force-Directed Placement", Software – Practice & Experience (Wiley) 21 (11): 1129–1164, DOI 10.1002/spe.4380211102.
  14. Carlson, Josiah & Eppstein, David (2006), "Trees with convex faces and optimal angles", in Kaufmann, Michael & Wagner, Dorothea, Proc. 14th Int. Symp. Graph Drawing, vol. 4372, Lecture Notes in Computer Science, Springer-Verlag, pp. 77–88, DOI 10.1007/978-3-540-70904-6_9.
  15. Eppstein, David & Wortman, Kevin A. (2011), "Optimal angular resolution for face-symmetric drawings", J. Graph Algorithms & Applications 15 (4): 551–564, DOI 10.7155/jgaa.00238.