Mértékegység távolság grafikonja

A gráfelméletben az egységnyi távolsággráf az euklideszi sík pontjaiból alkotott gráf, amelynek két csúcsa egy éllel van összekötve, ha a köztük lévő távolság pontosan egy. Az egységnyi távolsággráf élei néha metszik egymást, így nem mindig síkbeliek . Az egységnyi távolságok metszéspontok nélküli grafikonját egyezési gráfnak nevezzük .

A Nelson-Erdős-Hadwiger probléma az egységnyi távolsággráfok kromatikus számát érinti. Ismeretes, hogy vannak olyan egységtávolság-grafikonok, amelyeknél 5 szín szükséges a megfelelő színezéshez, és minden ilyen grafikon legfeljebb 7 színnel színezhető. Egy másik fontos nyitott probléma az egységnyi távolság gráfokkal kapcsolatban, hogy hány éle lehet egy ilyen gráfnak a csúcsok számához képest .

Példák

A következő grafikonok egységnyi távolság grafikonok:

Az egységnyi távolság grafikonjainak részgráfjai

Egyes szerzők az egységnyi távolság gráfot olyan gráfként határozzák meg, amely beágyazható egy síkba úgy, hogy bármely két szomszédos csúcsnak egy távolságra kell lennie, de az egy távolságra lévő csúcsoknak nem kell szomszédosnak lenniük. Például a Möbius-Cantor gráfnak van egy ilyen grafikus ábrázolása.

E definíció szerint minden általánosított Petersen - gráf egységnyi távolság gráf ( Žitnik, Horvat, Pisanski 2010 ). E két definíció megkülönböztetésére azokat a gráfokat, amelyekben bármely két, egy távolságra lévő csúcsot él köt össze, szigorú egységtávolság-gráfoknak fogjuk nevezni ( Gervacio, Lim, Maehara 2008 ).

A W 7 kerékről egy küllő eltávolításával képzett grafikon egységnyi távolság részgráf, de nem szigorú egységnyi távolsággráf ( Soifer 2008 , 94. o.).

Egységtávolságok számítása

Megoldatlan matematikai feladatok : Hány egységnyi távolság lehet egy n pontból álló halmazban?

Erdős ( Erdős 1946 ) azt a problémát javasolta, hogy egy n pontból álló halmazban becsüljük meg az egy távolságra lévő párok számát. Gráfelmélet szempontjából a kérdés az egységnyi távolsággráf sűrűségének becslése.

A hiperkocka gráf egy alsó korlátot ad az egységnyi távolságok számának arányos értékére Egy gondosan megválasztott távolságú négyzetrács pontjait figyelembe véve Erdős javított alsó korlátot talált.

és felajánlott egy 500 dolláros bónuszt annak kiderítésére, hogy az egységnyi távolságok maximális száma kifejezhető-e azonos típusú függvénnyel ( Kuperberg 1992 ). A legismertebb felső korlát Spencer, Szemerédi és Trotter szerint ( Spencer, Szemerédi, Trotter 1984 ) arányos

.

Ezt a határértéket úgy tekinthetjük, mint az egységkörök pontjainak találatainak számát, és szorosan összefügg a pontok és egyenesek előfordulására vonatkozó Szemedi-Trotter tétellel .

Az algebrai számok és a Beckman-Quorles-tétel ábrázolása

Bármely A algebrai számra megtalálható egy G egységnyi távolsággráf , amelyben néhány csúcspár A távolságban van G minden egységnyi távolságábrázolásában ( Maehara 1991 ) ( Maehara 1992 ). Ez az eredmény a Beckman–Quorles-tétel véges változatát jelenti bármely két A távolságra lévő p és q pontra létezik egy véges merev egységnyi távolsággráf, amely p és q -t tartalmaz , így a az egységnyi távolságokat megőrző sík ezen a grafikonon megőrzi a p és q közötti távolságot ( Tyszka 2000 ). A teljes Beckman-Quorles-tétel kimondja, hogy az euklideszi sík (vagy magasabb dimenziójú tér) bármely távolságmegtartó transzformációja kongruenciának kell lennie . Így a végtelen egységtávolságú gráfoknál, amelyek csúcsai a teljes síkot jelentik, bármely gráfautomorfizmusnak izometriának kell lennie ( Beckman, Quarles 1953 ).

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

Az egységnyi távolsággráf definíciója természetesen általánosítható az euklideszi tér bármely dimenziójára . Bármely gráf beágyazható ponthalmazként egy kellően nagy dimenziójú térbe. Maehara és Rödl ( Maehara, Rödl 1990 ) kimutatták, hogy a gráf beágyazásához szükséges méret a maximális teljesítmény kétszeresére korlátozható.

Jelentősen eltérhet a gráfbeágyazáshoz szükséges méret, amelyben minden él egységnyi hosszúságú lesz, és a beágyazási méret, amelyben az élek pontosan azokat a pontokat kötik össze, amelyek között a távolság egy. Egy 2n csúcsú korona beágyazható a 4-es térbe úgy, hogy minden élnek egységnyi dine van, de legalább n − 2 méretre van szükség  ahhoz, hogy ne legyenek olyan csúcspárok, amelyek egységnyire vannak egymástól, és amelyeket nem él összeköt ( Erdős, Simonovits 1980 ).

Számítási összetettség

Egy NP-nehéz feladat , pontosabban a valós számok létezéselméletére teljes annak ellenőrzése, hogy egy adott gráf egységnyi távolsággráf vagy szigorú egységnyi távolsággráf ( Schaefer 2013 ).

Lásd még

Jegyzetek

Linkek