Здравствуйте, Посетитель - 375268!

Вначале вспомним теорию.

Пусть у нас имеется простой связный граф G = <X, E>, заданный множеством вершин X = {x[sub]1[/sub],..., x[sub]n[/sub]} и множеством рёбер E = {e[sub]1[/sub],..., e[sub]m[/sub]}.

Циклом будет последовательность рёбер, такая что концевая вершина каждого ребра является начальной вершиной следующего, а конец последнего ребра совпадает с началом первого. Множество всех циклов графа записывается с помощью матрицы циклов С = (с[sub]ik[/sub]), строки которой соответствуют циклам C[sub]i[/sub], а столбцы - рёбрам e[sub]k[/sub]. При этом c[sub]ik[/sub] = 1, если e[sub]k[/sub][$8712$]C[sub]i[/sub] и c[sub]ik[/sub] = 0, если e[sub]k[/sub][$8713$]C[sub]i[/sub]. Для ориентированного графа выбирается также направление обхода цикла и при e[sub]k[/sub][$8712$]C[sub]i[/sub] принимается c[sub]ik[/sub] = -1 для e[sub]k[/sub][$8593$][$8595$]C[sub]i[/sub] и c[sub]ik[/sub] = 1 для e[sub]k[/sub][$8593$][$8593$]C[sub]i[/sub].

Разрезающим множеством будет минимальное множество ребер, при удалении которых из графа G он перестанет быть связным и распадётся на два подграфа G[sub]1[/sub] и G[sub]2[/sub] (минимальное означает, что любое его подмножество разрезающим уже не будет). Все разрезающие множества графа также можно записать с помощью матрицы S = (s[sub]jk[/sub]), строки которой соответствуют разрезающим множествам S[sub]j[/sub], а столбцы - рёбрам e[sub]k[/sub]. При этом s[sub]jk[/sub] = 1, если e[sub]k[/sub][$8712$]S[sub]j[/sub] и s[sub]jk[/sub] = 0, если e[sub]k[/sub][$8713$]S[sub]j[/sub]. Для ориентированного графа выбирается также направление разреза и при e[sub]k[/sub][$8712$]S[sub]j[/sub] принимается s[sub]jk[/sub] = -1 для e[sub]k[/sub][$8593$][$8595$]S[sub]j[/sub] и s[sub]jk[/sub] = 1 для e[sub]k[/sub][$8593$][$8593$]S[sub]j[/sub].

Граф T = <X, E'>, E'[$8712$]E (то есть содержащий все вершины графа G, но только часть его рёбер), являющийся деревом (то есть связный и не содержащий циклов), называется остовом графа G. Для ориентированного графа остов является ориентированным деревом, то есть помимо связности и отсутствия циклов выполняется условие: в каждую вершину входит ровно одна дуга (ребро), за исключением единственной вершины - корня дерева. Остальные рёбра (не входящие в остов) образуют коостов (кодерево) T[sup]*[/sup]. Рёбра остова (из множества E') называют ветвями, а рёбра коостова (из множества E\E') - хордами. Любой связный (и только связный) граф имеет остов, причём число ветвей в нём равно n-1 (соответственно, число хорд в коостове равно m-n+1).

Так как остов T является деревом, то при добавлении к нему любой хорды из коостова T[sup]*[/sup] в нём образуется ровно один цикл, называемый базисным циклом графа. Множество всех таких циклов называется базисным множеством циклов графа G относительно остова T (оно, очевидно, содержит m-n+1 базисный цикл - по числу хорд в коостове). Матрица базисных циклов C[sub]f[/sub] будет иметь размерность (m-n+1) x m. В каждой её строке ненулевыми будут: элемент в столбце, соответствующем одной из хорд коостова (своей для каждой строки), и элементы в столбцах, соответствующих ветвям остова, которые образуют цикл вместе с данной хордой. Остальные элементы будут равны нулю. Знак ненулевых элементов для ориентированного графа определяется совпадением или несовпадением направления соответствующего ребра с направлением цикла.

