Részleges kocka

A gráfelméletben a parciális kocka egy hiperkocka részgráfja , amely megőrzi a távolságokat (gráfokban kifejezve) - a részgráf bármely két csúcsa közötti távolság megegyezik az eredeti gráfban szereplővel [1] . Ezzel egyenértékűen a részleges kocka olyan gráf, amelynek csúcsai azonos hosszúságú bitsorokkal címkézhetők fel úgy, hogy a gráf két csúcsa közötti távolság egyenlő a két címke közötti Hamming-távolsággal . Ezt a jelölést Hamming -jelölésnek nevezik , és egy részleges kocka izometrikus beágyazását jelenti egy hiperkockába.


Történelem

V. Firsov [2] volt az első, aki a gráfok hiperkockákba való izometrikus beágyazását tanulmányozta. Az ilyen beágyazásokat lehetővé tevő grafikonokat D. Djokovic [3] és P. Winkler [4] írta le, és később „részkockáknak” nevezték el. A hiperkockák címkézése helyett a halmazcsaládok terminológiájában ugyanazon struktúrákra vonatkozó kutatási irányt többek között V. Kuzmin és S. Ovchinnikov [5] , valamint Falmagnet és Doinon [6] dolgozta ki. [7] .

Példák

Bármely fa részleges kocka. Tegyük fel, hogy egy T fának m éle van, és ezeknek az éleknek a száma (tetszőleges sorrendben) 0-tól m  − 1-ig. Kiválasztunk egy tetszőleges r gyökércsúcsot a fának, és minden v csúcshoz rendelünk egy m bitet egy címkét (bit karakterláncot). hosszú, amely 1-et tartalmaz az i pozícióban, ha az i él a T fában r -től v -ig tartó úton fekszik . Például magának az r csúcsnak nullák a címkéje, és a vele szomszédos összes csúcsnak ugyanabban a helyzetben lesz 1-es, és így tovább. Ekkor a Hamming-távolság bármely két címke között egyenlő lesz a fa megfelelő csúcsai közötti távolsággal, tehát ez a címkézés azt mutatja, hogy a T fa részkocka.

Bármely hiperkocka gráf maga is parciális kocka, amely különböző, a hiperkocka méretével megegyező hosszúságú bitsorokkal jelölhető.

Bonyolultabb példák:

Djokovic–Winkler arány

Sok részkockákra vonatkozó tétel közvetlenül vagy közvetve a gráf élein meghatározott bináris reláción alapul. Ezt a kapcsolatot, amelyet először Djokovic [3] írt le , jelöli . Winkler ekvivalens definíciót adott a relációnak távolságban [4] . Két él és relációban vannak (írt ), ha . Ez a kapcsolat reflexív és szimmetrikus , de általában nem tranzitív .

Winkler megmutatta, hogy egy összefüggő gráf akkor és csak akkor parciális kocka, ha bipartit , és a reláció tranzitív [12] [13] . Ebben az esetben a reláció egy ekvivalenciarelációt alkot, és minden ekvivalenciaosztály a gráf két összefüggő részgráfját választja el egymástól. Hamming-címkét úgy kaphatunk, hogy minden címkében egy bitet rendelünk a Djokovic–Winkler reláció minden ekvivalencia osztályához. Az élekvivalencia relációval elválasztott két összekapcsolt részgráf egyikében a címkék megfelelő pozíciójában 0, a másik összekapcsolt részgráfban pedig az azonos pozícióban lévő összes címkén 1 található.

Elismerés

A részleges kockák felismerhetők és a Hamming-jelölés időben felépül , ahol a gráf csúcsainak száma [14] . Adott egy részleges kocka, közvetlenül létrehozhatunk Djokovic–Winkler ekvivalencia osztályokat szélességi kereséssel minden csúcsból a teljes idő alatt . A felismerési algoritmus idővel felgyorsítja a keresést azáltal, hogy bitszintű párhuzamosság használatával több szélességben történő keresést hajt végre egyetlen grafikonon, majd egy külön algoritmus segítségével ellenőrzi, hogy az eredmény egy érvényes részleges kockaelrendezés.

