Graf vzdálenosti jednotek - Unit distance graph - Wikipedia

The Petersenův graf je graf jednotkové vzdálenosti: každý vnitřní vrchol se otáčí ${ displaystyle 90 ^ { circ}}$ ze sousedního vnějšího vrcholu vzhledem ke středu výkresu.^[1]

v matematika a zejména teorie geometrických grafů, a graf jednotkové vzdálenosti je graf vytvořený ze souboru bodů v souboru Euklidovské letadlo spojením dvou bodů hranou, kdykoli je vzdálenost mezi dvěma body přesně jeden. Okraje grafů jednotkové vzdálenosti se někdy protínají, takže tomu tak není vždy rovinný; jednotkový graf vzdálenosti bez křížení se nazývá a zápalkový graf.

The Hadwiger – Nelsonův problém týká se chromatické číslo grafů jednotkové vzdálenosti. Je známo, že existují grafy jednotkových vzdáleností vyžadující pět barev v jakémkoli správném vybarvení,^[2] a že všechny takové grafy lze obarvit nejvýše sedmi barvami. Další důležitý otevřený problém týkající se grafů jednotkové vzdálenosti se ptá, kolik hran mohou mít vzhledem k jejich počtu vrcholy.

Příklady

The hyperkrychlový graf Q₄ jako graf jednotkové vzdálenosti.

Následující grafy jsou grafy jednotkové vzdálenosti:

• Žádný graf cyklu
• Žádný mřížkový graf
• Žádný hyperkrychlový graf
• Žádný hvězdný graf
• Žádný zápalkový graf nebo penny graf
• The Petersenův graf^[3]
• The Heawoodův graf^[4]
• The graf kola Ž₇
• The Moser vřeteno, nejmenší graf vzdálenosti 4 chromatických jednotek

Žádný kartézský součin grafů jednotkové vzdálenosti vytvoří další graf jednotkové vzdálenosti. Totéž však neplatí pro ostatní běžně používané produkty grafů.^[5]

Podgrafy grafů jednotkové vzdálenosti

Výkres jednotkové vzdálenosti Möbius-Kantorův graf ve kterém jsou některé nesousedící páry také v jednotkové vzdálenosti od sebe.

Některé zdroje definují graf jako graf jednotkové vzdálenosti, pokud lze jeho vrcholy mapovat na různá místa v rovině tak, že sousední páry jsou v jednotkové vzdálenosti od sebe, bez ohledu na možnost, že některé nesousedící páry mohou být také v jednotkové vzdálenosti od sebe. Například Möbius-Kantorův graf má výkres tohoto typu.

Podle této volnější definice grafu jednotkové vzdálenosti vše zobecněné Petersenovy grafy jsou grafy jednotkové vzdálenosti.^[6] Abychom rozlišili dvě definice, můžeme nazvat grafy, ve kterých je požadováno, aby ne-hrany byly od sebe vzdáleny přísné jednotkové vzdálenosti grafy.^[7].

Graf vytvořený odstraněním jednoho z paprsků z graf kola Ž₇ je podgrafem grafu jednotkové vzdálenosti, ale nejde o striktní graf jednotkové vzdálenosti: existuje pouze jeden způsob (až do shoda ) umístit vrcholy na odlišná místa tak, aby sousední vrcholy byly od sebe vzdálené jednotky, a toto umístění také umístí dva koncové body chybějícího paprsku do jednotkové vzdálenosti.^[8]

Počítání jednotkových vzdáleností

Nevyřešený problém v matematice: Kolik jednotkových vzdáleností lze určit sadou ${ displaystyle n}$ body? (více nevyřešených úloh z matematiky)

The Hammingův graf (3,3) má 27 vrcholů a 81 jednotkových vzdáleností

Paul Erdős  (1946 ) způsobil problém odhadnout, kolik párů bodů v sadě n body mohou být ve vzájemné jednotkové vzdálenosti. Jak teoreticky může být graf jednotkové vzdálenosti hustý?

