Penny graf - Penny graph

Penny graf s 11 vrcholy a 19 hranami, který v každém vyžaduje čtyři barvy zbarvení grafu
Čtyři zbarvení výše uvedeného grafu.

v teorie geometrických grafů, a penny graf je kontaktní graf z jednotkové kruhy. To znamená, že je neorientovaný graf jehož vrcholy mohou být reprezentovány jednotkovými kruhy, aniž by se dva z těchto kruhů protínaly navzájem, a se dvěma sousedními vrcholy právě tehdy, pokud jsou reprezentovány tečné kruhy.[1] Jednoduše řečeno, jsou to grafy vytvořené uspořádáním pencí nepřekrývajícím se způsobem na rovném povrchu, vytvořením vrcholu pro každý cent a vytvořením okraje pro každý dva penny, které se dotknou.

Byly také nazývány penny grafy grafy jednotkových mincí,[2] protože oni jsou mince grafy vytvořené z kruhů jednotek.[1] Pokud je každý vrchol reprezentován bodem uprostřed jeho kružnice, budou dva vrcholy sousedit právě tehdy, pokud je jejich vzdálenost minimální vzdáleností mezi všemi dvojicemi bodů. Proto se také nazývají penny grafy grafy minimální vzdálenosti,[3] grafy nejmenší vzdálenosti,[4] nebo grafy nejbližších párů.[5] Podobně v a graf vzájemného nejbližšího souseda který spojuje dvojice bodů v rovině, které jsou navzájem nejbližší sousedé, každý připojená součást je penny graf, i když hrany v různých součástech mohou mít různé délky.[6]

Každý centový graf je a graf jednotkového disku a a zápalkový graf.Jako rovinné grafy obecněji se řídí čtyřbarevná věta, ale tato věta je pro penny grafy snadnější. Testování, zda je graf penny, nebo nalezení jeho maximální nezávislá množina, je NP-tvrdé; jak horní, tak dolní mez jsou však známy pro velikost maximální nezávislé sady.

Výpočetní složitost

Sestavení penny grafu z jeho umístění n kruhy lze provést jako instanci problém nejbližší dvojice bodů v nejhorším případě Ó(n log n)[5] nebo (s náhodným časem as použitím funkce podlahy ) očekávaný čas Ó(n).[7]Alternativní metodou se stejným časem v nejhorším případě je konstrukce Delaunayova triangulace nebo graf nejbližšího souseda středů kruhu (oba obsahují penny graf jako podgraf)[5] a poté vyzkoušejte, které hrany odpovídají tečnám kruhů.

Testování, zda je daný graf penny, je NP-tvrdé,[6] i když je daný graf a strom.[8] Podobně je NP-tvrdé také testování, zda je graf trojrozměrný graf vzájemného nejbližšího souseda.[9]

Související rodiny grafů

The Hanojský graf jako penny graf (kontaktní graf černých disků)

Penny grafy jsou zvláštním případem mince grafy (grafy, které lze znázornit tečnami neprocházejících kruhů libovolných poloměrů).[1] Protože grafy mincí jsou stejné jako rovinné grafy,[10] všechny penny grafy jsou rovinné. Penny grafy jsou také jednotkové diskové grafy (dále jen průsečíkové grafy jednotkových kruhů), grafy jednotkové vzdálenosti (grafy, které lze nakreslit se všemi hranami se stejnou délkou, umožňující křížení), a zápalkové grafy (grafy, které lze nakreslit v rovině se stejnými délkami rovných hran a bez křížení hran).

The Hanojské grafy jsou penny grafy.

Počet hran

Každý vrchol v penny grafu má nejvýše šest sousedních vrcholů; tady je číslo šest líbání číslo pro kruhy v rovině. Pence, jejichž středy jsou méně než tři jednotky od konvexní obal haléře mají méně sousedů. Na základě přesnější verze tohoto argumentu lze ukázat, že každý penny graf s n vrcholy má maximálně

hrany. Některé penny grafy, vytvořené uspořádáním penny v a trojúhelníková mřížka, mít přesně tento počet hran.[11][12][13]

Question, Web Fundamentals.svgNevyřešený problém v matematice:
Jaký je maximální počet hran v penny grafu bez trojúhelníku?
(více nevyřešených úloh z matematiky)

