Wykres przepustowości - Graph bandwidth

W teorii wykres The problem pasma wykres jest etykieta z n wierzchołki v _I grafu G z różnych liczb f ( v _I ), tak, że ilość jest zminimalizowany ( e jest zestaw krawędzi G ). Problem można sobie wyobrazić jako umieszczenie wierzchołków wykresu w różnych punktach całkowitych wzdłuż osi x, tak aby zminimalizować długość najdłuższej krawędzi. Takie rozmieszczenie nazywa się liniowym układem wykresu , liniowym układem wykresu lub liniowym rozmieszczeniem wykresu . ${\ Displaystyle \ max \ {\, | f (v_ {i}) - f (v_ {j}) |: v_ {i} v_ {j} \ in E \, \}}$

Ważony błąd pasma wykres jest uogólnieniem, przy czym krawędzie są przypisane wagi w _ij oraz funkcja kosztu być zminimalizowane jest . ${\ Displaystyle \ max \ {\, w_ {ij} | f (v_ {i}) - f (v_ {j}) |: v_ {i} v_ {j} \ in E \, \}}$

W zakresie, matryca (nieważony) pasma wykres jest pasmo o matrycy symetryczny , który jest matryca przylegania wykresu. Szerokość pasma może być również zdefiniowana jako o jeden mniejsza niż maksymalny rozmiar kliki w odpowiednim supergrrafie interwałowym danego wykresu, dobranym tak, aby zminimalizować rozmiar jego kliki ( Kaplan i Shamir 1996 ).

Formuły przepustowości dla niektórych wykresów

W przypadku kilku rodzin wykresów szerokość pasma jest określona za pomocą wyraźnego wzoru. ${\ Displaystyle \ varphi (G)}$

Szerokość pasma wykresu ścieżki P _n na n wierzchołkach wynosi 1, a dla pełnego grafu K _m mamy . Dla pełnego wykresu dwudzielnego K _{m , n} , ${\ Displaystyle \ varphi (K_ {n}) = n-1}$

${\ Displaystyle \ varphi (K_ {m, n}) = \ lfloor (m-1) / 2 \ rfloor + n}$ , zakładając ${\ Displaystyle m \ geq n \ geq 1,}$

co zostało udowodnione przez Chvátala. Jako szczególny przypadek tego wzoru, graf gwiazdowy na  wierzchołkach k + 1 ma szerokość pasma . ${\ Displaystyle S_ {k} = K_ {k, 1}}$${\ Displaystyle \ varphi (S_ {k}) = \ lfloor (k-1) / 2 \ rfloor +1}$

Dla wykresu hipersześcianowego na wierzchołkach szerokość pasma została określona przez Harpera (1966) jako ${\ displaystyle Q_ {n}}$${\ displaystyle 2 ^ {n}}$

${\ Displaystyle \ varphi (Q_ {n}) = \ suma _ {m = 0} ^ {n-1} {\ binom {m} {\ lfloor m / 2 \ rfloor}}.}$

Chvátalová wykazały, że szerokość pasma m  x  n kwadratowy wykres siatki , to jest im iloczyn dwóch wykresach na ścieżce i wierzchołków, wynosi min { m , n }. ${\ displaystyle P_ {m} \ razy P_ {n}}$${\ displaystyle m}$${\ displaystyle n}$

Miedza

Szerokość pasma wykresu może być ograniczona różnymi innymi parametrami wykresu. Na przykład, pozwalając χ ( G ) oznacza liczbę chromatyczną o G ,

${\ Displaystyle \ varphi (G) \ geq \ chi (G) -1;}$

pozwalając średnica ( G ) oznacza średnicę od G , posiadają następujące nierówności:

${\ displaystyle \ lceil (n-1) / \ operatorname {diam} (G) \ rceil \ leq \ varphi (G) \ równoważnik n- \ operatorname {diam} (G),}$

gdzie jest liczbą wierzchołków w . ${\ displaystyle n}$${\ displaystyle G}$

Jeśli wykres G ma szerokość pasma k , to jego szerokość ścieżki wynosi co najwyżej k ( Kaplan i Shamir 1996 ), a głębokość jego drzewa wynosi co najwyżej k  log ( n / k ) ( Gruber 2012 ). W przeciwieństwie do tego, jak zauważono w poprzedniej sekcji, graf gwiazdowy S _k , strukturalnie bardzo prosty przykład drzewa , ma stosunkowo dużą szerokość pasma. Zauważ, że pathwidth od S _k wynosi 1, a jej głębokość jest drzewo-2.

Niektóre rodziny grafów o ograniczonym stopniu mają pasmo podliniowe: Chung (1988) udowodnił, że jeśli T jest drzewem o maksymalnym stopniu co najwyżej ∆, to

${\ Displaystyle \ varphi (T) \ równoważnik {\ Frac {5n} {\ log _ {\ Delta} n}}.}$

