Gyufagráf

Sablon:Gráf infobox 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.) 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.

Reguláris gyufaszálgráfok

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áfSablon:Wd egymáshoz illesztésével oly módon, hogy a megfelelő csúcspontok egységnyi távolságra legyenek egymástól.

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. Ez egy merev gráf.

Nem létezik négynél magasabb fokszámú reguláris gyufaszálgráf, minden $n$ csúcsú gyufagráfnak legalább $\mathrm{\Omega }(\sqrt{n})$ 4-nél kisebb fokszámú csúcsa van.

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

Annak eldöntése, hogy adott irányítatlan síkgráf lerajzolható-e gyufagráfként, NP-nehéz probléma. 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 realsSablon: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 $\mathrm{\exists }ℝ$-teljes, netán valahova a két szélsőérték közé esik, egyelőre nyitott kérdés. Sablon:Harvtxt 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.

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.

Kombinatorikai leszámlálá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 Sablon:OEIS.

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

Gráfok speciális osztályai

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

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

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

Fordítás

• Sablon:Fordítás