Graf jednotkové vzdálenosti

V teorii grafů je jednotkový graf vzdálenosti graf tvořený body na euklidovské rovině se dvěma vrcholy spojenými hranou, pokud je vzdálenost mezi nimi právě jedna. Hrany grafu jednotkové vzdálenosti se někdy protínají, takže nejsou vždy rovinné . Graf jednotkových vzdáleností bez průsečíků se nazývá zápasový graf .

Problém Nelson-Erdős-Hadwiger se týká chromatického počtu grafů jednotkové vzdálenosti. Je známo, že existují grafy jednotkové vzdálenosti, které vyžadují 5 barev pro správné vybarvení, a že všechny takové grafy lze vybarvit maximálně 7 barvami. Další důležitý otevřený problém týkající se jednotkových vzdálenostních grafů se ptá, kolik hran může mít takový graf vzhledem k počtu vrcholů .

Příklady

Následující grafy jsou grafy vzdálenosti jednotek:

• jakýkoli cyklus ;
• jakákoli mříž ;
• libovolný graf hyperkrychle ;
• jakákoli hvězda ;
• hrabě z Petersen ;
• hrabě z Heawoodu ( Gerbracht 2009 );
• kolo W 7 ;
• Moserovo vřeteno , nejmenší jednotkový graf vzdálenosti s chromatickým číslem 4.

Podgrafy jednotkových vzdálenostních grafů

Někteří autoři definují graf jednotkové vzdálenosti jako graf, který lze vložit do roviny tak, že libovolné dva sousední vrcholy musí být ve vzdálenosti jednoho, ale vrcholy, které jsou ve vzdálenosti jednoho, sousedit nemusí. Grafické znázornění tohoto druhu má například Möbiův-Cantorův graf .

Podle této definice jsou všechny zobecněné Petersenovy grafy grafy jednotkové vzdálenosti ( Žitnik, Horvat, Pisanski 2010 ). Abychom rozlišili mezi těmito dvěma definicemi, grafy, ve kterých jsou libovolné dva vrcholy ve vzdálenosti jedné spojeny hranou, budeme nazývat grafy striktní jednotkové vzdálenosti ( Gervacio, Lim, Maehara 2008 ).

Graf vytvořený odstraněním jednoho paprsku z kola W 7 je podgraf jednotkové vzdálenosti, ale ne striktní jednotkový graf vzdálenosti ( Soifer 2008 , s. 94).

Výpočet jednotkových vzdáleností

Erdős ( Erdős 1946 ) navrhl problém odhadnout v sadě n bodů počet párů, které jsou ve vzdálenosti jedné. Z hlediska teorie grafů je otázkou odhadnout hustotu grafu jednotkové vzdálenosti.

Graf hyperkrychle udává spodní hranici počtu jednotkových vzdáleností úměrnou k Uvážením bodů čtvercové mřížky s pečlivě vybranou vzdáleností Erdős našel zlepšenou spodní hranici.

a nabídli bonus 500 $, aby zjistili, zda lze maximální počet jednotkových vzdáleností vyjádřit funkcí stejného druhu ( Kuperberg 1992 ). Nejznámější horní hranice podle Spencera, Szemerédiho a Trottera ( Spencer, Szemerédi, Trotter 1984 ) je úměrná

Tento limit si lze představit jako počet zásahů bodů na jednotkové kružnice a úzce souvisí se Szemeredi-Trotterovou větou o výskytu bodů a čar.

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

Pro libovolné algebraické číslo A lze najít graf jednotkové vzdálenosti G , ve kterém jsou některé dvojice vrcholů ve vzdálenosti A ve všech reprezentacích jednotkové vzdálenosti G ( Maehara 1991 ) ( Maehara 1992 ). Tento výsledek implikuje konečnou verzi Beckmanovy-Quorlesovy věty pro jakékoli dva body p a q , které jsou ve vzdálenosti A , existuje konečný rigidní graf vzdálenosti obsahující p a q takový, že jakákoli transformace rovina, která v tomto grafu zachovává jednotkové vzdálenosti, zachovává vzdálenost mezi p a q ( Tyszka 2000 ). Kompletní Beckman-Quorlesův teorém říká, že jakákoli vzdálenost zachovávající transformace euklidovské roviny (nebo prostoru vyšší dimenze) musí být kongruence . Pro grafy vzdálenosti s nekonečnými jednotkami, jejichž vrcholy jsou celá rovina, tedy musí být jakýkoli automorfismus grafu izometrií ( Beckman, Quarles 1953 ).

Zobecnění do vyšších dimenzí

