Dimensiunea graficului

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 5 martie 2021; verificarea necesită 1 editare .

Dimensiunea unui grafic este cel mai mic număr întreg n , astfel încât să existe o „reprezentare clasică” a graficului într-un spațiu euclidian de dimensiune n cu lungimi de muchii unitare.

În reprezentarea clasică, toate vârfurile trebuie să fie distincte, dar muchiile se pot intersecta [1] .

Dimensiunea graficului G se scrie ca . $\dim G$

De exemplu, graficul Petersen poate fi desenat cu muchiile unității în dar nu în , deci dimensiunea sa este 2 (vezi figura din dreapta). $E^{2}$ $E^{1}$

Conceptul a fost propus în 1965 de Pal Erdős , Frank Harari și William Tutt [2] . Generalizează conceptul de grafic al distanței unitare pentru dimensiuni mai mari de 2.

Exemple

Grafic complet

În cel mai rău caz, fiecare pereche de vârfuri este conectată, rezultând un grafic complet .

Pentru a scufunda un grafic complet cu toate muchiile unității de lungime, avem nevoie de un spațiu euclidian de dimensiune [3] . De exemplu, aveți nevoie de un spațiu bidimensional pentru imersare (un triunghi echilateral) și un spațiu tridimensional pentru imersare ( un tetraedru obișnuit ), așa cum se arată în dreapta. $K_n$ $n-1$ $K_{3}$ $K_{4}$

\dim K_{n}=n-1

Cu alte cuvinte, dimensiunea unui grafic complet este aceeași cu dimensiunea unui simplex având același număr de vârfuri.

Grafice bipartite complete

Toate stelele au o dimensiune de 2, așa cum se arată în figura din stânga. Pentru stelele cu m egal cu 1 sau 2, dimensiunea 1 este suficientă. $K_{m,1)$ $m\geqslant 3$

Un grafic bipartit complet pentru poate fi desenat ca în figura din dreapta, plasând m vârfuri pe un cerc a cărui rază este mai mică de unu, celelalte două puncte sunt situate de ambele părți ale planului cercului la o distanță adecvată. are dimensiunea 2, deoarece poate fi desenat pe plan ca un romb. $K_{m,2}$ $m\geqslant 3$ $K_{2,2}$

Dimensiunea graficului bipartit complet pentru și este egală cu 4. $K_{{m,n}}$ $m\geqslant 3$ $n\geqslant 3$

Dovada

Pentru a arăta că spațiul cu 4 dimensiuni este suficient, ca și în cazul precedent, folosim cercuri.

Să notăm coordonatele spațiului cu 4 dimensiuni . Punem un set de vârfuri în mod arbitrar pe cerc , unde , iar celălalt set arbitrar pe cerc . Vedem că distanța dintre orice vârf din primul set și orice vârf din al doilea set este . $w,x,y,z$ $w^{2}+x^{2}=a,y=0,z=0$ $0<a<1$ $y^{2}+z^{2}=1-a,w=0,x=0$ ${\sqrt {w^{2}+x^{2}+y^{2}+z^{2}}}={\sqrt {a+1-a}}=1$

De asemenea, putem arăta că subgraful nu permite o astfel de reprezentare în dimensiune mai mică de 4: $K_{{3,3}}$

Dacă o astfel de reprezentare există, atunci cele trei puncte , și se află pe sfera unității cu centrul . În mod similar, ele se află pe sfere unitare cu centre și . Primele două sfere trebuie să se intersecteze într-un cerc, într-un punct, sau să nu se intersecteze deloc. Pentru a plasa trei puncte diferite și trebuie să presupunem că intersecția este un cerc. Fie acest cerc se află în întregime pe a treia sferă unitate, ceea ce implică că a treia sferă coincide cu una dintre primele două, astfel încât , și nu sunt toate distincte. Dacă cercurile nu se intersectează într-un cerc, ele se intersectează cu a treia sferă în cel mult două puncte, iar acest lucru nu este suficient pentru a aranja trei puncte , și . $A_{1}$ $A_{2}$ $A_{3}$ $B_1$ $B_{2}$ $B_{3}$ $A_{1}$ $A_{2}$ $A_{3}$ $B_1$ $B_{2}$ $B_{3}$ $A_{1}$ $A_{2}$ $A_{3}$

În cele din urmă:

\dim K_{m,n}=1,2,3,4

, în funcție de valorile lui m și n .