Méret

A parciális kocka izometrikus dimenziója a hiperkocka minimális mérete, amelybe egy gráf izometrikusan beágyazható, és megegyezik a Djokovic–Winkler reláció ekvivalencia osztályainak számával. Például egy csúcsokkal rendelkező fa izometrikus mérete megegyezik az éleinek számával, . A részleges kocka beágyazása egy ilyen dimenziójú hiperkockába a hiperkocka szimmetriákig egyedi [15] [16] .

Bármilyen hiperkocka, tehát bármely részkocka, izometrikusan beágyazható egy egész rácsba , és a részleges kocka rácsmérete az egész rács minimális mérete, amelybe részleges kocka beágyazható. A rács mérete lényegesen kisebbnek bizonyulhat, mint az izometrikus méret. Például egy fa esetében ez egyenlő a fában lévő levelek számának felével (a legközelebbi egész számra kerekítve). A rács dimenziója bármely gráfhoz és a minimális méretű rácsba való beágyazódás polinomiális időben egy segédgráfban a legnagyobb egyezés megtalálásán alapuló algoritmussal megkereshető [17] .

Más típusú részleges kockaméretek vannak meghatározva, konkrétabb struktúrák alapján [18] [19] .

Alkalmazások a kémiai gráfelmélethez

A gráfok izometrikus beágyazása egy hiperkockába fontos alkalmazások a kémiai gráfelméletben . A benzoid gráf egy gráf, amely egy cikluson és egy cikluson belüli csúcsokból és élekből áll egy hatszögletű rácsban . Ilyen grafikonok a benzoid szénhidrogének molekuláris grafikonjai , amelyek a szerves molekulák nagy csoportja. Minden ilyen gráf egy részkocka. Egy ilyen gráf Hamming-jelölése felhasználható a megfelelő molekula Wiener-indexének kiszámítására , amivel előre jelezhető egyes kémiai tulajdonságok [20] . Egy másik, szén által alkotott molekulaszerkezet, a gyémánt szerkezete szintén a részkockáknak felel meg [18] .

Jegyzetek

  1. ↑ Ovchinnikov, 2011 , p. 127. 5.1.
  2. ↑ Firsov, 1965 .
  3. ↑ 1 2 Djokovic, 1973 .
  4. ↑ 12 Winkler , 1984 .
  5. ↑ Kuzmin, Ovchinnikov, 1975 .
  6. ↑ Falmagne, Doignon, 1997 .
  7. ↑ Ovchinnikov, 2011 , p. 174.
  8. ↑ Ovchinnikov, 2011 , p. 163–165., 5.11. szakasz, „Mediángrafikonok”.
  9. ↑ Ovchinnikov, 2011 , p. 207–235, 7. fejezet, „Hipersík elrendezések”.
  10. ↑ Eppstein, 2006 .
  11. ↑ Ovchinnikov, 2011 , p. 144–145, 5.7. szakasz, „Részleges kockák derékszögű szorzatai”.
  12. ↑ Winkler, 1984 , p. 4. tétel.
  13. ↑ Ovchinnikov, 2011 , p. 29., 139., 2.13. definíció, 5.19. tétel.
  14. ↑ Eppstein, 2008 .
  15. ↑ Ovchinnikov, 2011 , p. 142–144, 5.6. szakasz, „Izometrikus méret”.
  16. ↑ Ovchinnikov, 2011 , p. 157–162, 5.10. szakasz, „Az izometrikus beágyazások egyedisége”.
  17. ↑ Hadlock, Hoffman, 1978 ; Eppstein, 2005 ; Ovchinnikov, 2011 , 6. fejezet, „Rácsbeágyazások”, 183–205.
  18. ↑ 12 Eppstein , 2009 .
  19. ↑ Cabello, Eppstein, Klavžar, 2011 .
  20. ↑ Klavžar, Gutman, Mohar, 1995 , 2.1. és 3.1. tétel; Imrich, Klavžar, 2000 , 60. o.; Ovchinnikov, 2011 , 5.12. szakasz, „Átlagos hossz és a Wiener-index”, 165–168.

Irodalom