Так как остов T является деревом, то при удалении из него любой ветви он распадётся на два несвязных подостова T[sub]1[/sub] и T[sub]2[/sub]. Добавляя все хорды коостова, вершины которых лежат в разных подостовах, получаем разрезающее множество, делящее граф G на два несвязных подграфа G[sub]1[/sub] и G[sub]2[/sub] (остовами которых и являются T[sub]1[/sub] и T[sub]2[/sub]). Оно называется базисным разрезающим множеством графа G относительно остова T (всего будет n-1 базисное разрезающее множество - по числу ветвей остова). Матрица базисного разрезающего множества S[sub]f[/sub] будет иметь размерность (n-1) x m. В каждой её строке ненулевыми будут: элемент в столбце, соответствующем одной из ветвей остова (своей для каждой строки), и элементы в столбцах, соответствующих хордам коостова, которые образуют разрезающее множество вместе с данной ветвью. Остальные элементы будут равны нулю. Знак ненулевых элементов для ориентированного графа определяется совпадением или несовпадением направления соответствующего ребра с направлением разреза.

Как правило, в графе можно выбрать несколько разных остовов. В данном случае имеем ориентированный граф, содержащий 6 вершин и 9 рёбер. Следовательно, остов будет содержать 5 (6-1) рёбер, граф будет иметь 4 (9-6+1) базисных цикла и 5 (6-1) базисных разрезающих множества.

Для данного графа остовами будут следующие деревья: x[sub]1[/sub]x[sub]6[/sub]x[sub]2[/sub]x[sub]3[/sub]x[sub]4[/sub]x[sub]5[/sub] и x[sub]3[/sub]x[sub]4[/sub]x[sub]5[/sub]x[sub]6[/sub]x[sub]2[/sub]x[sub]1[/sub]. Выберем второе из них, тогда множество ветвей остова будет E' = {2,3,4,8,9}, а множество хорд коостова - E\E' = {1,5,6,7}. Построим искомые матрицы.

Для построения матрицы базисных циклов будем по очереди добавлять к множеству ветвей остова одну из хорд и отмечать получившийся цикл (в качестве направления обхода циклов примем направление по часовой стрелке). При добавлении хорд 1, 5, 6 и 7 будут получаться циклы {1,3,2}, {5,3,4}, {6,3,4,8} и {7,3,4,8,9} соответственно. Заполним соответствующие элементы матрицы единицами:

Так как граф ориентированный, то нужно учесть направление обхода циклов. Для первого цикла все рёбра направлены против направления обхода, для второго и четвёртого - по направлению, для третьего - все по направлению, кроме ребра 6. Соответственно, матрица будет иметь вид:


Для построения матрицы базисного разрезающего множества будем по очереди убирать из остова каждую из ветвей и отмечать, какие рёбра образуют разрезающее множество для двух получившихся подграфов (за направление разреза примем направление от подграфа, содержащего корень остова - вершину x[sub]3[/sub]). Например, при удалении ветви 2 получаем подграфы x[sub]3[/sub]x[sub]4[/sub]x[sub]5[/sub]x[sub]6[/sub]x[sub]2[/sub] и x[sub]1[/sub], связанные рёбрами {1,2}, причём первое из них идёт против направления разреза, а второе - по направлению. При удалении ветви 3 получаем подграфы x[sub]3[/sub]x[sub]4[/sub]x[sub]5[/sub]x[sub]6[/sub] и x[sub]2[/sub]x[sub]1[/sub], связанные рёбрами {1,3,5,6,7}, среди которых рёбра 3 и 6 имеют положительное направление, а остальные - отрицательное. Продолжая аналогично, получаем матрицу:

Для проверки можно воспользоваться тем свойством, что C[sub]f[/sub]·S[sub]f[/sub][sup]T[/sup] = S[sub]f[/sub]·C[sub]f[/sub][sup]T[/sup] = 0.