Yksikköetäisyyskaavio

Graafiteoriassa yksikköetäisyysgraafi on euklidisen tason pisteistä muodostettu graafi, jossa on kaksi kärkeä, joita yhdistää reuna, jos niiden välinen etäisyys on täsmälleen yksi. Yksikköetäisyyskaavion reunat leikkaavat joskus, joten ne eivät aina ole tasomaisia . Yksikköetäisyyksien kuvaajaa ilman leikkauspisteitä kutsutaan täsmäyskaavioksi .

Nelson-Erdős-Hadwiger-ongelma koskee yksikköetäisyysgraafien kromaattista määrää . Tiedetään, että on olemassa yksikköetäisyyskaavioita, jotka vaativat 5 väriä oikeaan väritykseen, ja että kaikki tällaiset kaaviot voidaan värjätä enintään 7 värillä. Toinen tärkeä avoin ongelma yksikköetäisyysgraafien suhteen kysyy, kuinka monta reunaa tällaisella graafilla voi olla suhteessa pisteiden määrään .

Esimerkkejä

Seuraavat kaaviot ovat yksikköetäisyyskaavioita:

Yksikköetäisyyskaavioiden alakuvaajat

Jotkut kirjoittajat määrittelevät yksikköetäisyysgraafin graafiksi, joka voidaan upottaa tasoon siten, että minkä tahansa kahden vierekkäisen kärjen on oltava yhden etäisyydellä, mutta yhden etäisyydellä olevien pisteiden ei tarvitse olla vierekkäisiä. Esimerkiksi Möbius-Cantor-graafissa on tällainen graafinen esitys.

Tämän määritelmän mukaan kaikki yleistetyt Petersen - graafit ovat yksikköetäisyyskaavioita ( Žitnik, Horvat, Pisanski 2010 ). Näiden kahden määritelmän erottamiseksi graafit, joissa mitkä tahansa kaksi kärkeä, jotka ovat yhden etäisyydellä, on yhdistetty reunalla, kutsutaan tiukoiksi yksikköetäisyysgraafiksi ( Gervacio, Lim, Maehara 2008 ).

Kuvaaja, joka muodostuu poistamalla yksi puoli pyörästä W 7 , on yksikköetäisyyden alagraafi, mutta ei tiukka yksikköetäisyysgraafi ( Soifer 2008 , s. 94).

Yksikköetäisyyksien laskeminen

Ratkaisemattomat matematiikan tehtävät : Kuinka monta yksikköetäisyyttä voi olla n pisteen joukossa?

Erdős ( Erdős 1946 ) ehdotti ongelmaa arvioida n pisteen joukossa niiden parien lukumäärä, jotka ovat yhden etäisyydellä. Graafiteorian kannalta kysymys on yksikköetäisyysgraafin tiheyden arvioimisesta.

Hyperkuutiograafi antaa alarajan yksikköetäisyyksien lukumäärälle, joka on verrannollinen

ja tarjosi 500 dollarin bonuksen selvittääkseen, voidaanko yksikköetäisyyksien enimmäismäärä ilmaista samanlaisella funktiolla ( Kuperberg 1992 ). Tunnetuin yläraja Spencerin, Szemerédin ja Trotterin mukaan ( Spencer, Szemerédi, Trotter 1984 ) on verrannollinen

.

Tätä rajaa voidaan ajatella pisteiden osumien lukumääränä yksikköympyröillä, ja se liittyy läheisesti Szemedi-Trotterin lauseeseen pisteiden ja suorien esiintymisestä.

Algebrallisten lukujen ja Beckman-Quorles-lauseen esitys

Mille tahansa algebralliselle luvulle A löytyy yksikköetäisyysgraafi G , jossa jotkin kärkiparit ovat etäisyydellä A kaikissa G :n yksikköetäisyysesityksissä ( Maehara 1991 ) ( Maehara 1992 ). Tämä tulos viittaa äärelliseen versioon Beckman-Quorles-lauseesta kahdelle pisteelle p ja q , jotka ovat etäisyydellä A , on olemassa äärellinen jäykkä yksikköetäisyysgraafi, joka sisältää p :n ja q :n siten, että mikä tahansa muunnos Taso, joka säilyttää yksikköetäisyydet tässä kaaviossa, säilyttää p :n ja q :n välisen etäisyyden ( Tyszka 2000 ). Täydellinen Beckman-Quorles-lause sanoo, että minkä tahansa euklidisen tason (tai korkeamman ulottuvuuden avaruuden) etäisyyttä säilyttävän muunnoksen on oltava kongruenssi . Siten äärettömien yksikköetäisyysgraafien kohdalla, joiden kärjet ovat koko taso, minkä tahansa graafin automorfismin on oltava isometria ( Beckman, Quarles 1953 ).

Yleistys korkeampiin ulottuvuuksiin

Yksikköetäisyysgraafin määritelmä voidaan luonnollisesti yleistää mihin tahansa euklidisen avaruuden ulottuvuuteen . Mikä tahansa graafi voidaan upottaa pistejoukoksi riittävän korkean ulottuvuuden tilaan. Maehara ja Rödl ( Maehara, Rödl 1990 ) ovat osoittaneet, että graafin upottamiseen tarvittava ulottuvuus voidaan rajoittaa kaksinkertaiseen maksimitehoon.

Graafisen upotuksen vaatima mitta, jossa kaikilla reunoilla on yksikköpituus, ja upotusmitta, jossa reunat yhdistävät täsmälleen ne pisteet, joiden välinen etäisyys on yksi, voivat vaihdella merkittävästi. Kruunu , jossa on 2n kärkeä, voidaan upottaa 4-avaruuteen siten, että kaikilla reunoilla on yksikködyne, mutta upottamiseen tarvitaan vähintään mitta n  − 2, jotta ei ole yksikkönä erillään olevia pistepareja, joita ei yhdistä reuna. ( Erdős, Simonovits 1980 ).

Laskennallinen monimutkaisuus

On NP-kova ongelma , tarkemmin sanottuna täydellinen reaalilukujen olemassaoloteorialle , tarkistaa, onko tietty graafi yksikköetäisyysgraafi vai tiukka yksikköetäisyysgraafi ( Schaefer 2013 ).

Katso myös

Muistiinpanot

Linkit