Graficul distanței unității

În teoria grafurilor, un grafic de distanță unitară este un grafic format din puncte pe planul euclidian, cu două vârfuri legate printr-o muchie dacă distanța dintre ele este exact una. Marginile graficului unității de distanță se intersectează uneori, deci nu sunt întotdeauna plane . Un grafic al distanțelor unitare fără intersecții se numește grafic de potrivire .

Problema Nelson-Erdős-Hadwiger se referă la numărul cromatic al graficelor de distanță unitară. Se știe că există grafice de unitate de distanță care necesită 5 culori pentru o colorare corectă și că toate astfel de grafice pot fi colorate cu cel mult 7 culori. O altă problemă deschisă importantă referitoare la graficele de distanță unitară se întreabă câte muchii poate avea un astfel de grafic în raport cu numărul de vârfuri .

Exemple

Următoarele grafice sunt grafice ale distanței unitare:

• orice ciclu ;
• orice zăbrele ;
• orice grafic hipercub ;
• orice stea ;
• Contele de Petersen ;
• conte de Heawood ( Gerbracht 2009 );
• Roata W 7 ;
• Axul lui Moser , cel mai mic grafic al distanței unitare cu numărul cromatic 4.

Subgrafe ale graficelor de distanță unitară

Unii autori definesc un grafic de distanță unitară ca un grafic care poate fi încorporat într-un plan astfel încât oricare două vârfuri adiacente trebuie să fie la o distanță de unu, dar vârfurile care sunt la o distanță de unu nu trebuie să fie adiacente. De exemplu , graficul Möbius-Cantor are o reprezentare grafică de acest fel.

Conform acestei definiții, toate graficele Petersen generalizate sunt grafice ale distanței unitare ( Žitnik, Horvat, Pisanski 2010 ). Pentru a distinge între aceste două definiții, graficele în care oricare două vârfuri la o distanță de unu sunt conectate printr-o muchie vor fi numite grafice stricte de distanță unitară ( Gervacio, Lim, Maehara 2008 ).

Graficul format prin îndepărtarea unei spițe din roata W 7 este un subgraf de distanță unitară, dar nu un grafic de distanță unitară strictă ( Soifer 2008 , p. 94).

Calculul distanțelor unitare

Erdős ( Erdős 1946 ) a propus problema estimării, într-o mulţime de n puncte, a numărului de perechi care se află la o distanţă de unu. În ceea ce privește teoria graficelor, întrebarea este de a estima densitatea graficului de distanță unitară.

Graficul hipercubului oferă o limită inferioară a numărului de unități de distanță proporțională cu . Luând în considerare punctele unei rețele pătrate cu o distanță aleasă cu grijă, Erdős a găsit o limită inferioară îmbunătățită.

și a oferit un bonus de 500 USD pentru a afla dacă numărul maxim de distanțe unitare poate fi exprimat printr-o funcție de același fel ( Kuperberg 1992 ). Cea mai cunoscută limită superioară, conform lui Spencer, Szemerédi și Trotter ( Spencer, Szemerédi, Trotter 1984 ), este proporțională cu

Această limită poate fi considerată ca fiind numărul de lovituri de puncte pe cercurile unitare și este strâns legată de teorema Szemeredi-Trotter privind incidența punctelor și a liniilor.

Reprezentarea numerelor algebrice și teorema Beckman-Quorles

Pentru orice număr algebric A , se poate găsi un grafic de distanță unitară G , în care unele perechi de vârfuri sunt la distanța A în toate reprezentările de distanță unitară ale lui G ( Maehara 1991 ) ( Maehara 1992 ). Acest rezultat implică o versiune finită a teoremei Beckman–Quorles pentru orice două puncte p și q care se află la distanța A , există un grafic finit rigid de distanță unitară care conține p și q astfel încât orice transformare a planul care păstrează distanțele unitare în acest grafic păstrează distanța dintre p și q ( Tyszka 2000 ). Teorema completă Beckman-Quorles afirmă că orice transformare care păstrează distanța a planului euclidian (sau spațiului de dimensiune mai mare) trebuie să fie o congruență . Astfel, pentru grafurile de distanță unități infinite ale căror vârfuri sunt întregul plan, orice automorfism de graf trebuie să fie o izometrie ( Beckman, Quarles 1953 ).

Generalizare la dimensiuni mai mari

Definiția unui grafic de distanță unitară poate fi generalizată în mod natural la orice dimensiune a spațiului euclidian . Orice grafic poate fi încorporat ca un set de puncte într-un spațiu de dimensiune suficient de mare. Maehara și Rödl ( Maehara, Rödl 1990 ) au arătat că dimensiunea necesară pentru încorporarea unui grafic poate fi limitată la dublul puterii maxime.

