Egységérmegráf

11 csúccsal és 19 éllel rendelkező pennygráf, melynek színezéséhez, ahogy az ábrán is, legalább négy színre van szükség.

A fenti gráf „megvalósítása” egycentesekkel

A matematika, azon belül a geometriai gráfelmélet területén egy egységérmegráf vagy pennygráf (penny graph, unit coin graph) egységkörök érintőgráfja, vagyis egyforma érmék által alkotott érmegráf. Olyan irányítatlan gráf tehát, melyek csúcsainak az egymást nem metsző egységkörök felelnek meg, két csúcsa pedig akkor van összekötve, ha a megfelelő egységkörök éppen érintő helyzetűek. Más megfogalmazásban egy asztallapon átfedés nélkül elhelyezett egypennysek alkotta gráf, ahol minden érme a gráf egy csúcsa, és az érintkező egypennysekhez tartozó csúcsokat él köti össze.

Ha a körök középpontjába helyezzük el az őket jelképező csúcsokat, akkor két csúcs pontosan akkor szomszédos, ha távolságuk a pontpárok közötti minimális távolsággal egyezik meg. Ezért az egységérmegráfok minimálistávolság-gráfoknak (minimum-distance graphs) smallest-distance graphs, vagy legközelebbipár-gráfoknak (closest-pairs graphs) is nevezhetők.

Minden pennygráf egységkörlapgráf és gyufagráf. Síkgráfként érvényes rájuk a négyszíntétel, ami rájuk nézve könnyebben bizonyítható. Annak a tesztelése, hogy adott gráf egységérmegráf-e, NP-nehéz feladat, ahogy a maximális elemszámú független csúcshalmaz megtalálása is; utóbbi méretére azonban alsó és felső korlátok is ismertek.

Számítási bonyolultság

Az egységérmegráf előállítása az Sablon:Mvar kör ismeretében felfogható az egymáshoz legközelebbi pontpár megkeresése probléma eseteként, ami legfeljebb Sablon:Math idő alatt megoldható vagy (randomizált időben és az egészrész függvény használatával) Sablon:Math várható időben. Egy másik megoldás, ami legrosszabb esetben ugyanannyi idő alatt fut le, hogy elvégezzük a körök középpontjainak Delaunay-háromszögelését vagy létrehozzuk a legközelebbi szomszéd gráfot (mindkettő részgráfként tartalmazza az egységérmegráfot) majd vizsgáljuk, hogy melyik élek felelnek meg érintő körnek.

Annak tesztelése, hogy adott gráf pennygráf-e, még akkor is NP-teljes probléma, ha a gráf fa.

Kapcsolódó gráfcsaládok

A $H_3^5$ Hanoi-gráf egységérmegráfként (a fekete korongok érintőgráfja)

Az egységérmegráfok az érmegráfok (a sík egymást nem metsző, tetszőleges sugarú köreinek érintőviszonyai által meghatározott gráfok) speciális esetei. Mivel a síkgráfok és az érmegráfok megegyeznek, természetesen az összes pennygráf is síkgráf. Az egységérmegráfok továbbá egységkörök metszetgráfjai (egységkörgráf), egységtávolsággráfok (azonos hosszúságú élekkel lerajzolható gráfok, a metszést is megengedve), azon belül gyufagráfok (azonos hosszúságú, egymást nem metsző élekkel lerajzolható gráfok). A $H_3^n$ Hanoi-gráfok egységérmegráfok.

Élek száma

A pennygráf minden csúcsának legfeljebb hat szomszédos csúcsa lehet; itt a hat éppen a sík köreinek csókszáma. Ennél kevesebb szomszédja van azoknak az érméknek, melyek közepe kevesebb mint három egység (másfél átmérő) távolságra van az érmék konvex burkától. Ennek az ötletnek precíz kidolgozásával megmutatható, hogy az Sablon:Mvar csúcsú egységérmegráf éleinek száma legfeljebb

$\lfloor 3n-\sqrt{12n-3}\rfloor$.

A háromszögrács-elrendezésben elhelyezett pennygráfok pontosan el is érik ezt az élszámot. Sablon:Megoldatlan A pénzérméket négyzetrács, vagy bizonyos négyszöggráfok formájában elrendezve olyan háromszögmentes egységérmegráfok alakíthatók ki, melyek éleinek száma legalább

$\lfloor 2n-2\sqrt{n}\rfloor .$

Swanepoel arra is felfigyelt, hogy az Euler-karakterisztika implikálja, hogy a háromszögmentes pennygráfok legfeljebb Sablon:Math éllel rendelkeznek. Véleménye szerint az alsó korlát éles, ennek bizonyítása azonban még nem sikerült, sem cáfolata jobb korlát előállításával.

Színezés

Minden pennygráfban van olyan csúcs, aminek legfeljebb három szomszédja van. Ilyen csúcsot lehet találni az érmék középpontjai konvex burkának sarkainál, vagy a két egymástól legtávolabbi érmeközéppont között. Ezért az egységérmegráfok degeneráltsága legfeljebb három lehet (a háromszögmenteseké 2). Ebből kiindulva az általános négyszíntételnél sokkal könnyebben bizonyítható, hogy színezésükhöz négy szín mindig elégséges. Korlátozott szerkezetük ellenére léteznek olyan pennygráfok, melyek színezéséhez szükség is van mind a négy színre.

Független csúcshalmazok

A maximális elemszámú független csúcshalmaz az érmék olyan, lehető legnagyobb részhalmaza, melyben semelyik két érem nem érinti egymást. A maximális elemszámú független csúcshalmazok megkeresése általános gráfok esetében NP-nehéz feladat, és egységérmegráfokra is az marad. Ez a maximális diszjunkt halmaz problémájának egy esete; annál a sík minél nagyobb egymást át nem fedő régióit kell megkeresni. Ahogy síkgráfoknál is, a Baker-technika itt is polinomiális approximációs séma a problémához. Sablon:Megoldatlan 1983-ban Erdős Pál tette fel a kérdést, hogy mi a legnagyobb olyan Sablon:Mvar szám, melyre minden Sablon:Mvar-csúcsú pennygráf legalább Sablon:Mvar csúcsból álló független csúcshalmazzal rendelkezik, tehát az Sablon:Mvar pénzérméből Sablon:Mvar darab kölcsönösen nem érinti egymást. A négyszíntételből nyilvánvaló, hogy Sablon:Math, Swanepoel ezt javította a Sablon:Math értékre, A másik irányban Pach János és Tóth Géza igazolta, hogy Sablon:Math. Jelenleg (2013) ezek a legjobb ismert korlátok az Erdős-féle problémafelvetésre.

Fordítás

• Sablon:Fordítás