Dimensiunea și numărul cromatic

Dimensiunea unui grafic G este întotdeauna mai mică sau egală cu dublul numărului cromatic :

\dim G\leqslant 2\,\chi (G)

Dovada

Această dovadă folosește cercuri.

Notați cu n numărul cromatic al graficului G și atribuiți numere întregi la n culori. În spațiul euclidian -dimensional cu dimensiunile notate cu , plasăm toate vârfurile de culoare n în mod arbitrar pe cercul dat de . $(1..n)$ $2n$ ${\displaystyle x_{1},x_{2},..x_{2n))$ $x_{2n-2}^{2}+x_{2n-1}^{2}=1/2,\quad x_{i}|(i\neq 2{n-2},i\neq 2{n-1})=0$

Apoi distanța de la vârful culorii p la vârful culorii q este dată de formula . ${\sqrt {x_{2p-2}^{2}+x_{2p-1}^{2}+x_{2q-2}^{2}+x_{2q-1}^{2} }}={\sqrt {1/2+1/2}}=1$

Dimensiunea euclidiană

Definiția dimensiunii graficului dată mai sus afirmă pentru reprezentarea n - minimă:

dacă două vârfuri ale unui grafic G sunt legate printr-o muchie, ele trebuie să fie la o distanță de unu;
totuși, două vârfuri la o distanță de unul nu trebuie să fie conectate printr-o muchie.

Această definiție este respinsă de unii autori. O altă definiție a fost propusă în 1991 de Alexander Soifer , pe care el o numește dimensiunea euclidiană a unui graf [4] . Înainte de aceasta, în 1980 Pal Erdős și Miklós Szymonowicz propușiseră deja aceeași definiție numită dimensiune adevărată [5] . Prin această definiție, o reprezentare n -minimă este una în care două vârfuri de graf sunt conectate dacă și numai dacă reprezentarea lor este la distanța 1.

Figura opusă arată diferența dintre aceste definiții pentru cazul unei roți având un vârf central și șase vârfuri periferice cu o spiță îndepărtată. Reprezentarea plană a unui graf permite ca două vârfuri să fie la o distanță de 1, dar nu sunt conectate.

Distanța euclidiană o scriem ca . Nu este niciodată mai mică decât distanța definită mai sus: $\operatorname {Edim} G$

\dim G\leqslant \operatorname {Edim} G

Dimensiunea euclidiană și gradul maxim

Pal Erdős și Miklos Shimonovich au demonstrat următorul rezultat în 1980 [5] :

Dimensiunea euclidiană a unui grafic G este de cel mult două ori puterea sa maximă + 1:

\operatorname {Edim} G\leqslant 2\,\Delta (G)+1

Complexitate computațională

Problema este NP-hard și, mai precis, pentru teoria existențială a numerelor reale , problema de a determina dacă dimensiunea sau dimensiunea euclidiană a unui grafic dat de o valoare dată este mai mare sau nu este completă. Problema rămâne dificilă chiar și de a verifica dacă dimensiunea sau dimensiunea euclidiană este egală cu doi [6] .

Note

↑ Unii matematicieni consideră această „ încorporare ”, dar mulți teoreticieni ai graficelor, inclusiv Erdős, Harari și Tatta, au folosit termenul „ încorporare ”
↑ Erdős, Harary, Tutte, 1965 , p. 118–122.
↑ Kavangh, Ryan Explorări despre dimensionalitatea graficelor . Preluat: 16 august 2018. (nedefinit)
↑ Soifer, 2009 .
↑ 1 2 Erdős, Simonovits, 1980 , p. 229–246.
↑ Schaefer, 2013 , p. 461–482.

Literatură

Erdős P., Harary F., Tutte WT Despre dimensiunea unui grafic // Mathematika. - 1965. - T. 12 . - doi : 10.1112/s0025579300005222 .
Alexandru Soifer. Cartea de colorat matematic. - Springer, 2009. - ISBN 978-0-387-74640-1 .
Erdős P., Simonovits M. Despre numărul cromatic al graficelor geometrice // Ars Comb.. - 1980. - Issue. 9 . — S. 229–246 .
Marcus Schaefer. Realizabilitatea graficelor și legăturilor // Treizeci de eseuri despre teoria graficelor geometrice / János Pach. - Springer, 2013. - S. 461-482. - doi : 10.1007/978-1-4614-0110-0_24 .