The hyperkrychlový graf poskytuje dolní mez počtu úměrných jednotkových vzdáleností ${ displaystyle n log n.}$ Uvažováním o bodech ve čtvercové mřížce s pečlivě zvoleným rozestupem našel Erdős vylepšenou spodní hranici formy

${ displaystyle n ^ {1 + c / log log n},}$

a nabídl cenu 500 $ za určení, zda může být maximální počet jednotkových vzdáleností také horně omezen funkcí tohoto formuláře.^[9] Nejznámější horní hranice tohoto problému, kvůli Joel Spencer, Endre Szemerédi, a William Trotter  (1984 ), je úměrný

${ displaystyle n ^ {4/3};}$

tuto vazbu lze také zobrazit jako počítání výskytů mezi body a kruhy jednotek a úzce souvisí s Szemerédi – Trotterova věta na výskyty mezi body a přímkami.

Reprezentace algebraických čísel a Beckman-Quarlesova věta

Pro každého algebraické číslo A, je možné najít graf jednotkové vzdálenosti G ve kterém jsou některé páry vrcholů ve vzdálenosti A ve všech reprezentacích jednotek na vzdálenost G.^[10] Tento výsledek naznačuje konečnou verzi Věta Beckman – Quarles: za jakékoli dva body str a q na dálku A, existuje konečný tuhý graf jednotkové vzdálenosti obsahující str a q tak, že jakákoli transformace roviny, která zachovává jednotkové vzdálenosti v tomto grafu, zachovává vzdálenost mezi str a q.^[11] Celá teorém Beckman – Quarles uvádí, že jakákoli transformace euklidovské roviny (nebo prostoru vyšší dimenze), která zachovává jednotkové vzdálenosti, musí být shoda; tj. pro graf nekonečné jednotkové vzdálenosti, jehož vrcholy jsou všechny body v rovině, jakýkoli automatický graf musí být izometrie.^[12]

Zobecnění na vyšší dimenze

Definici grafu jednotkové vzdálenosti lze přirozeně zobecnit na jakoukoli vyšší dimenzi Euklidovský prostor Libovolný graf může být vložen jako množina bodů v dostatečně vysoké dimenzi; Maehara & Rödl (1990) ukazují, že kóta nezbytná pro vložení grafu tímto způsobem může být ohraničena dvojnásobkem maximálního stupně.

Dimenze potřebná k vložení grafu tak, aby všechny hrany měly jednotkovou vzdálenost, a kóta potřebná k vložení grafu tak, aby hrany byly přesně páry jednotkových vzdáleností, se od sebe mohou značně lišit: 2n-vrchol korunový graf může být vložen ve čtyřech rozměrech, takže všechny jeho okraje mají jednotkovou délku, ale vyžaduje alespoň n - 2 rozměry, které mají být vloženy tak, aby hrany byly jedinými páry jednotek a vzdáleností.^[13]

Výpočetní složitost

to je NP-tvrdé a konkrétněji kompletní pro existenciální teorie skutečností, aby se otestovalo, zda je daný graf grafem jednotkové vzdálenosti, nebo zda jde o přísný graf jednotkové vzdálenosti.^[14]

Je to také NP-kompletní k určení, zda má graf jednotkové vzdálenosti a Hamiltonovský cyklus, i když mají vrcholy grafu všechny celočíselné souřadnice.^[15]

Viz také

• Graf disku jednotky, graf v rovině, která má hranu, kdykoli jsou dva body ve vzdálenosti nejvýše jednoho

Reference

Poznámky

Zdroje

