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. (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áf 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.

Az az erősen elfogadott feltételezés, hogy nem létezik négynél magasabb fokszámú reguláris gyufaszálgráf, 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.
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á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 reals 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.  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 .
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
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.

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

Fordítás

Jegyzetek

Gráfelmélet
Geometriai gráfelmélet
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észenes fokszámig . Az illetvecsúcsú teljes gráfok ( egyetlen csúcspont , egyetlen él és egy háromszög ) mind , , illetvereguláris gyufaszálgráfok . A legkisebbreguláris gyufaszálgráf előállítható két gyémántgráf 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éllel éscsúccsal rendelkező Harborth-gráf a legkisebb ismertreguláris gyufaszálgráf . Ez egy merev gráf . Az az erősen elfogadott feltételezés , hogy nem létezik négynél magasabb fokszámú reguláris gyufaszálgráf , de az eddigi bizonyítások mindegyikében találtak hibát . A legkisebb háromszögmentes ( derékbőség ≥ 4) reguláris gyufagráfcsúcspontú , amit Kurz és Mazzuoccolo igazoltak . Ugyanők adták meg a legkisebbderékbőségűreguláris gyufagráfotcsúcsponttal ) . 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 reals 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 . 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…élig ; ezek : 1, . 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 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 . Hasonló tulajdonságúak a négyszöggráfok . Fordítás Jegyzetek Gráfelmélet Geometriai gráfelmélet