Написать эту заметку меня побудила статья «Хранение иерархических данных в плоском виде», в которой автор занимается решением задачи хранения дерева комментариев в виде плоского текста. Дерево это ведь граф, поэтому я вспомнил о молодом и мало известном аппарате описания графов их скобочными образами, на который наткнулся в процессе написания диссертации. О технологии построения скобочных образов графов я и расскажу.
Автор описываемого подхода — старший научный сотрудник Института физики полупроводников СО РАН В.А. Мелентьев. Новый способ формального описания графов впервые предложен им в 2000 году в статье «Скобочная форма описания графов и ее использование в структурных исследованиях живучих вычислительных систем».
Общеизвестны две формы описания графа: графическая и матричная. Графическая форма представляет собой отображение на плоскости перечислимого множества вершин в виде узлов (точек) и линий связи (дуг, ребер), непосредственно соединяющих эти вершины. Матричная форма в зависимости от выбора образующих матрицу строк и столбцов носит название матрицы смежности (строки и столбцы соответствуют вершинам графа), матрицы инцидентности (строки — вершины, столбцы — ребра) и матрицы смежности ребер (элементами строк и столбцов являются ребра графа). Понятно, что в отличие от графической формы матричная предполагает введение однозначных обозначений соответствующих элементов графа, например нумерации.
Во избежание разночтений приведу некоторые общеизвестные определения, а также основные сведения об образах графа, используемые в статье.
Граф G — это упорядоченная пара G(V, E), в которой V — непустое множество вершин или узлов, E — множество пар вершин, называемых ребрами.
Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u, v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются смежными.
Степенью deg(v) вершины v называют количество ребер, для которых она является концевой. Проще говоря, это количество исходящих из вершины ребер.
Образ P(vi) графа G(V, E) — описание графа в скобочной форме, отправной точкой (ракурсной вершиной) которого является вершина vi ∈ V.
Множество N(w) — окружение вершины w, состоящее из s(w) = deg(w) вершин.
Множество Mi — множество вершин, находящихся на i-ом уровне проекции.
Ci — общее число вершин i-го уровня проекции.
Объектами исследований являются, как правило, связные неориентированные графы с равновзвешенными ребрами без кратных ребер и без петель. Продемонстрируем построение скобочной проекции на примере единичного куба.
Для лучшего зрительного восприятия образа и для удобства работы с ним структурируем скобочное описание графа в виде конечного множества уровней. Выберем начальную вершину (выбор может произвольным или мотивированным, в нашем случае v0=0) и поместим ее на нулевом уровне, смежные ей вершины поместим на 1-ом уровне выше и правее начальной. Окружение ракурсной вершины N(0) = {1, 2, 3} составляет множество вершин 1-го уровня: M1={1, 2, 3}, |M1|= C1=3.
0{1, 2, 3}
Итак, на нулевом и первом уровнях образа рассматриваемого графа определена одна вершина из |V| = 8 и три ребра из |E| = 12.
Продолжим описание до 2-го уровня. Множество M2 вершин 2-го уровня объединяет в себе C1 = 3 подмножества, являющиеся окружениями (без вершины 0, непосредственно предшествующей этим подмножествам) трех вершин 1-го уровня:
M2 = M21 U M22 U M23 = {4, 5} U {4, 6} U {5, 6} = {4, 5, 6}, при этом C2 = 6, а |M2| = 3.
Получим:
0{1{4, 5}, 2{4, 6}, 3{5, 6}}
В общем случае, начиная со 2-го уровня, каждый последующий уровень представляет собой совокупность, а не множество вершин, так как в нее могут входить повторяющиеся элементы. Отметим, что M1 U M2 ≠ V, поэтому построение проекции необходимо продолжить следующим уровнем.
Множество M3 вершин 3-го уровня состоит из 6 подмножеств, представляющих собой окружения соответствующих им 6 вершин 2-го уровня, каждое из которых модифицировано вычитанием множеств предшествующих этому окружению вершин:
M3 = M341 U M351 U M342 U M361 U M352 U M362.
Здесь первая цифра нижнего индекса указывает на принадлежность к соответствующему уровню проекции, вторая идентифицирует вершину графа, а верхний индекс служит для дополнительной индексации нескольких экземпляров одной и той же вершины на рассматриваемом уровне проекции. Из построенной таким образом проекции
0{1{4{2, 7}, 5{3, 7}}, 2{4{1, 7}, 6{3, 7}}, 3{5{1, 7}, 6{2, 7}}}
видно, что только на 3-м уровне появляется вершина 7, не включенная в состав ни одного из подмножеств предшествующих уровней: M3= {2, 7} U {3, 7} U {1, 7} U {3, 7} U {1,7} U {2, 7} = {1, 2, 3, 7}. C3 = 12. |M3| = 4. Запись этой же проекции в однострочном варианте имеет вид
P3(0) = 0{1{4{2, 7}, 5{3, 7}}, 2{4{1, 7}, 6{3, 7}}, 3{5{1, 7}, 6{2, 7}}}.
Открывающиеся скобки перед тем или иным подмножеством вершин указывают на его вложенность, а число скобок, «непогашенных» закрывающимися, определяет уровень вложенности этого подмножества в множества вершин-предшественниц. Уровень вложенности подмножества в множество потомков ракурсной вершины (номер уровня в проекции) определяет ее удаленность от вершин соответствующего подмножества.
Проекция графа Pk(vo)считается полной, если ею определены все вершины и все ребра (отношения смежности) этого графа. Из приведенной выше проекции P3(0) видно, что и вершинное, и реберное условия полноты выполняются здесь только на 3-м уровне:
M0 U M1 U M2 U M3 = V, |M0 U M1 U M2 U M3| = |V| = 8
E0 U E1 U E2 U E3 = E, |E0 U E1 U E2 U E3| = |E| = 12
Каждый уровень скобочного образа не взвешенного графа содержит совокупность концевых вершин всех исходящих из начальной вершины уникальных (не повторяющихся) простых цепей, длины которых равны номеру этого уровня.
Рассмотрим совокупность вершин k-го уровня. В указанную совокупность входят концевые вершины всех исходящих из начальной вершины простых цепей, длины которых которых равны номеру этого уровня, включая вершины, расстояние которых от начальной вершины образа равно номеру этого уровня. Сюда не могут входить вершины, расстояние которых от начальной вершины превышает номер уровня k.
Если граф является гамильтоновым, то в множестве его вершин существует такая, что число уровней максимального образа, включая нулевой, равно числу вершин графа.
В отличие от общеизвестных графического и матричного представлений, скобочный образ графа обладает повышенной информативностью, так как помимо заданной в явном виде информации о множествах вершин и ребер графа и об их смежности или инцидентности, в скобочном образе в явной или в легко извлекаемой форме представлена информация о множествах маршрутов между вершинами, об их длинах и т.п. Наличие в описании графа дополнительной информации позволяет заменить довольно трудоемкие алгоритмы, например, поиска кратчайших маршрутов, поиска непересекающихся для пары вершин маршрутов, выявления радиуса, диаметра и обхода графа, эксцентриситета его вершин и многих других типичных задач на графах достаточно простой операцией выборки искомых величин или объектов, «лежащих на поверхности» такого описания.
Существенный выигрыш в трудоемкости еще более очевиден при сравнении между собой нескольких множеств подграфов, так как предложенная форма их представления позволяет исключить многократное повторение выполненных ранее ветвей или их участков. Попытки зафиксировать в обычных алгоритмах такие участки для последующего использования в качестве промежуточных результатов приводят к неоправданному усложнению логики этих алгоритмов для особо сложных графов, что, в свою очередь, может привести к обратному эффекту: увеличению трудоемкости таких алгоритмов при непредсказуемости результатов вследствие недостаточной их «прозрачности».
Аппарат скобочных образов успешно апробирован Мелентьевым в решении некоторых классических задач теории графов, в частности, о кратчайших и непересекающихся маршрутах, об эксцентриситетах вершин, о диаметре графа и т.д.
Список трудов В.А. Мелентьева
Автор описываемого подхода — старший научный сотрудник Института физики полупроводников СО РАН В.А. Мелентьев. Новый способ формального описания графов впервые предложен им в 2000 году в статье «Скобочная форма описания графов и ее использование в структурных исследованиях живучих вычислительных систем».
Так в чем же суть?
Общеизвестны две формы описания графа: графическая и матричная. Графическая форма представляет собой отображение на плоскости перечислимого множества вершин в виде узлов (точек) и линий связи (дуг, ребер), непосредственно соединяющих эти вершины. Матричная форма в зависимости от выбора образующих матрицу строк и столбцов носит название матрицы смежности (строки и столбцы соответствуют вершинам графа), матрицы инцидентности (строки — вершины, столбцы — ребра) и матрицы смежности ребер (элементами строк и столбцов являются ребра графа). Понятно, что в отличие от графической формы матричная предполагает введение однозначных обозначений соответствующих элементов графа, например нумерации.
Во избежание разночтений приведу некоторые общеизвестные определения, а также основные сведения об образах графа, используемые в статье.
Граф G — это упорядоченная пара G(V, E), в которой V — непустое множество вершин или узлов, E — множество пар вершин, называемых ребрами.
Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u, v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются смежными.
Степенью deg(v) вершины v называют количество ребер, для которых она является концевой. Проще говоря, это количество исходящих из вершины ребер.
Образ P(vi) графа G(V, E) — описание графа в скобочной форме, отправной точкой (ракурсной вершиной) которого является вершина vi ∈ V.
Множество N(w) — окружение вершины w, состоящее из s(w) = deg(w) вершин.
Множество Mi — множество вершин, находящихся на i-ом уровне проекции.
Ci — общее число вершин i-го уровня проекции.
Объектами исследований являются, как правило, связные неориентированные графы с равновзвешенными ребрами без кратных ребер и без петель. Продемонстрируем построение скобочной проекции на примере единичного куба.
Для лучшего зрительного восприятия образа и для удобства работы с ним структурируем скобочное описание графа в виде конечного множества уровней. Выберем начальную вершину (выбор может произвольным или мотивированным, в нашем случае v0=0) и поместим ее на нулевом уровне, смежные ей вершины поместим на 1-ом уровне выше и правее начальной. Окружение ракурсной вершины N(0) = {1, 2, 3} составляет множество вершин 1-го уровня: M1={1, 2, 3}, |M1|= C1=3.
0{1, 2, 3}
Итак, на нулевом и первом уровнях образа рассматриваемого графа определена одна вершина из |V| = 8 и три ребра из |E| = 12.
Продолжим описание до 2-го уровня. Множество M2 вершин 2-го уровня объединяет в себе C1 = 3 подмножества, являющиеся окружениями (без вершины 0, непосредственно предшествующей этим подмножествам) трех вершин 1-го уровня:
M2 = M21 U M22 U M23 = {4, 5} U {4, 6} U {5, 6} = {4, 5, 6}, при этом C2 = 6, а |M2| = 3.
Получим:
0{1{4, 5}, 2{4, 6}, 3{5, 6}}
В общем случае, начиная со 2-го уровня, каждый последующий уровень представляет собой совокупность, а не множество вершин, так как в нее могут входить повторяющиеся элементы. Отметим, что M1 U M2 ≠ V, поэтому построение проекции необходимо продолжить следующим уровнем.
Множество M3 вершин 3-го уровня состоит из 6 подмножеств, представляющих собой окружения соответствующих им 6 вершин 2-го уровня, каждое из которых модифицировано вычитанием множеств предшествующих этому окружению вершин:
M3 = M341 U M351 U M342 U M361 U M352 U M362.
Здесь первая цифра нижнего индекса указывает на принадлежность к соответствующему уровню проекции, вторая идентифицирует вершину графа, а верхний индекс служит для дополнительной индексации нескольких экземпляров одной и той же вершины на рассматриваемом уровне проекции. Из построенной таким образом проекции
0{1{4{2, 7}, 5{3, 7}}, 2{4{1, 7}, 6{3, 7}}, 3{5{1, 7}, 6{2, 7}}}
видно, что только на 3-м уровне появляется вершина 7, не включенная в состав ни одного из подмножеств предшествующих уровней: M3= {2, 7} U {3, 7} U {1, 7} U {3, 7} U {1,7} U {2, 7} = {1, 2, 3, 7}. C3 = 12. |M3| = 4. Запись этой же проекции в однострочном варианте имеет вид
P3(0) = 0{1{4{2, 7}, 5{3, 7}}, 2{4{1, 7}, 6{3, 7}}, 3{5{1, 7}, 6{2, 7}}}.
Открывающиеся скобки перед тем или иным подмножеством вершин указывают на его вложенность, а число скобок, «непогашенных» закрывающимися, определяет уровень вложенности этого подмножества в множества вершин-предшественниц. Уровень вложенности подмножества в множество потомков ракурсной вершины (номер уровня в проекции) определяет ее удаленность от вершин соответствующего подмножества.
Проекция графа Pk(vo)считается полной, если ею определены все вершины и все ребра (отношения смежности) этого графа. Из приведенной выше проекции P3(0) видно, что и вершинное, и реберное условия полноты выполняются здесь только на 3-м уровне:
M0 U M1 U M2 U M3 = V, |M0 U M1 U M2 U M3| = |V| = 8
E0 U E1 U E2 U E3 = E, |E0 U E1 U E2 U E3| = |E| = 12
Некоторые свойства скобочного образа
Каждый уровень скобочного образа не взвешенного графа содержит совокупность концевых вершин всех исходящих из начальной вершины уникальных (не повторяющихся) простых цепей, длины которых равны номеру этого уровня.
Рассмотрим совокупность вершин k-го уровня. В указанную совокупность входят концевые вершины всех исходящих из начальной вершины простых цепей, длины которых которых равны номеру этого уровня, включая вершины, расстояние которых от начальной вершины образа равно номеру этого уровня. Сюда не могут входить вершины, расстояние которых от начальной вершины превышает номер уровня k.
Если граф является гамильтоновым, то в множестве его вершин существует такая, что число уровней максимального образа, включая нулевой, равно числу вершин графа.
И как это использовать?
В отличие от общеизвестных графического и матричного представлений, скобочный образ графа обладает повышенной информативностью, так как помимо заданной в явном виде информации о множествах вершин и ребер графа и об их смежности или инцидентности, в скобочном образе в явной или в легко извлекаемой форме представлена информация о множествах маршрутов между вершинами, об их длинах и т.п. Наличие в описании графа дополнительной информации позволяет заменить довольно трудоемкие алгоритмы, например, поиска кратчайших маршрутов, поиска непересекающихся для пары вершин маршрутов, выявления радиуса, диаметра и обхода графа, эксцентриситета его вершин и многих других типичных задач на графах достаточно простой операцией выборки искомых величин или объектов, «лежащих на поверхности» такого описания.
Существенный выигрыш в трудоемкости еще более очевиден при сравнении между собой нескольких множеств подграфов, так как предложенная форма их представления позволяет исключить многократное повторение выполненных ранее ветвей или их участков. Попытки зафиксировать в обычных алгоритмах такие участки для последующего использования в качестве промежуточных результатов приводят к неоправданному усложнению логики этих алгоритмов для особо сложных графов, что, в свою очередь, может привести к обратному эффекту: увеличению трудоемкости таких алгоритмов при непредсказуемости результатов вследствие недостаточной их «прозрачности».
Аппарат скобочных образов успешно апробирован Мелентьевым в решении некоторых классических задач теории графов, в частности, о кратчайших и непересекающихся маршрутах, об эксцентриситетах вершин, о диаметре графа и т.д.
Литература
Список трудов В.А. Мелентьева
