Egységérmegráf

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^[1]) 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.^[2] 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)^[3] smallest-distance graphs,^[4] vagy legközelebbipár-gráfoknak (closest-pairs graphs)^[5] 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 $n$ kör ismeretében felfogható az egymáshoz legközelebbi pontpár megkeresése probléma eseteként, ami legfeljebb $O (n log n)$ idő alatt megoldható^[5] vagy (randomizált időben és az egészrész függvény használatával) $O (n)$ várható időben.^[6] 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)^[5] 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.^[7]

Kapcsolódó gráfcsaládok

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.^[2] Mivel a síkgráfok és az érmegráfok megegyeznek,^[8]^[9] 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 $n$ csúcsú egységérmegráf éleinek száma legfeljebb

\left\lfloor 3n-{\sqrt {12n-3}}\right\rfloor

.

A háromszögrács-elrendezésben elhelyezett pennygráfok pontosan el is érik ezt az élszámot.^[10]^[11]^[12]

A matematika megoldatlan problémája:

Mi egy háromszögmentes egységérmegráf éleinek maximális száma?

(A matematika további megoldatlan problémái)

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

\left\lfloor 2n-2{\sqrt {n}}\right\rfloor .

Swanepoel arra is felfigyelt, hogy az Euler-karakterisztika implikálja, hogy a háromszögmentes pennygráfok legfeljebb $2 n - 4$ éllel rendelkeznek. Véleménye szerint az alsó korlát éles,^[13] 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^[14]). 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.^[15] 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.^[1] 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.^[16]

A matematika megoldatlan problémája:

Mi a legnagyobb

c

konstans, amire minden

n

-csúcsú pennygráfnak legalább

cn

méretű független csúcshalmaza van?

(A matematika további megoldatlan problémái)

1983-ban Erdős Pál tette fel a kérdést, hogy mi a legnagyobb olyan $c$ szám, melyre minden $n$ -csúcsú pennygráf legalább $cn$ csúcsból álló független csúcshalmazzal rendelkezik,^[17] tehát az $n$ pénzérméből $cn$ darab kölcsönösen nem érinti egymást. A négyszíntételből nyilvánvaló, hogy $c \geq 1/4$ , Swanepoel ezt javította a $c \geq 8/31 \approx 0,258$ értékre,^[18] A másik irányban Pach János és Tóth Géza igazolta, hogy $c \leq 5/16 = 0,3125$ .^[17] Jelenleg (2013) ezek a legjobb ismert korlátok az Erdős-féle problémafelvetésre.^[4]^[19]

Fordítás

Ez a szócikk részben vagy egészben a Penny 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

