Gyufagráf

A Wikipédiából, a szabad enciklopédiából
Harborth-gráf
Csúcsok száma52
Élek száma104
Sugár6
Átmérő9
Derékbőség3
Automorfizmusok4

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. (Vigyázat, ha egy gráf egyszerre egységtávolsággráf és síkgráf, akkor nem feltétlenül gyufagráf, hiszen lehet, hogy eltér a két reprezentáció, mint például a Moser-rokka esetében.)[1] 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.[2]

Reguláris gyufaszálgráfok[szerkeszté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.[2]

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.[3] Ez egy merev gráf.[4]

Nem létezik négynél magasabb fokszámú reguláris gyufaszálgráf,[5] minden csúcsú gyufagráfnak legalább 4-nél kisebb fokszámú csúcsa van.[6]

A legkisebb háromszögmentes (derékbőség ≥ 4) 3-reguláris gyufagráf 20 csúcspontú, amit Kurz és Mazzuoccolo igazoltak.[7] 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ág[szerkesztés]

Annak eldöntése, hogy adott irányítatlan síkgráf lerajzolható-e gyufagráfként, NP-nehéz probléma.[8][9] 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.[10] (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.[11]

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.[12]

Kombinatorikai leszámlálás[szerkeszté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).[13][14]

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ályai[szerkesztés]

A gráfábrázolás során az egyenlőre rajzolt élhosszúságokat régóta kedvezőnek tekintették,[15] é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.[16]

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

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

Fordítás[szerkeszté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. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek[szerkesztés]

  1. ↑ Gervacio, Severino V. (2008). „Planar unit-distance graphs having planar unit-distance complement”. Discrete Mathematics 308 (10), 1973–1984. o. DOI:10.1016/j.disc.2007.04.050.  
  2. ↑ a b Weisstein, Eric W.: Gyufagráfok (angol nyelven). Wolfram MathWorld
  3. ↑ 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.: Harborth-gráf (angol nyelven). Wolfram MathWorld
  4. ↑ Gerbracht, E. H.-A. (2006), Minimal polynomials for the coordinates of the Harborth graph
  5. ↑ Kurz, Sascha (2011). „Regular matchstick graphs”. American Mathematical Monthly 118 (3), 264–267. o. DOI:10.4169/amer.math.monthly.118.03.264.  
  6. ↑ (2022) „The number of small-degree vertices in matchstick graphs”.  
  7. ↑ (2010) „3-regular matchstick graphs with given girth”. Geombinatorics 19, 156–175. o.  
  8. ↑ (1990) „Fixed edge-length graph drawing is NP-hard”. Discrete Applied Mathematics 28 (2), 111–134. o. DOI:10.1016/0166-218X(90)90110-X.  .
  9. ↑ (2007) „Planar embeddings of graphs with specified edge lengths”. Journal of Graph Algorithms and Applications 11 (1), 259–276. o. DOI:10.7155/jgaa.00145.  .
  10. ↑ Schaefer, Marcus (2013). „Thirty Essays on Geometric Graph Theory”, 461–482. o, Kiadó: Springer. DOI:10.1007/978-1-4614-0110-0_24.  .
  11. ↑ Kurz, Sascha (2014). „Fast recognition of planar non unit distance graphs”.  .
  12. ↑ (1982) „Hamilton paths in grid graphs”. SIAM Journal on Computing 11 (4), 676–686. o. DOI:10.1137/0211056.  .
  13. ↑ Salvia, Raffaele (2013), A catalog for matchstick graphs
  14. ↑ Matchstick graphs with up to 10 edges, 2015
  15. ↑ 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.
  16. ↑ 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.
  17. ↑ 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.
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Gyufagráf&oldid=26712375”