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 thumb|150px|A Q4 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 A W7 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 thumb|150px|left|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 . 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) .

Például a W7 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 .

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

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 -nel arányos. Egy négyzetrácson megfelelően elhelyezett pontokkal Erdős talált egy javított alsó korlátot:

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 . A legjobb ismert felső korlátot adta, ami arányos a következőhöz: .

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 . 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 is. 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 .

Á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; 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 .

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 .

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 .

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.

Jegyzetek

Források . . . As cited by . . . . . . . . . . . . .

További információk .

Kategória:Geometriai gráfok