В математической подполе теории графов структура уровней из неориентированного графа является разбиением из вершин на подмножества , которые имеют один и то же расстояние от заданной корневой вершины. [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): Q ← {r} для ℓ от 0 до ∞: process (Q, ℓ) // множество Q содержит все вершины уровня пометьте все вершины в Q как обнаруженные Q '← {} для u в Q: для каждого ребра (u, v): если v еще не отмечен: добавить v к Q ' если Q 'пусто: возврат Q ← Q '
Характеристики
В структуре уровней каждое ребро G либо имеет обе конечные точки на одном уровне, либо две его конечные точки находятся на последовательных уровнях. [1]
Приложения
Разделение графа на его структуру уровней может использоваться в качестве эвристики для проблем компоновки графа, таких как пропускная способность графа . [1] алгоритм Cuthill-Макки является уточнением этой идеи, основываясь на дополнительной стадии сортировки в пределах каждого уровня. [3]
Структуры уровня также используются в алгоритмах для разреженных матриц , [4] и для построения сепараторов плоских графов . [5]
Рекомендации
- ^ a b c d Диас, Хосеп; Petit, Jordi; Серна, Мария (2002), «Обзор проблем компоновки графов» (PDF) , ACM Computing Surveys , 34 (3): 313–356, CiteSeerX 10.1.1.12.4358 , doi : 10.1145 / 568522.568523.
- ^ Мельхорн, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: Basic Toolbox (PDF) . Springer.
- ^ Cuthill, E .; Макки, J. (1969), "Уменьшение ширины полосы разреженных симметричных матриц", Труды 24 - е 1969 национальной конференции (ACM '69) , АСМ, стр 157-172,. DOI : 10,1145 / 800195,805928.
- ^ Джордж, Дж. Алан (1977), "Решение линейных систем уравнений: прямые методы для задач конечных элементов", Методы разреженных матриц (Adv. Course, Технический университет Дании, Копенгаген, 1976) , Берлин: Springer, стр. 52 –101. Конспект лекций по математике, Vol. 572, Руководство MR 0440883.
- ^ Липтон, Ричард Дж .; Тарьян, Роберт Е. (1979), "Теорема Сепаратор для плоских графов", SIAM журнал по прикладной математике , 36 (2): 177-189, CiteSeerX 10.1.1.214.417 , DOI : 10,1137 / 0136016.