Mówiąc bardziej ogólnie, w przypadku grafów planarnych o ograniczonym maksymalnym stopniu co najwyżej ∆ zachodzi podobna granica (por. Böttcher et al. 2010 ):

${\ Displaystyle \ varphi (G) \ równoważnik {\ Frac {20n} {\ log _ {\ Delta} n}}.}$

Obliczanie przepustowości

Zarówno wersja nieważona, jak i ważona są specjalnymi przypadkami problemu kwadratowego przypisania wąskiego gardła . Problem z przepustowością jest NP-trudny , nawet w niektórych szczególnych przypadkach. Jeśli chodzi o istnienie wydajnych algorytmów aproksymacyjnych , wiadomo, że przepustowość jest NP-trudna do przybliżenia w ramach dowolnej stałej, co ma miejsce nawet wtedy, gdy wykresy wejściowe są ograniczone do drzew gąsienic o maksymalnej długości włosa 2 ( Dubey, Feige & Unger 2010 ) . W przypadku gęstych grafów algorytm 3-aproksymacji został zaprojektowany przez Karpińskiego, Wirtgen i Zelikovsky (1997) . Z drugiej strony znanych jest wiele przypadków specjalnych, które można rozwiązywać wielomianowo. Heurystyczny algorytm otrzymania liniowych układów wykres małą szerokość pasma, jest algorytm Cuthill-McKee . Szybki wielopoziomowy algorytm obliczania szerokości pasma grafu został zaproponowany w.

Aplikacje

Zainteresowanie tym problemem pochodzi z niektórych obszarów zastosowań.

Jednym z obszarów jest obsługa macierzy rzadkich / pasm , a ogólne algorytmy z tego obszaru, takie jak algorytm Cuthilla – McKee , mogą być stosowane do znalezienia przybliżonych rozwiązań problemu szerokości pasma grafu.

Inną dziedziną zastosowań jest automatyzacja projektowania elektronicznego . W standardowej metodologii projektowania komórek typowe komórki standardowe mają tę samą wysokość, a ich rozmieszczenie jest rozmieszczone w kilku rzędach. W tym kontekście problem szerokości pasma wykresu modeluje problem umieszczenia zestawu standardowych komórek w jednym rzędzie w celu zminimalizowania maksymalnego opóźnienia propagacji (które zakłada się, że jest proporcjonalne do długości przewodu).

Zobacz też

• Szerokość ścieżki , inny problem optymalizacji NP-zupełnej obejmujący liniowe układy wykresów.

Bibliografia

• Böttcher, J .; Pruessmann, KP; Taraz, A .; Würfl, A. (2010). „Przepustowość, rozszerzenie, szerokość drzewa, separatory i uniwersalność dla grafów o ograniczonym stopniu”. European Journal of Combinatorics . 31 (5): 1217–1227. arXiv : 0910.3014 . doi : 10.1016 / j.ejc.2009.10.010 .
• Chinn, PZ ; Chvátalová, J .; Dewdney, AK ; Gibbs, NE (1982). „Problem przepustowości dla wykresów i macierzy - ankieta”. Journal of Graph Theory . 6 (3): 223–254. doi : 10.1002 / jgt.3190060302 .
• Chung, Fan RK (1988), „Labelings of Graphs”, w Beineke, Lowell W .; Wilson, Robin J. (red.), Selected Topics in Graph Theory (PDF) , Academic Press, str. 151–168, ISBN   978-0-12-086203-0
• Dubey, C .; Feige, U .; Unger, W. (2010). „Wyniki twardości dla przybliżenia szerokości pasma”. Journal of Computer and System Sciences . 77 : 62–90. doi : 10.1016 / j.jcss.2010.06.006 .
• Garey, MR ; Johnson, DS (1979). Komputery i trudność: przewodnik po teorii kompletności NP . Nowy Jork: WH Freeman. ISBN   0-7167-1045-5 .
• 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.a5
• Harper, L. (1966). „Optymalne numeracje i problemy izoperymetryczne na wykresach” . Journal of Combinatorial Theory . 1 (3): 385–393. doi : 10.1016 / S0021-9800 (66) 80059-5 .
• Kaplan, Haim; Shamir, Ron (1996), „Pathwidth, bandwidth, and finish problems to correct interval graphs with small cliques”, SIAM Journal on Computing , 25 (3): 540–561, doi : 10.1137 / s0097539793258143
• Karpiński, Marek; Wirtgen Jürgen; Zelikovsky, Aleksandr (1997). „Algorytm aproksymacji dla problemu przepustowości na gęstych grafach” . Elektroniczne kolokwium na temat złożoności obliczeniowej . 4 (17).

Linki zewnętrzne

• Problem minimalnej przepustowości , w: Pierluigi Crescenzi i Viggo Kann (red.), Kompendium problemów optymalizacji NP. Dostęp 26 maja 2010.