Egységtávolsággráf

A matematika, azon belül a geometriai gráfelmélet területén az egységtávolsággráf vagy egység távolságú gráf (unit distance graph) olyan gráf, ami az euklideszi síkon lévő pontokon felrajzolható oly módon, hogy két csúcspont akkor van éllel összekötve, ha a közöttük lévő távolság éppen 1. Az egységtávolsággráfok élei metszhetik egymást, tehát nem feltétlenül síkba rajzolható gráfok; a metszések nélkül azonos élhosszal síkba rajzolható gráf neve gyufagráf.

A Hadwiger–Nelson-probléma felveti az egység távolságú gráfok kromatikus számának kérdését. Ismertek négy színnel színezhető egységtávolsággráfok, és azt is tudjuk, hogy minden ilyen gráf legfeljebb hét színnel színezhető.

Egy másik fontos nyitott kérdés, hogy az egység távolságú gráfoknak hány élük lehet csúcspontjaik számának arányában.

Példák

A Q₄ hiperkockagráf egységtávolsággráfként

A következő gráfok egységtávolsággráfok:

• Bármely körgráf
• Bármely rácsgráf (csempézési gráf)
• Bármely hiperkockagráf
• Bármely csillaggráf
• A Petersen-gráf
• A Heawood-gráf Sablon:Harv
• A W₇ kerékgráf
• a Moser-rokka, a legkisebb 4 színnel színezhető egységtávolsággráf

Egységtávolsággráfok részgráfjai

A Möbius–Kantor-gráf egység távolságú ábrázolása, ahol néhány nem szomszédos pár is egység távolságra található egymástól

Egyes szerzők egységtávolsággráfnak tekintenek minden gráfot, ha csúcsai elhelyezhetők egy síkban oly módon, hogy a szomszédos csúcspárok egységnyi távolságra legyenek, nem foglalkozva azzal a lehetőséggel, hogy egyes nem szomszédos párok is egységnyi távolságra kerülnek-e. Például a Möbius–Kantor-gráf lerajzolható ily módon.

Az egységtávolsággráf ilyen lazább definíciója alapján minden általánosított Petersen-gráf is egységtávolsággráf Sablon:Harv. A két definíció megkülönböztetése érdekében az olyan gráfok, ahol a síkba rajzoláskor megköveteljük, hogy az anti-élek ne egység hosszúságúak legyenek, nevezhetők szigorú egységtávolsággráfoknak (strict unit distance graphs) Sablon:Harv.

Például a W₇ kerékgráf egyik küllőjének eltávolításával kapott gráf egységtávolsággráf részgráfja, de nem szigorú egységtávolsággráf; egybevágóságtól eltekintve egyetlen módon lehet a csúcspontokat úgy elhelyezni, hogy a szomszédos csúcsok egységnyi távolságra legyenek, de ez az elhelyezés a két végpontot is egység távolságra helyezi el Sablon:Harv.

Egységtávolságok leszámlálása

Sablon:Megoldatlan Sablon:Harvs tette fel a kérdést, hogy n pont közül hány lehet páronként egységnyi távolságra egymástól. Gráfelméleti fogalmakat használva, mennyire lehet sűrű egy egységtávolsággráf?

A hiperkockagráf ad egy alsó korlátot az egységtávolságokra, ami $n\log n$-nel arányos. Egy négyzetrácson megfelelően elhelyezett pontokkal Erdős talált egy javított alsó korlátot:

$n^{1+c/\log \log n},$

majd 500 dollárt ajánlott annak, aki eldönti, hogy a maximális számú egységtávolságokra található-e ilyen formájú felső korlát Sablon:Harv. A legjobb ismert felső korlátot Sablon:Harvs adta, ami arányos a következőhöz: $n^{4/3};$.

Ez a korlát pontok és egységkörök incidenciaszámaként (illeszkedésszámaként) is tekinthető, és közeli kapcsolatban van a pontok és egyenesek illeszkedésével foglalkozó Szemerédi–Trotter-tétellel.

Algebrai számok reprezentációja és a Beckman–Quarles-tétel

Minden A algebrai számhoz lehetséges találni olyan G egységtávolsággráfot, melyben néhány csúcspont A távolságra található G minden egységtávolsággráf-megfeleltetésében Sablon:Harvs. Ez az eredmény implikálja a Beckman–Quarles-tétel egy véges változatát: bármely egymástól A távolságra lévő p és q pontot tekintve létezik p és q pontokat tartalmazó olyan véges merev egységtávolsággráf, hogy a sík minden olyan transzformációja, ami megtartja az egységtávolságokat a gráfban, egyben megtartja a p és q közötti távolságot isSablon:Harv. A teljes Beckman–Quarles-tétel állítása szerint ha egy euklideszi sík (vagy annak magasabb dimenziójú megfelelője) bármilyen transzformációja során az egységtávolságok megmaradnak, akkor az a transzformáció egybevágósági; tehát a végtelen egységtávolsággráf számára, melynek csúcspontjai a sík összes pontjával esnek egybe, bármely gráfautomorfizmus egy izometria Sablon:Harv.

Általánosítás magasabb dimenziókra

Az egységtávolsággráf meghatározása kiterjeszthető magasabb dimenziójú euklideszi terekre. Bármilyen gráf beágyazható egy kellően magas dimenziójú tér pontjaiként; Sablon:Harvtxt megmutatja, hogy az ilyen módon szükséges dimenziószám kétszerese a gráf csúcspontjai maximális fokszámának.

Az egységtávolsággráfhoz és a szigorú egységtávolsággráfhoz szükséges dimenziószám nagyon különböző is lehet. A 2n-csúcsú koronagráf például négy dimenzióba ágyazható oly módon, hogy minden éle egység hosszúságú, de legalább n−2 dimenzió szükséges ahhoz, hogy az élek legyenek az egyetlen egység távolságra lévő csúcstávolságok Sablon:Harv.

Számítási komplexitás

NP-nehéz feladat annak eldöntése, hogy adott gráf egységtávolsággráf vagy szigorú egységtávolsággráf-e Sablon:Harv.

NP-teljes feladat annak eldöntése, hogy egy egységtávolsággráf tartalmaz-e Hamilton-kört, még akkor is, ha a gráf csúcspontjai mind egész koordinátákon helyezkednek el Sablon:Harv.

Kapcsolódó szócikkek

• Egységkörlapgráf, olyan síkgráf, ahol két pont között akkor húzódik él, ha távolságuk legfeljebb egy.

Források

• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation. As cited by Sablon:Harvtxt.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation Sablon:Wayback.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.

További információk

• Sablon:Citation Sablon:Wayback.
• Sablon:Mathworld