Enhedsafstandsgraf

I grafteori er en enhedsafstandsgraf en graf dannet af punkter på det euklidiske plan med to hjørner forbundet med en kant, hvis afstanden mellem dem er nøjagtig én. Kanterne på enhedsafstandsgrafen skærer nogle gange hinanden, så de er ikke altid plane . En graf over enhedsafstande uden skæringspunkter kaldes en matchgraf .

Nelson-Erdős-Hadwiger-problemet vedrører det kromatiske antal enhedsafstandsgrafer. Det er kendt, at der er enhedsafstandsgrafer, der kræver 5 farver for korrekt farvelægning, og at alle sådanne grafer højst kan farvelægges med 7 farver. Et andet vigtigt åbent problem vedrørende enhedsafstandsgrafer spørger, hvor mange kanter en sådan graf kan have i forhold til antallet af toppunkter .

Eksempler

Følgende grafer er enhedsafstandsgrafer:

Undergrafer af enhedsafstandsgrafer

Nogle forfattere definerer en enhedsafstandsgraf som en graf, der kan indlejres i et plan, således at to tilstødende hjørner skal være i en afstand af én, men hjørner, der er i en afstand af én, behøver ikke at være tilstødende. For eksempel har Möbius-Cantor grafen en grafisk repræsentation af denne art.

Ifølge denne definition er alle generaliserede Petersen -grafer enhedsafstandsgrafer ( Žitnik, Horvat, Pisanski 2010 ). For at skelne mellem disse to definitioner vil grafer, hvori hvilke som helst to hjørner i en afstand af én er forbundet med en kant, blive kaldt strenge enhedsafstandsgrafer ( Gervacio, Lim, Maehara 2008 ).

Grafen dannet ved at fjerne den ene eger fra hjulet W 7 er en enhedsafstandsundergraf, men ikke en streng enhedsafstandsgraf ( Soifer 2008 , s. 94).

Beregning af enhedsafstande

Uløste problemer i matematik : Hvor mange enhedsafstande kan der være i et sæt af n punkter?

Erdős ( Erdős 1946 ) foreslog problemet med at estimere, i et sæt af n punkter, antallet af par, der er i en afstand af et. Med hensyn til grafteori er spørgsmålet at estimere tætheden af ​​enhedsafstandsgrafen.

Hyperkubegrafen giver en nedre grænse for antallet af enhedsafstande proportionalt med Ved at betragte punkterne i et kvadratisk gitter med en nøje valgt afstand, fandt Erdős en forbedret nedre grænse

og tilbød en bonus på 500 $ for at finde ud af, om det maksimale antal enhedsafstande kan udtrykkes ved en funktion af samme slags ( Kuperberg 1992 ). Den bedst kendte øvre grænse er ifølge Spencer, Szemerédi og Trotter ( Spencer, Szemerédi, Trotter 1984 ) proportional med

.

Denne grænse kan opfattes som antallet af hits af punkter på enhedscirkler, og den er tæt forbundet med Szemeredi-Trotter-sætningen om forekomsten af ​​punkter og linjer.

Repræsentation af algebraiske tal og Beckman-Quorles sætning

For ethvert algebraisk tal A kan man finde en enhedsafstandsgraf G , hvor nogle par af hjørnepunkter er i afstand A i alle enhedsafstandsrepræsentationer af G ( Maehara 1991 ) ( Maehara 1992 ). Dette resultat indebærer en endelig version af Beckman-Quorles-sætningen for alle to punkter p og q , der er i afstanden A , eksisterer der en endelig rigid enhedsafstandsgraf indeholdende p og q , således at enhver transformation af plan, der bevarer enhedsafstande i denne graf, bevarer afstanden mellem p og q ( Tyszka 2000 ). Den komplette Beckman-Quorles-sætning siger, at enhver afstandsbevarende transformation af det euklidiske plan (eller rum af højere dimension) skal være en kongruens . For uendelige enhedsafstandsgrafer, hvis toppunkter er hele planet, skal enhver grafautomorfi således være en isometri ( Beckman, Quarles 1953 ).

Generalisering til højere dimensioner

Definitionen af ​​en enhedsafstandsgraf kan naturligt generaliseres til enhver dimension af det euklidiske rum . Enhver graf kan indlejres som et sæt punkter i et rum med tilstrækkelig høj dimension. Maehara og Rödl ( Maehara, Rödl 1990 ) har vist, at den dimension, der kræves for at indlejre en graf, kan begrænses til to gange den maksimale effekt.

Den dimension, der kræves til grafindlejring, hvor alle kanter vil have enhedslængde, og indlejringsdimensionen, hvor kanterne forbinder præcis de punkter, mellem hvilke afstanden er én, kan variere betydeligt. En krone med 2n hjørner kan indlejres i 4-mellemrum, så alle kanter har enhedsdyne, men det kræver mindst dimension n  − 2 at indlejre sådan, at der ikke er par knudepunkter, der er enhed fra hinanden, og som ikke er forbundet med en kant ( Erdős, Simonovits 1980 ).

Beregningsmæssig kompleksitet

Det er et NP-hårdt problem , mere præcist komplet for eksistensteorien for reelle tal , at kontrollere, om en given graf er en enhedsafstandsgraf eller en streng enhedsafstandsgraf ( Schäfer 2013 ).

Se også

Noter

Links