레벨 구조

Level structure
대수 기하학의 개념은 수준 구조(알지브라질 기하학)를 참조한다.

그래프 이론의 수학적 하위 영역에서, 비방향 그래프의 수준 구조는 정점을 주어진 뿌리 꼭지점으로부터 같은 거리를 갖는 부분 집합으로 분할하는 것이다.[1]

정의 및 시공

V와 연결된 그래프 G = (V, E) 에지 집합과 E 에지 집합, 그리고 루트 꼭지점 r이 있는 경우, 레벨 구조는 정점을 r에서 거리 i의 정점으로 구성된 레벨이라고 불리는 하위 집합 L로i 분할하는 것이다.동등하게, 이0 집합은 L = {r}을(를) 설정한 다음, i > 0에 대해 L을i L의i − 1 정점에 인접하지만 그 자신이 이전의 수준에 있지 않은 정점 집합으로 정의할 수 있다.[1]

그래프의 수준 구조는 폭 우선 검색의 변형으로 계산할 수 있다.[2]: 176 

algorithm level-BFS(G, r):     Q ← {r}     for ℓ from 0 to ∞:         process(Q, ℓ)  // the set Q holds all vertices at level ℓ         mark all vertices in Q as discovered         Q' ← {}         for u in Q:             for each edge (u, v):                 if v is not yet marked:                     add v to Q'         if Q' is empty:Q ← Q' 반환

특성.

레벨 구조에서 G의 각 가장자리는 동일한 레벨 내에 두 끝점을 모두 가지거나 두 끝점이 연속적인 레벨에 있다.[1]

적용들

그래프의 수준 구조로 분할된 그래프는 그래프 대역폭과 같은 그래프 레이아웃 문제에 대해 경험적 접근법으로 사용될 수 있다.[1]커트힐-맥키 알고리즘은 각 수준 내의 추가 분류 단계에 기초하여 이 아이디어를 정교하게 다듬은 것이다.[3]

수준 구조는 희소 행렬에 대한 알고리즘과 [4]평면 그래프의 분리자를 구성하는 데도 사용된다.[5]

참조

  1. ^ a b c d Díaz, Josep; Petit, Jordi; Serna, Maria (2002), "A survey of graph layout problems" (PDF), ACM Computing Surveys, 34 (3): 313–356, CiteSeerX 10.1.1.12.4358, doi:10.1145/568522.568523, S2CID 63793863.
  2. ^ Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer.
  3. ^ Cuthill, E.; McKee, J. (1969), "Reducing the bandwidth of sparse symmetric matrices", Proceedings of the 1969 24th national conference (ACM '69), ACM, pp. 157–172, doi:10.1145/800195.805928, S2CID 18143635.
  4. ^ George, J. Alan (1977), "Solution of linear systems of equations: direct methods for finite element problems", Sparse matrix techniques (Adv. Course, Technical Univ. Denmark, Copenhagen, 1976), Berlin: Springer, pp. 52–101. Lecture Notes in Math., Vol. 572, MR 0440883.
  5. ^ Lipton, Richard J.; Tarjan, Robert E. (1979), "A separator theorem for planar graphs", SIAM Journal on Applied Mathematics, 36 (2): 177–189, CiteSeerX 10.1.1.214.417, doi:10.1137/0136016.