Структура уровней - Level structure

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

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

Для связного графа G = ( V , E ), где V - множество вершин, а E - множество ребер , и с корневой вершиной r , структура уровней представляет собой разбиение вершин на подмножества L _i, называемые уровнями, состоящие из вершины на расстоянии i от r . Эквивалентно, это множество может быть определено, установив L ₀  = { r }, а затем, для i  > 0, определив L _i как набор вершин, которые являются соседями вершин в L _{i  - 1,} но сами не находятся в каком-либо более раннем уровень.

Уровневую структуру графа можно вычислить с помощью варианта поиска в ширину :

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 либо имеет обе конечные точки на одном уровне, либо две его конечные точки находятся на последовательных уровнях.

Приложения

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

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

Рекомендации