Dimensiunea necesară pentru încorporarea graficului, în care toate muchiile vor avea lungimea unitară, și dimensiunea de încorporare, în care muchiile vor conecta exact acele puncte între care distanța este una, pot diferi semnificativ. O coroană cu 2n vârfuri poate fi încorporată într-un spațiu de 4, astfel încât toate muchiile să aibă unitatea de dyne, dar este nevoie de cel puțin dimensiunea n  - 2 pentru a se încorpora astfel încât să nu existe perechi de vârfuri care să fie unitar depărtare și care să nu fie conectate printr-o muchie. ( Erdős , Simonovits 1980 ).

Complexitate computațională

Este o problemă NP-hard , mai precis completă pentru teoria existenței numerelor reale , pentru a verifica dacă un grafic dat este un grafic de distanță unitară sau un grafic de distanță unitară strictă ( Schaefer 2013 ).

Vezi și

• Graficul cerc unitar , un grafic în plan ale cărui două vârfuri sunt conectate printr-o muchie dacă distanța dintre puncte nu depășește unul.

Note

• F.S. Beckman, D.A., Jr. Se ceartă. Despre izometriile spațiilor euclidiene // Proceedings of the American Mathematical Society. - 1953. - T. 4 . - S. 810-815 .
• Paul Erds. Pe seturi de distanțe de n puncte. — American Mathematical Monthly . - The American Mathematical Monthly, 1946. - V. 53. - S. 248-250. - doi : 10.2307/2305092 . .
• Paul Erdős, Miklos Simonovits. Despre numărul cromatic al graficelor geometrice // Ars Combinatoria. - 1980. - T. 9 . - S. 229-246 . După cum este citat în Soifer, 2008 , p. 97.
• Eberhard H.-A. Gerbracht. Unsprezece unități de încorporare de distanță ale graficului Heawood . - 2009. - arXiv : 0912.5395 . .
• Severino V. Gervacio, Yvette F. Lim, Hiroshi Maehara. Grafice planare unitate-distanță având complement planar unitate-distanță // Matematică discretă. - 2008. - T. 308 , nr. 10 . - S. 1973-1984 . - doi : 10.1016/j.disc.2007.04.050 . .
• Greg Kuperberg. Pisicuța Erdos: Cel puțin 9050 USD în premii! . - 1992. Arhivat la 29 septembrie 2006.
• Hiroshi Maehara. Distanțe într-un grafic rigid unitate-distanță în plan // Matematică aplicată discretă. - 1991. - T. 31 , nr. 2 . - S. 193-200 . - doi : 10.1016/0166-218X(91)90070-D . .
• Hiroshi Maehara. Extinderea unui cadru flexibil de bare de unitate la unul rigid // Matematică discretă. - 1992. - T. 108 , nr. 1-3 . - S. 167-174 . - doi : 10.1016/0012-365X(92)90671-2 . .
• Hiroshi Maehara, Vojtech Rodl. Pe dimensiunea de reprezentat un grafic printr-un grafic de distanță unitară  // Grafice și combinatorie. - 1990. - T. 6 , nr. 4 . - S. 365-367 . - doi : 10.1007/BF01787703 . .
• Marcus Schaefer. Treizeci de eseuri despre teoria graficelor geometrice / János Pach. - Springer, 2013. - S. 461-482. - doi : 10.1007/978-1-4614-0110-0_24 . .
• Alexandru Soifer. Cartea de colorat matematic. - Springer-Verlag, 2008. - ISBN 978-0-387-74640-1 .
• Joel Spencer, Endre Szemerédi, William T. Trotter. Teoria grafurilor și combinatorică. - Presa Academică, 1984. - S. 293-308.
• Apoloniusz Tyszka. Versiuni discrete ale teoremei Beckman-Quarles // Aequationes Mathematicae. - 2000. - T. 59 , nr. 1-2 . - S. 124-133 . - doi : 10.1007/PL00000119 . .
• Arjana Žitnik, Boris Horvat, Tomaž Pisanski. Toate graficele Petersen generalizate sunt grafice unitate-distanță . - 2010. - T. 1109 .

Link -uri

• Suresh Venkatasubramanian. Problema 39: Distanțele dintre seturile de puncte din R 2 și R 3  // Proiectul problemelor deschise. Arhivat din original la 30 august 2006.
• Weisstein, Eric W. Unit-Distance Graph  (engleză) pe site-ul Wolfram MathWorld .