Definici jednotkového grafu vzdálenosti lze přirozeně zobecnit na jakoukoli dimenzi euklidovského prostoru . Jakýkoli graf lze vložit jako množinu bodů do prostoru dostatečně velkých rozměrů. Maehara a Rödl ( Maehara, Rödl 1990 ) ukázali, že rozměr potřebný pro vložení grafu může být omezen na dvojnásobek maximálního výkonu.

Rozměr potřebný pro vložení grafu, ve kterém budou mít všechny hrany jednotkovou délku, a rozměr vložení, ve kterém budou hrany spojovat přesně ty body, mezi nimiž je vzdálenost jedna, se mohou výrazně lišit. Koruna s 2n vrcholy může být vložena do 4prostoru tak, že všechny hrany mají jednotku dyne, ale k vložení potřebuje alespoň rozměr n  − 2 tak, že neexistují žádné páry vrcholů, které jsou od sebe v jednotě, které nejsou spojeny hranou ( Erdős, Simonovits 1980 ).

Výpočetní složitost

Je to NP-těžký problém , přesněji úplný pro teorii existence reálných čísel , ověřit, zda je daný graf jednotkovým grafem vzdálenosti nebo striktním jednotkovým grafem vzdálenosti ( Schaefer 2013 ).

Viz také

• Jednotkový kruhový graf, graf v rovině, jehož dva vrcholy jsou spojeny hranou, pokud vzdálenost mezi body nepřesahuje jednu.

Poznámky

• F.S. Beckman, D.A., Jr. Hádky. O izometriích euklidovských prostorů // Proceedings of the American Mathematical Society. - 1953. - T. 4 . - S. 810-815 .
• Paul Erds. Na množinách vzdáleností n bodů. — Americký matematický měsíčník . - The American Mathematical Monthly, 1946. - V. 53. - S. 248-250. - doi : 10.2307/2305092 . .
• Paul Erdős, Miklos Simonovits. O chromatickém počtu geometrických grafů // Ars Combinatoria. - 1980. - T. 9 . - S. 229-246 . Jak je uvedeno v Soifer, 2008 , s. 97.
• Eberhard H.-A. Gerbracht. Jedenáct jednotkových vzdáleností vložení Heawoodova grafu . - 2009. - arXiv : 0912.5395 . .
• Severino V. Gervacio, Yvette F. Lim, Hiroshi Maehara. Grafy rovinné jednotky-vzdálenost s doplňkem rovinné jednotky-vzdálenost // Diskrétní matematika. - 2008. - T. 308 , č.p. 10 . - S. 1973-1984 . - doi : 10.1016/j.disc.2007.04.050 . .
• Greg Kuperberg. Kočička Erdos: Nejméně 9050 $ na cenách! . - 1992. Archivováno 29. září 2006.
• Hiroshi Maehara. Vzdálenosti v pevném grafu jednotkových vzdáleností v rovině // Diskrétní aplikovaná matematika. - 1991. - T. 31 , no. 2 . - S. 193-200 . - doi : 10.1016/0166-218X(91)90070-D . .
• Hiroshi Maehara. Rozšíření flexibilní jednotkové konstrukce na pevnou // Diskrétní matematika. - 1992. - T. 108 , no. 1-3 . - S. 167-174 . - doi : 10.1016/0012-365X(92)90671-2 . .
• Hiroshi Maehara, Vojtěch Rodl. Na dimenzi pro znázornění grafu pomocí grafu vzdálenosti jednotek  // Grafy a kombinatorika. - 1990. - T. 6 , no. 4 . - S. 365-367 . - doi : 10.1007/BF01787703 . .
• Marcus Schaefer. Třicet esejí o teorii geometrických grafů / János Pach. - Springer, 2013. - S. 461-482. - doi : 10.1007/978-1-4614-0110-0_24 . .
• Alexander Soifer. Matematická omalovánka. - Springer-Verlag, 2008. - ISBN 978-0-387-74640-1 .
• Joel Spencer, Endre Szemerédi, William T. Trotter. Teorie grafů a kombinatorika. - Academic Press, 1984. - S. 293-308.
• Apoloniusz Tyszka. Diskrétní verze Beckman-Quarlesovy věty // Aequationes Mathematicae. - 2000. - T. 59 , no. 1-2 . - S. 124-133 . - doi : 10.1007/PL00000119 . .
• Arjana Žitnik, Boris Horvat, Tomaž Pisanski. Všechny zobecněné Petersenovy grafy jsou grafy jednotkové vzdálenosti . - 2010. - T. 1109 .

Odkazy

• Suresh Venkatasubramanian. Úloha 39: Vzdálenosti mezi množinami bodů v R 2 a R 3  // The Open Problems Project. Archivováno z originálu 30. srpna 2006.
• Weisstein, Eric W. Unit-Distance Graph  (anglicky) na webových stránkách Wolfram MathWorld .