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 .
For eksempel kan Petersen-grafen tegnes med enhedskanter i , men ikke i , så dens dimension er 2 (se figuren til højre).
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.
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.
Med andre ord er dimensionen af en komplet graf den samme som dimensionen af en simpleks med det samme antal hjørner.
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.
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.
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 . Vi kan også vise, at undergrafen ikke tillader en sådan repræsentation i dimension mindre end 4: 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 . |
Til sidst:
, afhængigt af værdierne af m og n .
Dimensionen af en graf G er altid mindre end eller lig med to gange det kromatiske tal : |
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 .
Så er afstanden fra toppunktet for farve p til toppunktet for farve q givet af formlen .
Definitionen af grafdimensionen givet ovenfor angiver for n - minimal repræsentation:
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:
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: |
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] .