Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3.2. Морфология графа

Трансверсаль, матроид и двойственность графов

Снова вернемся к нашему исходному двудольному графу Г_д(V, E) и введем в оборот новое важное понятие — трансверсаль. Трансверсалью (или системой различных представителей) называется подмножество T из V, состоящее из элементов v_i по одному из каждого подмножества e_j. В нашем конкретном случае —

Г_д(V, E) = {e₁, e₂, e₃, e₄} = {{v₁, v₄, v₅}, {v₁}, {v₂, v₃, v₄}, {v₂, v₄}}

можно выделить четыре трансверсали:

T₁ = {v₁, v₂, v₃, v₄},     T₂ = {v₁, v₂, v₃, v₅},

T₃ = {v₁, v₃, v₄, v₅},     T₄ = {v₁, v₂, v₄, v₅}.

В определенном смысле нам повезло с двудольным графом Г_д. Ясно, что трансверсаль существует только в том случае, если для любых k элементов подмножеств e_j их объединение содержит, по меньшей мере, k элементов. Например, в семействе {e₁, e₂, e₃, e₄, e₅}:

{{v₁, v₂}, {v₁, v₃}, {v₂, v₃}, {v₁, v₂, v₃}, {v₁, v₃, v₄, v₅}},

невозможно найти пять различных элементов v_i по одному из каждого e_j, поэтому данное семейство не имеет трансверсалей. Здесь объединение четырех множеств содержит только три элемента:

e₁ ∪ e₂ ∪ e₃ ∪ e₄ = {v₁, v₂, v₃}.

Такие семейства, с точки зрения образования системы различных представителей, выпадают из анализа.

Трансверсали обладают одним замечательным свойством: если T и T ' — любые две трансверсали семейства E и v — элемент из T, то существует элемент v' из T ' такой, что (T – v) ∪ v' = T " — тоже трансверсаль. Например, для нашего графа Г_д(V, E), возьмем в качестве T = T₂, T ' = T₄ и v = v₃. Тогда в T₄ найдется элемент v' = v₄ такой, что (T₂ – v₃) ∪ v₄ = T₃.

Оказывается, точно таким же свойством обладают остовы графов. Покрывающие деревья исполняют роль трансверсалей потому, если T и T ' — любые два остова и e — некоторое ребро из остова T, то в остове T ' можно найти такое ребро e', которое даст новый остов: T " = (T – e) ∪ e'. Значит, можно говорить не только о вершинных трансверсалях, но и о реберных, что уже предполагает наличие некоторой двойственности.

Нужно заметить, что понятие трансверсали достаточно основополагающее для всей дискретной математики. С ним мы встречались в логике, существует оно в комбинаторике и линейной алгебре. Что касается последней области знания, указанное свойство демонстрируется следующей формулировкой: если V и V ' — два базиса одного и того же векторного пространства и v — вектор из V, то найдется базисный вектор v' из V ', что (V – v) ∪ v' = V ", где V " — новая система базисных векторов.

Трансверсаль позволяет ввести новое понятие в теорию графов — матроид. Матроидом M(T, C) графа называется система, состоящая из двух компонентов: в первую компоненту входит вся совокупность остовов T, т.е. совокупность подмножеств, в каждое из которых входит максимальное число, равное рангу k, независимых элементов; вторая совокупность C составлена из l ячеечных циклов, представляющих собой минимальные подмножества зависимых элементов. Цикломатическое число l определяется либо количеством хорд, т.е. числом ребер, не вошедших в остов, либо числом внутренних областей (ячеек) планарного графа, которые так же, как и хорды, образуют базисную систему циклов.

Матроид M может иметь двойственный к себе матроид M*, для которого ранг k* = l, а цикломатическое число l* = k. Двойственному матроиду M* отвечает двойственный граф Г*, причем i*-ребро графа Г* соответствует i-ребру графа Г, поэтому количество ребер в обоих графах одинаковое m = m*. Сказанное поясним на конкретном примере.

Рис. 3.27

