Скобочная Форма Описания Графиков

Написать эту заметку меня побудила статья « Хранение иерархических данных в плоском виде ", в которой автор решает задачу хранения дерева комментариев в виде плоского текста.

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

Автор описанного подхода – старший научный сотрудник Института физики полупроводников СО РАН В.

А.

Мелентьев.

Впервые он предложил новый метод формального описания графов в 2000 году в статье «Скобочная форма для описания графов и ее использование в структурных исследованиях живучих вычислительных систем».

Так какой смысл?

Известны две формы описания графа: графическая и матричная.

Графическая форма — это отображение на плоскости перечислимого множества вершин в виде узлов (точек) и линий связи (дуг, ребер), непосредственно соединяющих эти вершины.

Форма матрицы, в зависимости от выбора строк и столбцов, образующих матрицу, называется матрицей смежности (строки и столбцы соответствуют вершинам графа), матрицей инцидентности (строки — вершины, столбцы — ребра) и матрицей смежности ребер.

матрица (элементы строк и столбцов являются ребрами графа).

Понятно, что в отличие от графической формы матричная форма предполагает введение однозначных обозначений соответствующих элементов графа, например нумерации.

Чтобы избежать разногласий, приведу некоторые общеизвестные определения, а также основные сведения об изображениях графов, используемых в статье.

График Ж это упорядоченная пара Г(В, Е) , в которой В представляет собой непустой набор вершин или узлов, ? — набор пар вершин, называемых ребрами.

Пики ты И в называются конечными вершинами (или просто концами) ребра е = {и, v} .

Ребро, в свою очередь, соединяет эти вершины.

Две концевые вершины одного и того же ребра называются смежными.

Градус(в) пики в называется количество ребер, для которых он является концом.

Говоря простым языком, это количество ребер, исходящих из вершины.

Изображение P(v_я ) график Г(В, Е) — описание графа в скобочной форме, начальной точкой (перспективной вершиной) которого является вершина в _я ∈ В .

Установить Н(ш) - обстановка саммита ш , состоящий из s(ш) = град(ш) пики Установить М_я - множество вершин, расположенных на я -й уровень проекции.

С_я — общее количество вершин я уровень проекции.

Объектами исследования являются, как правило, связные неориентированные графы с равновесными ребрами, без кратных ребер и без петель.

Продемонстрируем построение скобочной проекции на примере единичного куба.

Скобочная форма описания графиков

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

Выберем начальную вершину (выбор может быть произвольным или мотивированным, в нашем случае в ₀ =0) и разместим его на нулевом уровне, соседние с ним вершины разместим на 1-м уровне выше и правее исходного.

Просмотр окружения вершин Н(0) = {1, 2, 3} представляет собой набор вершин уровня 1: М ₁ ={1, 2, 3}, | М ₁ |= С ₁ =3. 0^{{1, 2, 3}} Итак, на нулевом и первом уровнях образа рассматриваемого графа одна вершина из | В | = 8 и три ребра из | ? | = 12. Продолжим описание до 2-го уровня.

Куча М ₂ Пики 2-го уровня объединяются С ₁ = 3 подмножества, являющихся окружениями (без вершины 0, непосредственно предшествующей этим подмножествам) трёх вершин 1-го уровня: М ₂ = М ₂₁ ты М ₂₂ ты М ₂₃ = {4, 5} U {4, 6} U {5, 6} = {4, 5, 6}, а С ₂ = 6, а | М ₂ | = 3. Мы получаем: 0^{{1^{{4, 5}} , 2^{{4, 6}} , 3^{{5, 6}} }} В целом, начиная со 2-го уровня, каждый последующий уровень представляет собой коллекцию, а не набор вершин, поскольку он может содержать повторяющиеся элементы.

Обратите внимание, что М ₁ ты М ₂ ≠ В , следовательно, построение проекции необходимо продолжить на следующем уровне.

