Graf dimension

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 5. marts 2021; verifikation kræver 1 redigering .

Dimensionen af en graf er det mindste heltal n , således at der eksisterer en "klassisk repræsentation" af grafen i et euklidisk rum med dimension n med enhedskantlængder.

I den klassiske fremstilling skal alle hjørner være adskilte, men kanter kan skære hinanden [1] .

Dimensionen af grafen G skrives som . $\dim G$

For eksempel kan Petersen-grafen tegnes med enhedskanter i , men ikke i , så dens dimension er 2 (se figuren til højre). $E^{2}$ $E^{1}$

Konceptet blev foreslået i 1965 af Pal Erdős , Frank Harari og William Tutt [2] . Det generaliserer konceptet med en enhedsafstandsgraf for dimensioner større end 2.

Eksempler

Komplet graf

I værste fald er hvert par hjørner forbundet, hvilket resulterer i en komplet graf .

For at nedsænke en komplet graf med alle kanter af enhedslængde, har vi brug for et euklidisk rum med dimension [3] . For eksempel har du brug for et todimensionelt rum til nedsænkning (en ligesidet trekant) og et tredimensionelt rum til nedsænkning ( et regulært tetraeder ) som vist til højre. $K_n$ $n-1$ $K_{3}$ $K_{4}$

\dim K_{n}=n-1

Med andre ord er dimensionen af en komplet graf den samme som dimensionen af en simpleks med det samme antal hjørner.

Komplet todelte grafer

Alle stjerner for har en dimension på 2 som vist på figuren til venstre. For stjerner med m lig med 1 eller 2 er dimension 1 tilstrækkelig. ${\displaystyle K_{m,1))$ $m\geqslant 3$

En komplet todelt graf for kan tegnes som på figuren til højre ved at placere m toppunkter på en cirkel, hvis radius er mindre end én, de to andre punkter er placeret på begge sider af cirklens plan i passende afstand. har dimension 2, da den kan tegnes på planet som en rombe. $K_{m,2}$ $m\geqslant 3$ $K_{2,2}$

Dimensionen af den komplette todelte graf for og er lig med 4. $K_{{m,n}}$ $m\geqslant 3$ $n\geqslant 3$

Bevis

For at vise, at 4-dimensionelt rum er tilstrækkeligt, som i det foregående tilfælde, bruger vi cirkler.

Lad os betegne koordinaterne for det 4-dimensionelle rum . Vi placerer det ene sæt toppunkter vilkårligt på cirklen , hvor , og det andet sæt vilkårligt på cirklen . Vi ser, at afstanden mellem ethvert toppunkt fra det første sæt og ethvert toppunkt fra det andet sæt er . $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$

Vi kan også vise, at undergrafen ikke tillader en sådan repræsentation i dimension mindre end 4: $K_{{3,3}}$

Hvis en sådan repræsentation findes, så de tre punkter , og ligger på enhedssfæren med centrum . På samme måde ligger de på enhedssfærer med centre og . De første to sfærer skal skære hinanden i en cirkel, i et punkt eller slet ikke skære hinanden. For at placere tre forskellige punkter , og vi må antage skæringspunktet er en cirkel. Enten ligger denne cirkel helt på den tredje enhedssfære, hvilket indebærer, at den tredje sfære falder sammen med en af de to første, så , og ikke alle er forskellige. Hvis cirklerne ikke skærer hinanden i en cirkel, skærer de med den tredje kugle i højst to punkter, og det er ikke nok til at arrangere tre punkter , og . $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}$

Til sidst:

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

, afhængigt af værdierne af m og n .

Dimension og kromatisk tal

Dimensionen af en graf G er altid mindre end eller lig med to gange det kromatiske tal :

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

Bevis

Dette bevis bruger cirkler.

Betegn med n det kromatiske tal på grafen G og tildel heltal til n farver. I det dimensionelle euklidiske rum med dimensioner angivet med , placerer vi alle farvespidser n vilkårligt på cirklen givet af . $(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$

Så er afstanden fra toppunktet for farve p til toppunktet for farve q givet af formlen . ${\sqrt {x_{2p-2}^{2}+x_{2p-1}^{2}+x_{2q-2}^{2}+x_{2q-1}^{2} }}={\sqrt {1/2+1/2}}=1$

Euklidisk dimension

Definitionen af grafdimensionen givet ovenfor angiver for n - minimal repræsentation:

hvis to hjørner af en graf G er forbundet med en kant, skal de være i en afstand af én;
dog behøver to hjørner i en afstand af én ikke at være forbundet med en kant.

Denne definition afvises af nogle forfattere. En anden definition blev foreslået i 1991 af Alexander Soifer , som han kalder den euklidiske dimension af en graf [4] . Før det havde Pal Erdős og Miklós Szymonowicz allerede i 1980 foreslået den samme definition kaldet sand dimension [5] . Ved denne definition er en n -minimal repræsentation en, hvor to grafens toppunkter er forbundet, hvis og kun hvis deres repræsentation er i afstand 1.

Figuren modsatte viser forskellen mellem disse definitioner for et hjul med et centralt toppunkt og seks perifere toppunkter med en eger fjernet. Den plane repræsentation af en graf tillader to hjørner at være i en afstand på 1, men de er ikke forbundet.

Vi skriver den euklidiske afstand som . Den er aldrig mindre end den ovenfor definerede afstand: $\operatorname {Edim} G$

\dim G\leqslant \operatørnavn {Edim} G

Euklidisk dimension og maksimal grad

Pal Erdős og Miklos Shimonovich beviste følgende resultat i 1980 [5] :

Den euklidiske dimension af en graf G er højst det dobbelte af dens maksimale effekt + 1:

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

Beregningsmæssig kompleksitet

Problemet er NP-hårdt , og mere specifikt, for den eksistentielle teori om reelle tal , er problemet med at bestemme, om dimensionen eller den euklidiske dimension af en given graf med en given værdi er større eller ej komplet. Problemet er stadig svært selv at kontrollere, om dimensionen eller den euklidiske dimension er lig med to [6] .

Noter

↑ Nogle matematikere betragter denne " indlejring ", men mange grafteoretikere, herunder Erdős, Harari og Tatta, har brugt udtrykket " indlejring "
↑ Erdős, Harary, Tutte, 1965 , s. 118-122.
↑ Kavangh, Ryan Udforskninger af grafernes dimensionalitet . Hentet: 16. august 2018. (ubestemt)
↑ Soifer, 2009 .
↑ 1 2 Erdős, Simonovits, 1980 , s. 229-246.
↑ Schäfer, 2013 , s. 461-482.

Litteratur

Erdős P., Harary F., Tutte WT Om dimensionen af en graf // Mathematika. - 1965. - T. 12 . - doi : 10.1112/s0025579300005222 .
Alexander Soifer. Den matematiske malebog. - Springer, 2009. - ISBN 978-0-387-74640-1 .
Erdős P., Simonovits M. Om det kromatiske antal af geometriske grafer // Ars Comb.. - 1980. - Issue. 9 . — S. 229–246 .
Marcus Schäfer. Realiserbarhed af grafer og koblinger // Tredive essays om geometrisk grafteori / János Pach. - Springer, 2013. - S. 461-482. - doi : 10.1007/978-1-4614-0110-0_24 .