Структура уровней

В математическом подразделе теории графов структура уровней неориентированного графа представляет собой разбиение вершин на подмножества , находящиеся на одинаковом расстоянии от заданной корневой вершины. ^[1]

Определение и конструкция

Для связного графа G = ( V , E ) с V — набором вершин и E — набором ребер , а также с корневой вершиной r , структура уровней представляет собой разбиение вершин на подмножества L _i , называемые уровнями, состоящие из вершины на расстоянии i от r . Эквивалентно, этот набор можно определить, установив 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:
            return
        Q ← Q'

Характеристики

В уровневой структуре каждое ребро G либо имеет обе конечные точки на одном уровне, либо две его конечные точки находятся на последовательных уровнях. ^[1]

Приложения

Разделение графа на его структуру уровней может использоваться в качестве эвристики для решения проблем компоновки графа, таких как пропускная способность графа . ^[1] Алгоритм Катхилла-Макки представляет собой усовершенствование этой идеи, основанное на дополнительном этапе сортировки внутри каждого уровня. ^[3]

Структуры уровней также используются в алгоритмах для разреженных матриц . ^[4] и для построения разделителей планарных графов . ^[5]

Ссылки

^ Jump up to: ^а ^б ^с ^д Диас, Хосеп; Пети, Жорди; Серна, Мария (2002), «Обзор проблем компоновки графов» (PDF) , ACM Computing Surveys , 34 (3): 313–356, CiteSeerX 10.1.1.12.4358 , doi : 10.1145/568522.568523 , S2CID 63793863 .
^ Мельхорн, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF) . Спрингер.
^ Катхилл, Э .; Макки, Дж. (1969), «Уменьшение пропускной способности разреженных симметричных матриц», Труды 24-й национальной конференции 1969 года (ACM '69) , ACM, стр. 157–172, doi : 10.1145/800195.805928 , S2CID 18143635 .
^ Джордж, Дж. Алан (1977), «Решение линейных систем уравнений: прямые методы для задач конечных элементов», Методы разреженных матриц (Adv. Course, Технический университет Дании, Копенгаген, 1976) , Берлин: Springer, стр. 52 –101. Конспекты лекций по математике, Vol. 572, МР 0440883 .
^ Липтон, Ричард Дж .; Тарьян, Роберт Э. (1979), «Теорема о разделителе для плоских графов», SIAM Journal on Applied Mathematics , 36 (2): 177–189, CiteSeerX 10.1.1.214.417 , doi : 10.1137/0136016 .

[dps-1] Jump up to: ^а ^б ^с ^д Диас, Хосеп; Пети, Жорди; Серна, Мария (2002), «Обзор проблем компоновки графов» (PDF) , ACM Computing Surveys , 34 (3): 313–356, CiteSeerX 10.1.1.12.4358 , doi : 10.1145/568522.568523 , S2CID 63793863 .

[mehlhorn-2] Мельхорн, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF) . Спрингер.

[3] Катхилл, Э .; Макки, Дж. (1969), «Уменьшение пропускной способности разреженных симметричных матриц», Труды 24-й национальной конференции 1969 года (ACM '69) , ACM, стр. 157–172, doi : 10.1145/800195.805928 , S2CID 18143635 .

[4] Джордж, Дж. Алан (1977), «Решение линейных систем уравнений: прямые методы для задач конечных элементов», Методы разреженных матриц (Adv. Course, Технический университет Дании, Копенгаген, 1976) , Берлин: Springer, стр. 52 –101. Конспекты лекций по математике, Vol. 572, МР 0440883 .

[5] Липтон, Ричард Дж .; Тарьян, Роберт Э. (1979), «Теорема о разделителе для плоских графов», SIAM Journal on Applied Mathematics , 36 (2): 177–189, CiteSeerX 10.1.1.214.417 , doi : 10.1137/0136016 .

[1]

[2]

[3]

[4]

[5]