Куча М ₃ вершин 3-го уровня состоит из 6 подмножеств, которые являются окружениями соответствующих 6 вершин 2-го уровня, каждое из которых модифицируется путем вычитания наборов вершин, предшествующих этому окружению: М ₃ = М ₃₄ ¹ ты М ₃₅ ¹ ты М ₃₄ ² ты М ₃₆ ¹ ты М ₃₅ ² ты М ₃₆ ² .

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

Из построенной таким образом проекции 0^{{1^{{4^{{2, 7}} , 5^{{3, 7}} }} , 2^{{4^{{1, 7}} , 6^{{3, 7}} }} , 3^{{5^{{1, 7}} , 6^{{2, 7}} }} }} Видно, что только на 3-м уровне появляется вершина 7, не входящая ни в одно из подмножеств предыдущих уровней: М ₃ = {2, 7} U {3, 7} U {1, 7} U {3, 7} U {1,7} U {2, 7} = {1, 2, 3, 7}.

С ₃ = 12. | М ₃ | = 4. Однолинейный вариант той же проекции имеет вид п₃ (0) = 0{1{4{2, 7}, 5{3, 7}}, 2{4{1, 7}, 6{3, 7}}, 3{5{1, 7}, 6{2, 7}}}.

Раскрывающиеся скобки перед тем или иным подмножеством вершин указывают на его вложенность, а количество скобок, «непогашенных» закрывающими, определяет уровень вложенности этого подмножества в множества вершин-предшественников.

Уровень вложенности подмножества в множество потомков перспективной вершины (номер уровня в проекции) определяет его расстояние от вершин соответствующего подмножества.

Проекция графика п_к (в_о ) считается полным, если он определяет все вершины и все ребра (отношения смежности) этого графа.

Из проекции выше п₃ (0) ясно, что и условия вершинной, и реберной полноты здесь выполняются только на 3-м уровне: М₀ ты М₁ ты М₂ ты М₃ = В , | М₀ ты М₁ ты М₂ ты М₃ | = | В | = 8 ?₀ ты ?₁ ты ?₂ ты ?₃ = ? , | ?₀ ты ?₁ ты ?₂ ты ?₃ | = | ? | = 12

Некоторые свойства изображения скобки

Каждый уровень скобочного образа невзвешенного графа содержит множество концевых вершин всех уникальных (неповторяющихся) простых цепей, исходящих из начальной вершины, длины которых равны номеру этого уровня.

Рассмотрим набор вершин к -й уровень.

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

Сюда не могут быть включены вершины, расстояние которых от начальной вершины превышает номер уровня.

к .

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

И как его использовать?

В отличие от известных графических и матричных представлений, изображение графа в скобках обладает повышенной информативностью, так как помимо явно заданной информации о множествах вершин и ребер графа и их смежности или инцидентности, изображение в скобках дает информация о наборах маршрутов между вершинами, их длинах и т. д. Наличие дополнительной информации в описании графа позволяет заменить достаточно трудоемкие алгоритмы, например, поиск кратчайших маршрутов, поиск маршрутов, не пересекающихся пары вершин, определяющие радиус, диаметр и обход графа, эксцентриситет его вершин и многие другие типичные проблемы на графах с достаточно простой операцией выборки искомых значений или объектов, «лежащих на поверхности» таких описание.

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

Попытки закрепить такие участки в обычных алгоритмах для последующего использования в качестве промежуточных результатов приводят к неоправданному усложнению логики этих алгоритмов для особо сложных графов, что, в свою очередь, может привести к обратному эффекту: увеличению сложности таких алгоритмов с непредсказуемость результатов из-за их недостаточной «прозрачности»» Аппарат скобочных образов был успешно опробован Мелентьевым при решении некоторых классических задач теории графов, в частности, о кратчайших и непересекающихся маршрутах, об эксцентриситетах вершин, о диаметре графа и т. д.