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.
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 (Gerbracht 2009)
- A W7 kerékgráf
- a Moser-rokka, a legkisebb 4 színnel színezhető egységtávolsággráf
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 (Žitnik, Horvat & Pisanski 2010). 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) (Gervacio, Lim & Maehara 2008).
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 (Soifer 2008, p. 94).
 | A matematika megoldatlan problémája: Hány egységtávolság lehet pont között? (A matematika további megoldatlan problémái) |
Paul Erdős (1946) 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 (Kuperberg 1992). A legjobb ismert felső korlátot Joel Spencer, Endre Szemerédi, and William Trotter (1984) 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.
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 (Maehara 1991, 1992). 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(Tyszka 2000). 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 (Beckman & Quarles 1953).
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; (Maehara & Rödl 1990) 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 (Erdős & Simonovits 1980).
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 (Schaefer 2013).
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 (Itai, Papadimitriou & Szwarcfiter 1982).
- 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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