• Beckman, F. S .; Quarles, D. A., Jr. (1953), „On isometries of Euclidean spaces“, Proceedings of the American Mathematical Society, 4 (5): 810–815, doi:10.2307/2032415, JSTOR  2032415, PAN  0058193.
• Erdős, Paul (1946), „Na množinách vzdáleností n body ", Americký matematický měsíčník, 53 (5): 248–250, doi:10.2307/2305092, JSTOR  2305092.
• Erdős, Paul; Harary, Franku; Tutte, William T. (1965), „O dimenzi grafu“ (PDF), Mathematika, 12: 118–122, doi:10.1112 / S0025579300005222, PAN  0188096.
• Erdős, Paul; Simonovits, Miklós (1980), „O chromatickém počtu geometrických grafů“, Ars Combinatoria, 9: 229–246. Jak uvádí Soifer (2008, str. 97).
• Gerbracht, Eberhard H.-A. (2009), Vložení jedenácti jednotek vzdálenosti grafu Heawood, arXiv:0912.5395, Bibcode:2009arXiv0912.5395G.
• Gervacio, Severino V .; Lim, Yvette F .; Maehara, Hiroshi (2008), „Planární grafy jednotkových vzdáleností s doplňkem planárních jednotkových vzdáleností“, Diskrétní matematika, 308 (10): 1973–1984, doi:10.1016 / j.disc.2007.04.050.
• Griffiths, Martin (červen 2019), „103,27 Vlastnost konkrétního grafu jednotkové vzdálenosti“, Matematický věstník, 103 (557): 353–356, doi:10.1017 / mag.2019.74.
• Horvat, Boris; Pisanski, Tomaž (2010), „Produkty grafů jednotkových vzdáleností“, Diskrétní matematika, 310 (12): 1783–1792, doi:10.1016 / j.disc.2009.11.035, PAN  2610282.
• Itai, Alon; Papadimitriou, Christos H.; Szwarcfiter, Jayme Luiz (1982), „Hamiltonovy cesty v mřížkových grafech“, SIAM Journal on Computing, 11 (4): 676–686, CiteSeerX  10.1.1.383.1078, doi:10.1137/0211056, PAN  0677661.
• Kuperberg, Greg (1992), Koťátko Erdos: Ceny v hodnotě alespoň 9050 $!, Zveřejňování na usenet skupiny rec.puzzles a sci.math, archivovány od originál dne 29. 9. 2006.
• Langin, Katie (18. dubna 2018), „Amatérský matematik prolomil desítky let starý matematický problém“, Věda.
• Maehara, Hiroshi (1991), „Vzdálenosti v pevném grafu jednotkové vzdálenosti v rovině“, Diskrétní aplikovaná matematika, 31 (2): 193–200, doi:10.1016 / 0166-218X (91) 90070-D.
• Maehara, Hiroshi (1992), „Rozšíření pružné rámové tyče na tuhou“, Diskrétní matematika, 108 (1–3): 167–174, doi:10.1016 / 0012-365X (92) 90671-2, PAN  1189840.
• Maehara, Hiroši; Rödl, Vojtech (1990), „O dimenzi reprezentující graf jednotkovým grafem vzdálenosti“, Grafy a kombinatorika, 6 (4): 365–367, doi:10.1007 / BF01787703.
• Schaefer, Marcus (2013), „Realizovatelnost grafů a vazeb“, in Pach, János (vyd.), Třicet esejů o teorii geometrických grafů, Springer, str. 461–482, CiteSeerX  10.1.1.220.9651, doi:10.1007/978-1-4614-0110-0_24, ISBN  978-1-4614-0109-4.
• Soifer, Alexander (2008), Matematická omalovánka, Springer-Verlag, ISBN  978-0-387-74640-1.
• Spencer, Joel; Szemerédi, Endre; Trotter, William T. (1984), „Jednotkové vzdálenosti v euklidovské rovině“, Bollobás, Béla (ed.), Teorie grafů a kombinatorika, London: Academic Press, s. 293–308, ISBN  978-0-12-111760-3, PAN  0777185.
• Tyszka, Apoloniusz (2000), „Diskrétní verze Beckmanovy věty“, Aequationes Mathematicae, 59 (1–2): 124–133, arXiv:matematika / 9904047, doi:10.1007 / PL00000119, PAN  1741475.
• Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), Všechny zobecněné Petersenovy grafy jsou grafy jednotkových vzdáleností (PDF), Předtisky IMFM, 1109.

externí odkazy

• Venkatasubramanian, Suresh, "Problém 39: Vzdálenosti mezi body zapadají." R² a R³", Projekt Otevřené problémy
• Weisstein, Eric W. „Graph Unit-Distance“. MathWorld.