그래프 대역폭

In graph theory, the graph bandwidth problem is to label the n vertices v_i of a graph G with distinct integers f(v_i) so that the quantity ${\displaystyle \max\{\, f(v_{i})-f(v_{j}) :v_{i}v_{j}\in E\,\}}$ is minimized (E is the edge set of G).^[1]문제는 그래프의 정점을 x축을 따라 뚜렷한 정수점에 배치하여 가장 긴 에지의 길이가 최소화되도록 시각화할 수 있다.이러한 배치를 선형 그래프 배열, 선형 그래프 레이아웃 또는 선형 그래프 배치라고 한다.^[2]

The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights w_ij and the cost function to be minimized is ${\displaystyle \max\{\,w_{ij} f(v_{i})-f(v_{j}) :v_{i}v_{j}\in E\,\}}$.

행렬의 측면에서 (가중치 않은) 그래프 대역폭은 그래프의 인접 행렬인 대칭 행렬의 최소 대역폭이다.대역폭은 또한 해당 그래프의 클라이크 크기를 최소화하기 위해 선택한 해당 그래프의 적절한 간격 수퍼그래프에서 최대 클라이크 크기보다 한 개 작은 것으로 정의될 수 있다(Kaplan & Shamir 1996).

일부 그래프의 대역폭 공식

여러 그래프 패밀리의 경우 대역폭 $){\displaystyle \varphi(G)}$은 명시적 공식으로 주어진다$$.

