stringtranslate.com

Структура уровня

Пример неориентированного графа с вершиной r и соответствующей ему структурой уровней

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

Определение и построение

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

Структуру уровней графа можно вычислить с помощью варианта поиска в ширину : [2] : 176 

уровень алгоритма -BFS(G, r): В ← {р} для ℓ от 0 до ∞: process(Q, ℓ) // множество Q содержит все вершины на уровне ℓ отметить все вершины в Q как обнаруженные Q' ← {} для u в Q: для каждого ребра (u, v): если v еще не отмечено: добавить v к Q' если Q' пуст: возврат Q ← Q'

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

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

Приложения

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

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

Ссылки

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