Пусть дан граф Г на шести ребрах (рис. 3.27): граф Г* называется двойственным к графу Г, если векторы базисных разрезов графа Г* служат векторами базисных циклов графа Г, и наоборот. Методика построения двойственного графа показана на этом же рисунке черными кружками и пунктирными линиями. Таким образом, граф Г* имеет столько же ребер, сколько и граф Г; число вершин графа Г* равно числу областей, на которые делит плоскость своими ребрами граф Г, причем имеется соответствие: цикл {1, 2, 3} графа Г отвечает разрезу {1*, 2*, 3*} графа Г*, цикл {3, 4, 5} отвечает разрезу {3*, 4*, 5*}, разрез {6} отвечает циклу {6*}, разрез {1, 2} отвечает циклу {1*, 2*}, разрез {4, 5} отвечает циклу {4*, 5*}, наконец, разрез {2, 3, 5} отвечает циклу{2*, 3*, 5*}.

Число покрывающих деревьев исходного графа Г и двойственного Г* находится путем вычисления определителей:

D = = 8, D* = = 8.

Следовательно, в матроиде М графа Г имеется 8 трансверсалей:

T₁ = {1, 2, 4, 6}, T₂ = {1, 2, 5, 6}, T₃ = {1, 3, 4, 6}, T₄ = {1, 3, 5, 6},

T₅ = {1, 4, 5, 6}, T₆ = {2, 3, 4, 6}, T₇ = {2, 3, 5, 6}, T₈ = {2, 4, 5, 6}.

В матроид М входит два ячеечных цикла минимальной длины:

C₁ = {1, 2, 3} и C₂ = {3, 4, 5}.

Зависимость ребер в ячеечных циклах и независимость их в остовах связаны с линейной зависимостью или независимостью соответствующих столбцов матрицы инцидентности В(Г). В частности, столбцы {1, 2, 4, 6}, {1, 2, 5, 6} и т.д. независимы, а столбцы {1, 2, 3} и {3, 4, 5} зависимы. Зависимость столбцов означает, что каждый из них может быть выражен через два других:

В(Г) = ,     + = ,    + = .

Матроид М* от двойственного графа Г* образован следующими трансверсалями:

T₁* = {1, 3},  T₂* = {1, 4},  T₃* = {1, 5},  T₄* = {2, 3},

T₅* = {2, 4},  T₆* = {2, 5},  T₇* = {3, 4},  T₈* = {3, 5}.

Имеется четыре ячеечных цикла, которые охватывают соответствующие элементарные области:

C₁* = {6},   C₂* = {1, 2},   C₃* = {4, 5},   C₄* = {1, 3, 4}.

Кроме того,

k = l* = 4,     l = k* = 2,     k + l = k* + l* = 6.

Остановимся несколько подробнее на двойственности графов. При изучении групп мы узнали о пяти правильных многогранниках (первое число в круглых скобках означает количество граней, второе — число сторон каждой грани): тетраэдр (4, 3), куб (6, 4), октаэдр (8, 4), додекаэдр (12, 5), икосаэдр (20, 3). Между этими многогранниками существует двойственность: если у одного из этих многогранников соединить отрезками прямых центры граней, имеющих общее ребро, то получится другой многогранник. Двойственными друг к другу будут: куб — октаэдр, додекаэдр — икосаэдр, левый тетраэдр — правый тетраэдр (с точки зрения симметрии, вернее было бы говорить не о пяти, а о шести правильных геометрических телах). Если ребра этих многогранников спроецировать на плоскость, то геометрическая двойственность переходит в двойственность графов.

Рис. 3.28

