Částečná krychle

V teorii grafů je částečná krychle podgrafem hyperkrychle , který zachovává vzdálenosti (ve smyslu grafů) - vzdálenost mezi libovolnými dvěma vrcholy podgrafu je stejná jako v původním grafu [1] . Částečná krychle je ekvivalentně graf, jehož vrcholy mohou být označeny bitovými řetězci stejné délky, takže vzdálenost mezi dvěma vrcholy v grafu je rovna Hammingově vzdálenosti mezi dvěma popisky. Tato značka se nazývá Hammingova značka a představuje izometrické vložení částečné krychle do hyperkrychle.


Historie

V. Firsov [2] jako první studoval izometrické vkládání grafů do hyperkrychlí. Grafy umožňující takové vkládání popsali D. Djokovič [3] a P. Winkler [4] a později se jim říkalo „částečné krychle“. Samostatnou linii výzkumu stejných struktur v terminologii rodin množin , spíše než označování hyperkrychlí, vyvinuli mimo jiné V. Kuzmin a S. Ovchinnikov [5] a také Falmagnet a Doinon [6]. [7] .

Příklady

Každý strom je částečná krychle. Předpokládejme, že strom T má m hran a počet těchto hran (v libovolném pořadí) od 0 do m  − 1. Pro strom zvolíme libovolný kořenový vrchol r a každému vrcholu v přiřadíme návěští (bitový řetězec) m bitů long, který obsahuje 1 na pozici i , pokud hrana i leží na cestě z r do v ve stromu T . Například samotný vrchol r bude mít označení nul a všechny vrcholy, které s ním sousedí, budou mít 1 na stejné pozici a tak dále. Potom bude Hammingova vzdálenost mezi libovolnými dvěma štítky rovna vzdálenosti mezi odpovídajícími vrcholy stromu, takže toto označení ukazuje, že strom T je částečná krychle.

Každý graf hyperkrychle je sám o sobě částečnou krychlí, kterou lze označit různými bitovými řetězci s délkou rovnou rozměru hyperkrychle.

Složitější příklady:

Djokovič–Winklerův poměr

Mnoho teorémů o parciálních krychlích je založeno přímo nebo nepřímo na nějaké binární relaci definované na hranách grafu. Tento vztah, který poprvé popsal Djokovič [3] , je označen . Winkler podal ekvivalentní definici vztahu z hlediska vzdálenosti [4] . Dvě hrany a jsou ve vztahu (psány ) pokud . Tento vztah je reflexivní a symetrický , ale obecně není tranzitivní .

Winkler ukázal, že souvislý graf je částečná krychle právě tehdy, když je bipartitní a relace je tranzitivní [12] [13] . V tomto případě vztah tvoří vztah ekvivalence a každá třída ekvivalence odděluje dva spojené podgrafy grafu od sebe. Hammingův štítek lze získat přiřazením jednoho bitu každému štítku pro každou třídu ekvivalence vztahu Djokovič–Winkler. V jednom ze dvou spojených podgrafů oddělených vztahem ekvivalence hran mají štítky na odpovídající pozici 0 a ve druhém spojeném podgrafu mají všechny štítky na stejné pozici 1.

Rozpoznávání

Dají se rozpoznat dílčí krychle a Hammingova značka pro ně je sestavena v čase , kde je počet vrcholů grafu [14] . Vzhledem k částečné krychli lze přímo sestavit třídy Djokovic–Winklerovy ekvivalence pomocí vyhledávání na šířku z každého vrcholu v celkovém čase . Rozpoznávací algoritmus urychluje vyhledávání v průběhu času pomocí paralelismu na bitové úrovni k provedení několika prohledávání nejprve do šířky v jediném průchodu grafem, poté pomocí samostatného algoritmu zkontroluje, zda je výsledkem platné rozvržení částečné krychle.

Rozměr

Izometrický rozměr parciální krychle je minimální rozměr hyperkrychle, do kterého lze izometricky vložit graf a je roven počtu tříd ekvivalence Djokovic–Winklerova vztahu. Například izometrický rozměr stromu s vrcholy je roven počtu jeho hran, . Vložení částečné krychle do hyperkrychle tohoto rozměru je unikátní až do symetrií hyperkrychle [15] [16] .

Libovolnou hyperkrychli, a tedy jakoukoli částečnou krychli, lze izometricky vložit do celočíselné mřížky a rozměr mřížky pro částečnou krychli je minimální rozměr celočíselné mřížky, do které lze vložit částečnou krychli. Rozměr mřížky se může ukázat jako podstatně menší než izometrický rozměr. Například pro strom se rovná polovině počtu listů ve stromu (zaokrouhleno na nejbližší celé číslo). Dimenze mřížky pro libovolný graf a vnoření do mřížky minimálního rozměru lze nalézt v polynomiálním čase pomocí algoritmu založeného na nalezení největší shody v pomocném grafu [17] .

Jsou definovány další typy dílčích rozměrů krychle, založené na specifičtějších strukturách [18] [19] .

Aplikace na chemickou teorii grafů

Izometrické vkládání grafů do hyperkrychle má důležité aplikace v chemické teorii grafů . Benzoidní graf je graf skládající se z vrcholů a hran ležících na cyklu a uvnitř cyklu v hexagonální mřížce . Takové grafy jsou molekulární grafy benzoidních uhlovodíků , velké třídy organických molekul. Každý takový graf je částečná krychle. Hammingovo značení takového grafu lze použít k výpočtu Wienerova indexu odpovídající molekuly, který lze použít k predikci některých chemických vlastností [20] . Částečným krychlím odpovídá i další molekulární struktura tvořená uhlíkem, struktura diamantu ] .

Poznámky

  1. ↑ Ovčinnikov, 2011 , str. 127, definice 5.1.
  2. ↑ Firsov, 1965 .
  3. ↑ 12 Djokovič , 1973 .
  4. ↑ 12 Winkler , 1984 .
  5. ↑ Kuzmin, Ovčinnikov, 1975 .
  6. ↑ Falmagne, Doignon, 1997 .
  7. ↑ Ovčinnikov, 2011 , str. 174.
  8. ↑ Ovčinnikov, 2011 , str. 163–165, oddíl 5.11, "Střední grafy".
  9. ↑ Ovčinnikov, 2011 , str. 207–235, kapitola 7, „Uspořádání v nadplánu“.
  10. ↑ Eppstein, 2006 .
  11. ↑ Ovčinnikov, 2011 , str. 144–145, oddíl 5.7, "Kartézské produkty částečných krychlí".
  12. ↑ Winkler, 1984 , str. Věta 4.
  13. ↑ Ovčinnikov, 2011 , str. 29, 139, Definice 2.13, Věta 5.19.
  14. ↑ Eppstein, 2008 .
  15. ↑ Ovčinnikov, 2011 , str. 142–144, oddíl 5.6, "Izometrický rozměr".
  16. ↑ Ovčinnikov, 2011 , str. 157–162, oddíl 5.10, "Unikátnost izometrických vložení".
  17. ↑ Hadlock, Hoffman, 1978 ; Eppstein, 2005 ; Ovchinnikov, 2011 , kapitola 6, "Mřížkové vložení", s. 183–205.
  18. ↑ 12 Eppstein , 2009 .
  19. ↑ Cabello, Eppstein, Klavžar, 2011 .
  20. ↑ Klavžar, Gutman, Mohar, 1995 , Propozice 2.1 a 3.1; Imrich, Klavžar, 2000 , s. 60; Ovchinnikov, 2011 , oddíl 5.12, „Průměrná délka a Wienerův index“, s. 165–168.

Literatura