Uspořádáním haléře v a čtvercová mřížka, nebo v podobě určitých squaregraphs, jeden může tvořit bez trojúhelníků penny grafy, jejichž počet hran je alespoň

Swanepoel navrhl, že tato vazba je pevná.[14] Dokazování tohoto, nebo hledání lepšího vztahu, zůstává otevřené. Je známo, že počet hran může být maximálně

ale koeficient druhé odmocniny neodpovídá Swanepoelově domněnce.[15]

Zbarvení

Každý centový graf obsahuje vrchol s nejvýše třemi sousedy. Například takový vrchol lze nalézt v jednom z rohů konvexní obal středů kruhu nebo jako jeden ze dvou nejvzdálenějších středů kruhu. Proto mají penny grafy zvrhlost maximálně tři. Na základě toho lze prokázat, že jejich barvení grafů vyžadují maximálně čtyři barvy, mnohem snadněji než důkaz obecnějších čtyřbarevná věta.[16]Navzdory jejich omezené struktuře však existují penny grafy, které stále vyžadují čtyři barvy.

A bez trojúhelníků penny graf s vlastností, že se všechny penny na konvexním trupu dotýkají nejméně tří dalších pencí

Analogicky je degenerace každého pennyového grafu bez trojúhelníků maximálně dvě. Každý takový graf obsahuje vrchol s nejvýše dvěma sousedy, i když není vždy možné najít tento vrchol na konvexním trupu. Na základě toho lze dokázat, že vyžadují nejvýše tři barvy, snadněji než důkaz obecnějších Grötzschova věta že rovinné grafy bez trojúhelníků jsou 3barevné.[15]

Nezávislé sady

A maximální nezávislá množina v penny grafu je podmnožina penny, z nichž dva se navzájem nedotýkají. Nalezení maximálního počtu nezávislých sad je NP-tvrdé pro libovolné grafy a zůstává NP-tvrdé na penny grafy.[2] Jedná se o instanci maximální disjunktní sada problém, ve kterém je třeba najít velké podmnožiny nepřekrývajících se oblastí roviny. Stejně jako u plošných grafů obecně Bakerova technika poskytuje a schéma aproximace v polynomiálním čase pro tento problém.[17]

Question, Web Fundamentals.svgNevyřešený problém v matematice:
Co je největší takové, že každý -vertexový penny graf má nezávislou množinu velikostí ?
(více nevyřešených úloh z matematiky)

V roce 1983 Paul Erdős požádal o největší počet C takové, že každý n-vertex penny graph has a independent set of at least cn vrcholy.[18] Tedy pokud umístíme n haléře na rovném povrchu, měla by existovat podmnožina cn haléřů, které se navzájem nedotýkají. Podle čtyřbarevné věty, C ≥ 1/4a vylepšená vazba C ≥ 8/31 ≈ 0.258 bylo prokázáno Swanepoelem.[19] V opačném směru to Pach a Tóth dokázali C ≤ 5/16 = 0.3125.[18] Od roku 2013 zůstaly ty nejlepší hranice známé pro tento problém.[4][20]

