Šířka pásma grafu - Graph bandwidth
v teorie grafů, problém se šířkou pásma grafu je označit n vrcholy protii grafu G s odlišnými celými čísly F(protii) tak, aby množství je minimalizován (E je sada hran G).[1]Problém lze vizualizovat tak, že umístíte vrcholy grafu do různých celočíselných bodů podél X-os, takže délka nejdelší hrany je minimalizována. Takové umístění se nazývá lineární uspořádání grafu, lineární rozložení grafu nebo lineární umístění grafu.[2]
The vážený problém se šířkou pásma grafu je zevšeobecnění, ve kterém jsou hranám přiřazeny váhy wij a nákladová funkce být minimalizován je .
Pokud jde o matice, (nevážený) šířka pásma grafu je šířka pásma z symetrická matice který je matice sousedství Šířku pásma lze také definovat jako jednu menší než maximální klika velikost v správný interval supergraf daného grafu, zvolený k minimalizaci jeho velikosti kliky (Kaplan a Shamir 1996 ).
Vzorce šířky pásma pro některé grafy
Pro několik rodin grafů šířka pásma je dán explicitním vzorcem.
Šířka pásma a graf cesty Pn na n vrcholy je 1 a pro kompletní graf K.m my máme . Pro kompletní bipartitní graf K.m,n,
- , za předpokladu
což dokázal Chvátal.[3] Jako zvláštní případ tohoto vzorce platí: hvězdný graf na k + 1 vrcholy mají šířku pásma .
Pro hyperkrychlový graf na vrcholy šířka pásma byla určena Harper (1966) být
Ukázala Chvatálová[4] že šířka pásma m × n čtvercová mřížka graf , toto je kartézský součin dvou grafů cest na a vrcholy, se rovná min {m,n}.
Meze
Šířku pásma grafu lze omezit z hlediska různých dalších parametrů grafu. Například, nechat χ (G) označují chromatické číslo z G,
pronájem diam (G) označují průměr z Gplatí následující nerovnosti:[5]
kde je počet vrcholů v .
Pokud graf G má šířku pásma k, pak jeho šířka cesty je nanejvýš k (Kaplan a Shamir 1996 ), a jeho hloubka stromu je nanejvýš k log (n/k) (Gruber 2012 ). Naproti tomu, jak je uvedeno v předchozí části, hvězdný graf Sk, strukturálně velmi jednoduchý příklad a strom, má poměrně velkou šířku pásma. Všimněte si, že šířka cesty z Sk je 1 a jeho hloubka stromu je 2.
Některé rodiny grafů omezeného stupně mají sublearní šířku pásma: Chung (1988) dokázal, že pokud T je strom maximálního stupně then, tedy
Obecněji pro rovinné grafy maximálně omezeného maxima ∆, podobné vázané držení (srov. Böttcher a kol. 2010 ):
Výpočet šířky pásma
Nevážená i vážená verze jsou speciální případy problém s přiřazením kvadratického úzkého místa Problém se šířkou pásma je NP-tvrdé, dokonce i pro některé speciální případy.[6] Pokud jde o existenci efektivníhoaproximační algoritmy, je známo, že šířka pásma je NP-těžké se přiblížit v jakékoli konstantě, a to platí i v případě, že jsou omezeny vstupní grafy housenky s maximální délkou vlasů 2 (Dubey, Feige & Unger 2010 Pro případ hustých grafů byl navržen 3-aproximační algoritmus Karpinski, Wirtgen & Zelikovsky (1997) Na druhou stranu je známa řada polynomiálně řešitelných zvláštních případů.[2] A heuristický Algoritmus pro získání lineárních grafů s malou šířkou pásma je Algoritmus Cuthill – McKee. V roce byl navržen rychlý víceúrovňový algoritmus pro výpočet šířky pásma grafu.[7]
Aplikace
Zájem o tento problém pochází z některých oblastí použití.
Jedna oblast je řídká matice /pásmová matice zpracování a obecné algoritmy z této oblasti, jako např Algoritmus Cuthill – McKee, lze použít k nalezení přibližného řešení problému šířky pásma grafu.
Další doména aplikace je v automatizace elektronického designu. v standardní buňka metodika návrhu, obvykle mají standardní buňky stejnou výšku a jejich umístění je uspořádán do několika řádků. V této souvislosti problém šířky pásma grafu modeluje problém umístění sady standardních buněk do jednoho řádku s cílem minimalizovat maximální šíření zpoždění (předpokládá se, že je úměrná délce drátu).
Viz také
- Šířka cesty, jiný NP-kompletní optimalizační problém zahrnující lineární rozložení grafů.
Reference
- ^ (Chinn a kol. 1982 )
- ^ A b „Řešení NP-tvrdosti problému se šířkou pásma grafu“, Uriel Feige, Přednášky z informatiky, Svazek 1851, 2000, s. 129-145, doi:10.1007 / 3-540-44985-X_2
- ^ Poznámka k problému Hararyho. V. Chvátal, Československý matematický časopis 20(1):109–111, 1970. http://dml.cz/dmlcz/100949
- ^ Optimální označení produktu dvou cest. J. Chvatálová, Diskrétní matematika 11, 249–253, 1975.
- ^ Chinn a kol. 1982
- ^ Garey – Johnson: GT40
- ^ Ilya Safro a Dorit Ron a Achi Brandt (2008). "Víceúrovňové algoritmy pro problémy s lineárním objednáváním". ACM Journal of Experimental Algorithmics. 13: 1.4–1.20. doi:10.1145/1412228.1412232.
- Böttcher, J .; Pruessmann, K. P .; Taraz, A .; Würfl, A. (2010). "Šířka pásma, expanze, šířka stromu, oddělovače a univerzálnost pro grafy s omezeným stupněm". European Journal of Combinatorics. 31: 1217–1227. arXiv:0910.3014. doi:10.1016 / j.ejc.2009.10.010.CS1 maint: ref = harv (odkaz)
- Chinn, P. Z.; Chvátalová, J .; Dewdney, A. K.; Gibbs, N. E. (1982). „Problém se šířkou pásma pro grafy a matice - průzkum“. Journal of Graph Theory. 6: 223–254. doi:10,1002 / jgt.3190060302.CS1 maint: ref = harv (odkaz)
- Chung, Fan R. K. (1988), „Labelings of Graphs“, v Beineke, Lowell W .; Wilson, Robin J. (eds.), Vybraná témata v teorii grafů (PDF), Academic Press, s. 151–168, ISBN 978-0-12-086203-0CS1 maint: ref = harv (odkaz)
- Dubey, C .; Feige, U .; Unger, W. (2010). "Výsledky tvrdosti pro přibližnou šířku pásma". Journal of Computer and System Sciences. 77: 62–90. doi:10.1016 / j.jcss.2010.06.006.CS1 maint: ref = harv (odkaz)
- Garey, M.R.; Johnson, D.S. (1979). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti. New York: W.H. Freemane. ISBN 0-7167-1045-5.CS1 maint: ref = harv (odkaz)
- Gruber, Hermann (2012), „On Balanced Separators, Treewidth, and Cycle Rank“, Journal of Combinatorics, 3 (4): 669–682, arXiv:1012.1344, doi:10.4310 / joc.2012.v3.n4.a5CS1 maint: ref = harv (odkaz)
- Harper, L. (1966). "Optimální číslování a izoperimetrické problémy v grafech". Journal of Combinatorial Theory. 1: 385–393. doi:10.1016 / S0021-9800 (66) 80059-5.CS1 maint: ref = harv (odkaz)
- Kaplan, Haim; Shamir, Ron (1996), "Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques", SIAM Journal on Computing, 25 (3): 540–561, doi:10.1137 / s0097539793258143CS1 maint: ref = harv (odkaz)
- Karpinski, Marek; Wirtgen, Jürgen; Zelikovsky, Aleksandr (1997). „Aproximační algoritmus pro problém šířky pásma na hustých grafech“. Elektronické kolokvium o výpočetní složitosti. 4 (17).CS1 maint: ref = harv (odkaz)
externí odkazy
- Problém s minimální šířkou pásma, in: Pierluigi Crescenzi a Viggo Kann (eds.), Kompendium problémů s optimalizací NP. Zpřístupněno 26. května 2010.