Gyufagráf
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 | |
 | |
| 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).
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:
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]
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. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
JegyzetekSzerkesztés
- ↑ a b Weisstein, Eric W.: {{{title}}} (angol nyelven). Wolfram MathWorld
- ↑ 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
- ↑ 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 10.4169/amer.math.monthly.118.03.264.
- ↑ 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 10.1016/0166-218X(90)90110-X.
- ↑ 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>.
- ↑ 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.
- ↑ Kurz, Sascha (2014), Fast recognition of planar non unit distance graphs.
- ↑ 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.
- ↑ Salvia, Raffaele (2013), A catalog for matchstick graphs
- ↑ Matchstick graphs with up to 10 edges, 2015
- ↑ 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.
- ↑ 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.
- ↑ 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.