Reference

  1. ^ A b Cerioli, Marcia R .; Faria, Luerbio; Ferreira, Talita O .; Protti, Fábio (2011), „Poznámka k maximálním nezávislým množinám a minimálním klikovým oddílům v grafech jednotkových disků a penny grafech: složitost a aproximace“, RAIRO Teoretická informatika a aplikace, 45 (3): 331–346, doi:10.1051 / ita / 2011106, PAN  2836493.
  2. ^ Csizmadia, G. (1998), „O nezávislosti počtu grafů minimální vzdálenosti“, Diskrétní a výpočetní geometrie, 20 (2): 179–187, doi:10.1007 / PL00009381, PAN  1637884.
  3. ^ A b Brass, Peter; Moser, William; Pach, János (2005), Výzkumné problémy v diskrétní geometrii, New York: Springer, str. 228, ISBN  978-0387-23815-9, PAN  2163782.
  4. ^ A b C Veltkamp, ​​Remco C. (1994), „2.2.1 Nejbližší páry“, Hranice uzavřených objektů z rozptýlených bodů, Přednášky v informatice, 885, Berlín: Springer-Verlag, s. 12, doi:10.1007/3-540-58808-6, ISBN  3-540-58808-6.
  5. ^ A b Eades, Peter; Whitesides, žalovat (1996), „Logický engine a problém realizace grafů nejbližších sousedů“, Teoretická informatika, 169 (1): 23–37, doi:10.1016 / S0304-3975 (97) 84223-5, PAN  1424926
  6. ^ Khuller, Samir; Matias, Yossi (1995), „Jednoduchý randomizovaný sítový algoritmus pro problém nejbližší dvojice“, Informace a výpočet, 118 (1): 34–37, doi:10.1006 / inco.1995.1049, PAN  1329236.
  7. ^ Bowen, Clinton; Durocher, Stephane; Löffler, Maarten; Rounds, Anika; Schulz, André; Tóth, Csaba D. (2015), „Realizace jednoduše spojených polygonálních vazeb a rozpoznávání kontaktních stromů jednotkových disků“, Giacomo, Emilio Di; Lubiw, Anna (eds.), Kreslení grafů a síťová vizualizace: 23. mezinárodní sympozium, GD 2015, Los Angeles, CA, USA, 24. – 26. Září 2015, revidované vybrané příspěvky, Přednášky z informatiky, 9411, Springer, str. 447–459, doi:10.1007/978-3-319-27261-0_37.
  8. ^ Kitching, Matthew; Whitesides, žalovat (2004), "The Three Dimensional Logic Engine", in Pach, János (vyd.), Grafická kresba, 12. mezinárodní sympozium, GD 2004, New York, NY, USA, 29. září - 2. října 2004, revidované vybrané příspěvky, Přednášky v informatice, 3383, Springer, str. 329–339, doi:10.1007/978-3-540-31843-9_33
  9. ^ Hartsfield & Ringel (2013), Věta 8.4.2, s. 173.
  10. ^ Harborth, H. (1974), "Lösung zu Problem 664A", Elemente der Mathematik, 29: 14–15. Jak uvádí Swanepoel (2009) a Pach & Agarwal (1995).
  11. ^ Pach, János; Agarwal, Pankaj K. (1995), Kombinatorická geometrie, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons, Inc., doi:10.1002/9781118033203, ISBN  0-471-58890-3, PAN  1354145. Věta 13.12, s. 211.
  12. ^ Kupitz, Y. S. (1994), „O maximálním počtu výskytů minimální vzdálenosti mezi n body v rovině ", Intuitivní geometrie (Szeged, 1991)Colloq. Matematika. Soc. János Bolyai, 63, Severní Holandsko, str. 217–244, PAN  1383628.
  13. ^ Swanepoel, Konrad J. (2009), „Grafy minimální vzdálenosti bez trojúhelníků v rovině“ (PDF), Geombinatorika, 19 (1): 28–30, PAN  2584434.
  14. ^ A b Eppstein, David (2018), „Edge bounds and degeneracy of the triangle-free penny graphs and squaregraphs“, Journal of Graph Algorithms and Applications, 22 (3): 483–499, arXiv:1708.05152, doi:10,7155 / jgaa.00463, PAN  3866392.
  15. ^ Hartsfield, Nora; Ringel, Gerhard (2013), „Problém 8.4.8“, Perly v teorii grafů: komplexní úvod „Dover Books on Mathematics, Courier Corporation, s. 177–178, ISBN  9780486315522.
  16. ^ Baker, B. (1994), "Aproximační algoritmy pro NP-úplné problémy v rovinných grafech", Deník ACM, 41 (1): 153–180, doi:10.1145/174644.174650.
  17. ^ A b Pach, János; Tóth, Géza (1996), „K počtu nezávislých grafů mincí“, Geombinatorika, 6 (1): 30–33, PAN  1392795.
  18. ^ Swanepoel, Konrad J. (2002), „Independence numbers of plaar contact graphs“, Diskrétní a výpočetní geometrie, 28 (4): 649–670, arXiv:matematika / 0403023, doi:10.1007 / s00454-002-2897-r, PAN  1949907. Výsledek Swanepoel posiluje dřívější C ≥ 9/35 ≈ 0.257 vázaný na Csizmadia (1998).
  19. ^ Dumitrescu, Adrian; Jiang, Minghui (červen 2013), "Sloupec výpočetní geometrie 56" (PDF), Novinky SIGACT, New York, NY, USA: ACM, 44 (2): 80–87, arXiv:cs / 9908007, doi:10.1145/2491533.2491550.