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

О концепции в алгебраической геометрии см. структура уровней (алгебраическая геометрия)

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

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

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

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

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

Свойства

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

Приложения

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

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

использованная литература

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