На рис. 3.28 показана двойственность для тетраэдра, куба и октаэдра. Для произвольных многогранников (не обязательно правильных) с n вершинами, лежащими на сфере, m ребрами и f гранями выполняется равенство Эйлера: n – m + f = 2, например, для куба имеем: 8 – 12 + 6 = 2. Между точками бесконечной плоскости и точками сферы конечного радиуса существует взаимно однозначное соответствие. Поэтому планарный граф проецируется на сферу в виде выпуклого многогранника. Число граней многогранника всегда на единицу больше цикломатического числа соответствующего графа, т.е. f = l + 1, так как помимо ячеечных циклов, очерчивающих все «видимые» грани, всегда присутствует окаймляющий цикл (сумма по mod (2) всех ячеечных циклов), который очерчивает «невидимую» нам грань многогранника, представленного графом. Ранг графа на единицу меньше числа вершин, т.е. k = n – 1. Наконец, напомним известное равенство: m = k + l. Из этих трех равенств вытекает доказательство истинности тождества Эйлера:

n – m + f = n – (n – 1 + l) + (l + 1) = 2.

Теперь главный вывод. Если в многограннике провести пространственную диагональ, то в графе на плоскости появится «непланарное» ребро, равенство Эйлера нарушится, а вместе с ним и все остальные равенства, в том числе базисное: m = k + l, выполнимое для любого матроида. Поэтому на непланарном графе нельзя построить матроид.

В отношении построения двойственных графах существует некоторая неоднозначность. На рис. 3.29 изображен один и тот же граф Г, но с двумя различными укладками вершин и ребер Г₁ и Г₂. В зависимости от укладки будут получаться и различные двойственные графы — Г₁* и Г₂*. В частности, в графе Г₁* имеются вершины шестой и четвертой степени, а в графе Г₂* вместо них две вершины пятой степени. Данный факт нарушает главное свойство графов — их независимость от укладки вершин и ребер. Ранее говорилось, что граф однозначно характеризуется матрицами инцидентности, куда не заложена информация об укладке элементов графа на плоскости. Двойственный же граф, оказывается, зависит от этой несущественной детали: матрицы инцидентности для графов Г₁* и Г₂* различаются:

В(Г₁*) = ,     В(Г₂*) = .

Рис. 3.29

Однако, если мы подсчитаем число покрывающих деревьев для обоих графов Г₁* и Г₂*, то оно окажется одинаковым:

D(Г₁) = D(Г₂) = = 30,

D(Г₁*) = = 30,     D(Г₁*) = = 30.

Одинаковыми будут, по сути, и матроиды, так как остовы у них полностью совпадают:

М(Г₁) = М(Г₂),         М(Г₁*) = М(Г₂*)

T₁ = {1, 2, 5, 6, 7},     T₁* = {1*, 3*, 6*},

T₁ = {1, 2, 5, 6, 8} и т.д. T₂* = {1*, 4*, 6*} и т.д.

Внешнее различие наблюдается лишь в циклической части. Так, для М(Г₁) средняя ячеечная область выражается циклом C = {1, 2, 4, 5, 7, 8}, а для М(Г₂) средняя область выражается уже циклом C ' = {3, 4, 5, 7, 8}. Аналогичные различия могут возникнуть и в двойственных матроидах М(Г₁*) и М(Г₂*). Однако, если C₁ и C₂ являются двумя смежным ячеечными циклами и цепь ребер e_i для них общая, то результирующий цикл C₃, получившийся как объединение (C₁ ∪ C₂) – e_i = C₃, может участвовать в множестве C матроида M(T, C) вместо одного из ячеечных циклов. Путем подобных объединений мы можем заменить все ячеечные циклы на хордовые, получающиеся от хорд одного из покрывающих деревьев. Таким образом, для матроида циклическая часть C определена неоднозначно; что же касается множества остовов T, то оно строго неизменно, какова бы ни была укладка исходного графа Г, и называется базой матроида M(T, C).

Рис. 3.30

Тем не менее удобная укладка графа может сыграть принципиально важную роль в разрешении прикладных задач. Предположим, нам задан сложный орграф Г₀ (рис. 3.30) с различными весовыми характеристиками дуг, например, их длиной, и требуется найти минимальный путь между двумя заранее заданными вершинами. Ясно, что без серьезного «анатомирования» здесь не обойтись. Однако отвлечемся пока от весовых характеристик дуг и займемся чисто морфологическим анализом орграфа Г₀. Прежде, чем приступить к нему, введем в оборот новые понятия.