↑ ^a ^b Cerioli, Marcia R.; Faria, Luerbio & Ferreira, Talita O. et al. (2011), "A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation", RAIRO Theoretical Informatics and Applications 45 (3): 331–346, DOI 10.1051/ita/2011106.
↑ ^a ^b Pisanski, Tomaž & Randić, Milan (2000), "Bridges between geometry and graph theory", in Gorini, Catherine A., Geometry at Work, vol. 53, MAA Notes, Cambridge University Press, pp. 174–194. Lásd főként p. 176.
↑ Csizmadia, G. (1998), "On the independence number of minimum distance graphs", Discrete and Computational Geometry 20 (2): 179–187, DOI 10.1007/PL00009381.
↑ ^a ^b Brass, Peter; Moser, William & Pach, János (2005), Research Problems in Discrete Geometry, New York: Springer, p. 228, ISBN 978-0387-23815-9, <https://books.google.com/books?id=WehCspo0Qa0C&pg=PA228>.
↑ ^a ^b ^c Veltkamp, Remco C. (1994), "2.2.1 Closest pairs", Closed Object Boundaries from Scattered Points, vol. 885, Lecture Notes in Computer Science, Berlin: Springer-Verlag, p. 12, ISBN 3-540-58808-6, DOI 10.1007/3-540-58808-6.
↑ Khuller, Samir & Matias, Yossi (1995), "A simple randomized sieve algorithm for the closest-pair problem", Information and Computation 118 (1): 34–37, DOI 10.1006/inco.1995.1049.
↑ Bowen, Clinton; Durocher, Stephane & Löffler, Maarten et al. (2015), "Realization of simply connected polygonal linkages and recognition of unit disk contact trees", in Giacomo, Emilio Di & Lubiw, Anna, Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24–26, 2015, Revised Selected Papers, vol. 9411, Lecture Notes in Computer Science, Springer, pp. 447–459, DOI 10.1007/978-3-319-27261-0_37.
↑ (Hartsfield & Ringel 2013), Theorem 8.4.2, p. 173.
↑ Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. 88: 141–164
↑ Harborth, H. (1974), "Lösung zu Problem 664A", Elemente der Mathematik 29: 14–15. As cited by (Swanepoel 2009) and (Pach & Agarwal 1995).
↑ Pach, János & Agarwal, Pankaj K. (1995), Combinatorial Geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons, Inc., ISBN 0-471-58890-3, DOI 10.1002/9781118033203. Theorem 13.12, p. 211.
↑ Kupitz, Y. S. (1994), "On the maximal number of appearances of the minimal distance among $n$ points in the plane", Intuitive Geometry (Szeged, 1991), vol. 63, Colloq. Math. Soc. János Bolyai, North-Holland, pp. 217–244.
↑ Swanepoel, Konrad J. (2009), "Triangle-free minimum distance graphs in the plane", Geombinatorics 19 (1): 28–30, <http://personal.lse.ac.uk/SWANEPOE/swanepoel-min-dist.pdf>.
↑ Eppstein, D., "Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count", ArXiv e-prints, <https://arxiv.org/pdf/1708.05152.pdf>.
↑ Hartsfield, Nora & Ringel, Gerhard (2013), "Problem 8.4.8", Pearls in Graph Theory: A Comprehensive Introduction, Dover Books on Mathematics, Courier Corporation, pp. 177–178, ISBN 9780486315522, <https://books.google.com/books?id=VMjDAgAAQBAJ&pg=PA177>.
↑ Baker, B. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM 41 (1): 153–180, DOI 10.1145/174644.174650.
↑ ^a ^b Pach, János & Tóth, Géza (1996), "On the independence number of coin graphs", Geombinatorics 6 (1): 30–33, <https://infoscience.epfl.ch/record/129193/files/coincikk.ps>.
↑ Swanepoel, Konrad J. (2002), "Independence numbers of planar contact graphs", Discrete and Computational Geometry 28 (4): 649–670, DOI 10.1007/s00454-002-2897-y. ami a korábbi, (Csizmadia 1998)-féle $c \geq 9/35 \approx 0,257$ korlát javítása.
↑ Dumitrescu, Adrian & Jiang, Minghui (June 2013), "Computational Geometry Column 56", SIGACT News (New York, NY, USA: ACM) 44 (2): 80–87, doi:10.1145/2491533.2491550, <http://www.cs.uwm.edu/faculty/ad/column56.pdf>. Hozzáférés ideje: 2017-08-30 Archiválva 2014. november 26-i dátummal a Wayback Machine-ben Archivált másolat. [2014. november 26-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. augusztus 30.).

[cffp-1] Cerioli, Marcia R.; Faria, Luerbio & Ferreira, Talita O. et al. (2011), "A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation", RAIRO Theoretical Informatics and Applications 45 (3): 331–346, DOI 10.1051/ita/2011106.

[links-2] Pisanski, Tomaž & Randić, Milan (2000), "Bridges between geometry and graph theory", in Gorini, Catherine A., Geometry at Work, vol. 53, MAA Notes, Cambridge University Press, pp. 174–194. Lásd főként p. 176.

[csiz-3] Csizmadia, G. (1998), "On the independence number of minimum distance graphs", Discrete and Computational Geometry 20 (2): 179–187, DOI 10.1007/PL00009381.