n 꼭지점에 대한 경로 그래프_n P의 대역폭은 1이며, 전체 그래프_m K의 경우 $\phi {\displaystyle ({Kn}_{}{}_{}}$ =${\displaystyle n}$ - ${\displaystyle 1}${\$displaystyle \varphi(K_{n}=n-1$ 전체 초당 그래프 K에_m,n 대해,

${\displaystyle \phi }$( ${\displaystyle K_{}}$ ${\displaystyle m_{}}$, n${\displaystyle {}_{}}$)${\displaystyle }$= ${\displaystyle \lfloor }$( ${\displaystyle m}$- 1${\displaystyle }$)${\displaystyle }$/ ${\displaystyle \rfloor }$ ( m - ${\displaystyle 1}$ ) / ⌋${\displaystyle }$+ ${\displaystyle n}$ $({m,n})$ =\$displaystyle \varphi$(K_{m,$n})=\llfloor (m-1)/2\rfloor +n$$$}, m${\displaystyle }assuming{\displaystyle }$ $assuming$ $\\displaystaystym\geq.$

체바탈이 ^[3]증명해줬어As a special case of this formula, the star graph ${\displaystyle S_{k}=K_{k,1}}$ on k + 1 vertices has bandwidth ${\displaystyle \varphi (S_{k})=\lfloor (k-1)/2\rfloor +1}$.

${\displaystyle {2n}^{}}$ ${\$ 정점에 $대한$ 하이퍼큐브 $그래프{\displaystyle {}_{}}$ ${\displaystyle {Qn}_{}}${\$displaystyle Q_{n}$의 경우 대역폭은 Harper(1966)에 의해 결정되었다.

${\displaystyle \varphi (Q_{n}}=\sum _{m=0}^{n-1}{\binom {m}{\llloor m/2\rfloor }}}.}$

Chvatalova는 m^[4] × n 제곱 그리드 그래프 ${\displaystyle P_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ P ${\displaystyle n_{}}$ ${\$ $즉{\displaystyle }$ m$${\$displaystyle m}$과 n$${\$displaystyle n$} 정점에$$ 대한 두 경로 그래프의 데카르트 곱은 최소값,n}과 같다는 것을 보여주었다.

경계

그래프의 대역폭은 다양한 다른 그래프 매개변수의 관점에서 경계할 수 있다.예를 들어, χ(G)이 G의 색수를 나타내도록 하는 것은,

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

let diam(G)은 G의 직경을 나타내며, 다음과 같은 불평등이 유지된다.^[5]

${\displaystyle \lceil (n-1)/\operatorname {diam}(G)\rceil \leq \varphi(G)\leq n-\operatorname {diam}(G),}$

여기서 $n{\displaystyle }$ ${\displaystyle n}$은(는) $G{\displaystyle }$ ${\displaystyle G}$의 정점 수입니다$.$

그래프 G에 대역폭 k가 있으면 경로 너비는 최대 k(Kaplan & Shamir 1996), 트리 깊이는 최대 k log(n/k)이다(Gruber 2012).이와는 대조적으로, 앞의 절에서 언급한 바와 같이, 구조적으로 매우 단순한 트리의 예인 별 그래프_k S는 상대적으로 대역폭이 크다.S의_k 경로 폭은 1이고, 나무 깊이는 2인 것을 관찰한다.

경계가 있는 일부 그래프 계열은 하위선형 대역폭을 가지고 있다:정(1988)은 T가 기껏해야 최대 ∆의 나무라면 그 다음이라는 것을 증명했다.

${\displaystyle \varphi(T)\leq {5n}{\log _{\Delta }n}}.}$

더 일반적으로, 최대 ∆의 경계 최대도의 평면 그래프의 경우 유사한 경계 홀드(cf)가 있다.Bötcher 외 2010):

${\displaystyle \varphi (G)\leq {20n}{\log _{\Delta }n}}.}$

대역폭 계산

가중치가 없는 버전과 가중치 있는 버전 모두 2차 병목현상 할당 문제의 특별한 경우다.대역폭 문제는 일부 특별한 경우에도 NP-hard이다.^[6]효율적 근사 알고리즘의 존재에 대해, 대역폭은 어떤 상수 내에서 근사치 하기에는 NP-힘든 것으로 알려져 있으며, 입력 그래프가 최대 털 길이 2(Dubey, Feige & Unger 2010)의 애벌레 나무로 제한될 때도 이를 지탱한다.밀도가 높은 그래프의 경우 카르핀스키, 위르트겐 & 젤리코프스키(1997)가 3-대략 알고리즘을 설계했다.반면 다항식 해결 가능한 특례는 다수 알려져 있다.^[2]낮은 대역폭의 선형 그래프 레이아웃을 얻기 위한 경험적 알고리즘은 Cuthill-McKey 알고리즘이다.그래프 대역폭 계산을 위한 빠른 멀티레벨 알고리즘이 제안되었다.^[7]

적용들

이 문제에 대한 관심은 일부 응용 분야로부터 온다.

한 영역은 희박한 매트릭스/밴드 매트릭스 처리로, 커트힐-맥키 알고리즘과 같은 이 영역의 일반 알고리즘을 적용하여 그래프 대역폭 문제에 대한 대략적인 해결책을 찾을 수 있다.

또 다른 애플리케이션 영역은 전자 설계 자동화에 있다.표준 세포 설계 방법론에서 일반적으로 표준 세포의 높이는 같으며, 그 위치는 여러 행으로 배열된다.이러한 맥락에서, 그래프 대역폭 문제는 최대 전파 지연(선 길이에 비례하는 것으로 가정되는)을 최소화하는 것을 목표로, 표준 셀 세트를 하나의 열에 배치하는 문제를 모델링한다.

참고 항목

• 경로 폭, 그래프의 선형 레이아웃과 관련된 다른 NP-완전한 최적화 문제.

참조

• Böttcher, J.; Pruessmann, K. P.; Taraz, A.; Würfl, A. (2010). "Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs". European Journal of Combinatorics. 31 (5): 1217–1227. arXiv:0910.3014. doi:10.1016/j.ejc.2009.10.010.
• Chinn, P. Z.; Chvátalová, J.; Dewdney, A. K.; Gibbs, N. E. (1982). "The bandwidth problem for graphs and matrices—a survey". Journal of Graph Theory. 6 (3): 223–254. doi:10.1002/jgt.3190060302.
• Chung, Fan R. K. (1988), "Labelings of Graphs", in Beineke, Lowell W.; Wilson, Robin J. (eds.), Selected Topics in Graph Theory (PDF), Academic Press, pp. 151–168, ISBN 978-0-12-086203-0
• Dubey, C.; Feige, U.; Unger, W. (2010). "Hardness results for approximating the bandwidth". Journal of Computer and System Sciences. 77: 62–90. doi:10.1016/j.jcss.2010.06.006.
• Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. 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). "Optimal numberings and isoperimetric problems on graphs". Journal of Combinatorial Theory. 1 (3): 385–393. doi:10.1016/S0021-9800(66)80059-5.
• 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/s0097539793258143
• Karpinski, Marek; Wirtgen, Jürgen; Zelikovsky, Aleksandr (1997). "An Approximation Algorithm for the Bandwidth Problem on Dense Graphs". Electronic Colloquium on Computational Complexity. 4 (17).

외부 링크

• 최소 대역폭 문제, in: Pierluigi Crescenzi 및 Viggo Kann(eds), NP 최적화 문제의 요약.2010년 5월 26일 접속.