[bmp-4] Brass, Peter; Moser, William & Pach, János (2005), Research Problems in Discrete Geometry, New York: Springer, p. 228, ISBN 978-0387-23815-9, <https://books.google.com/books?id=WehCspo0Qa0C&pg=PA228>.

[rcv-5] Veltkamp, Remco C. (1994), "2.2.1 Closest pairs", Closed Object Boundaries from Scattered Points, vol. 885, Lecture Notes in Computer Science, Berlin: Springer-Verlag, p. 12, ISBN 3-540-58808-6, DOI 10.1007/3-540-58808-6.

[6] Khuller, Samir & Matias, Yossi (1995), "A simple randomized sieve algorithm for the closest-pair problem", Information and Computation 118 (1): 34–37, DOI 10.1006/inco.1995.1049.

[7] Bowen, Clinton; Durocher, Stephane & Löffler, Maarten et al. (2015), "Realization of simply connected polygonal linkages and recognition of unit disk contact trees", in Giacomo, Emilio Di & Lubiw, Anna, Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24–26, 2015, Revised Selected Papers, vol. 9411, Lecture Notes in Computer Science, Springer, pp. 447–459, DOI 10.1007/978-3-319-27261-0_37.

[8] (Hartsfield & Ringel 2013), Theorem 8.4.2, p. 173.

[9] Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. 88: 141–164

[10] Harborth, H. (1974), "Lösung zu Problem 664A", Elemente der Mathematik 29: 14–15. As cited by (Swanepoel 2009) and (Pach & Agarwal 1995).

[11] Pach, János & Agarwal, Pankaj K. (1995), Combinatorial Geometry, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons, Inc., ISBN 0-471-58890-3, DOI 10.1002/9781118033203. Theorem 13.12, p. 211.

[12] Kupitz, Y. S. (1994), "On the maximal number of appearances of the minimal distance among $n$ points in the plane", Intuitive Geometry (Szeged, 1991), vol. 63, Colloq. Math. Soc. János Bolyai, North-Holland, pp. 217–244.

[13] Swanepoel, Konrad J. (2009), "Triangle-free minimum distance graphs in the plane", Geombinatorics 19 (1): 28–30, <http://personal.lse.ac.uk/SWANEPOE/swanepoel-min-dist.pdf>.

[14] Eppstein, D., "Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count", ArXiv e-prints, <https://arxiv.org/pdf/1708.05152.pdf>.

[15] Hartsfield, Nora & Ringel, Gerhard (2013), "Problem 8.4.8", Pearls in Graph Theory: A Comprehensive Introduction, Dover Books on Mathematics, Courier Corporation, pp. 177–178, ISBN 9780486315522, <https://books.google.com/books?id=VMjDAgAAQBAJ&pg=PA177>.

[16] Baker, B. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM 41 (1): 153–180, DOI 10.1145/174644.174650.

[pt96-17] Pach, János & Tóth, Géza (1996), "On the independence number of coin graphs", Geombinatorics 6 (1): 30–33, <https://infoscience.epfl.ch/record/129193/files/coincikk.ps>.

[18] Swanepoel, Konrad J. (2002), "Independence numbers of planar contact graphs", Discrete and Computational Geometry 28 (4): 649–670, DOI 10.1007/s00454-002-2897-y. ami a korábbi, (Csizmadia 1998)-féle $c \geq 9/35 \approx 0,257$ korlát javítása.

[19] Dumitrescu, Adrian & Jiang, Minghui (June 2013), "Computational Geometry Column 56", SIGACT News (New York, NY, USA: ACM) 44 (2): 80–87, doi:10.1145/2491533.2491550, <http://www.cs.uwm.edu/faculty/ad/column56.pdf>. Hozzáférés ideje: 2017-08-30 Archiválva 2014. november 26-i dátummal a Wayback Machine-ben Archivált másolat. [2014. november 26-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. augusztus 30.).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]