Диссертация (1145311), страница 23

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 23)

Степень вершины vi — это количество ребер, инцидентных этойвершине.Матрица смежности простого графа G — это матрица, номера строк истолбцов которой соответствуют номерам вершин помеченного графа G, с элементами 1 или 0 на месте (vi , vj ) соответственно, если вершины vi и vj являютсясмежными или не смежными. В нашем случае (граф является простым и неориентированным) матрица смежности является симметричной, и на ее главнойдиагонали стоят нули.Вершинно-реберная матрица инцидентности графа — это матрица B =(bij ) размерности m × n, где m м n — количества вершин и ребер соответственно, такая, что bij = 1, если i-я вершина и j-е ребро инцидентны, и bij = 0 впротивном случае.Определение 24.

Полным графом, или кликой, называется граф, в которомлюбые две различные вершины соединены единственным ребром.Определение 25. Путем в графе G называется последовательность различных вершин графа v1 , v2 , . . . , v` такая, что {v1 , v2 }, {v2 , v3 }, . . ., {v`−1 , v` } являются ребрами графа G.

Граф называется связным, если существует путь,соединяющий любые две его вершины. В дальнейшем мы будем рассматриватьтолько связные графы. Если P — путь, соединяющий вершины v1 , v2 , . . . , v` ,и мы добавим ребро {v` , v1 }, то полученный подграф исходного графа мы будем называть циклом. Множество всех циклов графа G является линейнымпространством над полем GF (2).

Оно называется пространством циклов графа G.Определение 26. Разрезом называется разбиение вершин графа на два непересекающихся множества. Любой разрез определяет секущее множество, т.166е. множество ребер графа, концы которых принадлежат разным подмножествам разбиения. Объединение всех секущих множеств графа G являетсялинейным пространством над полем GF (2).

Оно называется пространствомразрезов графа G.Пусть даны два графа G1 = (V1 , E1 ) и G2 = (V2 , E2 ). Симметричнойразностью этих графов называется граф G = G1 ⊕ G2 = (V1 ∪ V2 , (E1 ∪ E2 ) \(E1 ∩ E2 )), причем изолированные вершины отбрасываются. Таким образом,ребро принадлежит G1 ⊕ G2 тогда и только тогда, когда оно является ребромграфа G1 или ребром графа G2 , но не ребром обоих графов.Пример 9. Для графа G, представленного на рис. 3.1, имеемV = {1, 2, 3, 4, 5, 6, 7}, E = {I,II,III,IV,V,VI,VI,VIII,IX,X,XI},Его матрица смежности A и матрица инцидентности1 0 0 1 1 0 1 00 1 1 1 1 0 01 1 1 0 0 0 0 01 0 1 1 0 0 00 1 0 1 0 1 0 01 1 0 1 0 0 1A =  1 1 1 0 0 1 0 ,B =  0 0 1 0 1 1 0 10 0 0 0 0 0 1 01 0 0 0 0 1 00 0 0 1 1 0 10 0 0 0 0 0 0 10 0 0 0 0 0 0 00 0 1 0 0 1 0B имеют вид:0 0 00 0 01 0 00 0 0 .0 1 00 1 11 0 1167Рис.

3.1. Граф G, циклы, разрезы.Иатрица смежности реберного графа L(G)0 1 1 1 1 0 1 01 0 1 1 0 1 0 01 1 0 0 1 1 0 11 1 0 0 1 1 1 01 0 1 1 0 1 1 1AL(G) = 0 1 1 1 1 0 0 11 0 0 1 1 0 0 00 0 1 0 1 1 0 00 1 0 1 0 1 0 00 0 0 0 0 0 1 1имеет вид0 0 01 0 00 0 01 0 00 0 01 0 0.0 1 00 1 10 0 10 0 10 0 0 0 0 0 0 1 1 1 0Реберный граф L(G) представлен на рис. 3.2.Одна из клик графа G — клика, содержащая вершины {1, 2, 3, 4}.

Одиниз циклов графа — это цикл, содержащий ребра {I,II,IX,XI,X,VII}. Например,один из разрезов — это разрез {VII,VIII,IX}. Для этого разреза два непересе-168Рис. 3.2. Реберный граф L(G).кающихся множества вершин следующие V1 = {1, 2, 3, 4} и V2 = {5, 6, 7}.Следующая теорема известна в теории графов [69, 168, 178].Теорема 58. Любой граф G может быть представлен в виде кольцевой суммы двух подграфов, один из которых принадлежит подпространству циклов,а второй — подпространству разрезов G.Далее мы докажем этот результат, рассматривая линейное пространствонад полем GF (2) и его ортогональное дополнение.Рассмотрим линейно независимые векторы X1 , X2 , .

. . , Xm ∈ Gn . Обозначим через L линейную оболочку этих векторов. Пусть векторы Y1 , Y2 , . . . , Yn−mобразуют базис ортогонального дополнения L⊥ . Обозначим через J вектор(1, 1, . . . , 1)T . Докажем следующую теорему [95].Теорема 59. Вектор J является линейной комбинацией векторов X1 , . .

. , Xm ,Y1 , . . ., Yn−m .169Доказательство. Для любого вектора Z ∈ L ∩ L⊥ имеем (Z, Z) = 0.Следовательно, все такие векторы Z четные. Таким образом, (Z, J) = 0 и J ∈(L ∩ L⊥ )⊥ .Предположим, что dim(L ∩ L⊥ ) = k. Тогда dim(L ∩ L⊥ )⊥ = n − k. Крометого,dim(L + L⊥ ) = dim L + dim L⊥ − dim(L ∩ L⊥ ) = n − k.Путь произвольный вектор V ∈ L + L⊥ , тогда V = X + Y , где X ∈ L, Y ∈L⊥ . Вектор X ортогонален любому вектору из L⊥ . Таким образом, X ортогонален любому вектору из L ∩ L⊥ . Следовательно, X ∈ (L ∩ L⊥ )⊥ .

АналогичноY ∈ (L ∩ L⊥ )⊥ . Это доказывает, что V ∈ (L ∩ L⊥ )⊥ . Отсюда L + L⊥ ⊆ (L ∩ L⊥ )⊥ .Так какdim(L ∩ L⊥ )⊥ = dim(L + L⊥ ),то L + L⊥ = (L ∩ L⊥ )⊥ .В действительности доказано больше. Любой вектор из линейного пространства (L ∩ L⊥ )⊥ является линейной комбинацией векторов X1 , . . . , Xm , Y1 ,. . ., Yn−m .Доказательство теоремы 58 в статьях [69, 178] гораздо более сложное идлинное, чем доказательство, основанное на теории линейных пространств надполем GF (2), которое представлено здесь.3.1.2.

Факторизация матрицы над полем GF (2)Заметим, что мы рассматриваем специальное разложение матрицы, отличное от наиболее часто используемых, таких как LU-разложение, разложениеХолецкого, QR-разложение и др.Определение 27. Будемговорить,чтосимметричная(0, 1)-матрица A порядка n факторизуема, если существует матрица B такая, что A = BB T .170Задача нахождения такой матрицы B, т. е. задача факторизации матрицы, эквивалентна нахождению системы векторов X1 , X2 , .

. ., Xm ∈ Gn таких,что A = G(X1 , X2 , . . ., Xm ). Задача факторизации матрицы решалась в работах [46, 102, 125, 130], где полученное решение было также обобщено на случайразличных конечных полей (см. также [145]). Было также предложено несколько различных алгоритмов для построения матрицы B с наименьшим числомстолбцов (минимальная факторизация).Здесь мы предлагаем новый подход к задаче матричной факторизации.Сначала рассмотрим факторизацию симметричной (0, 1)-матрицы A без учетачисла столбцов в матрице B. В этом случае можно использовать связь междусимметричными матрицами и обыкновенными графами.Теорема 60.

Любая симметричная (0, 1)-матрица факторизуема над полемGF (2).Замечание 31. Другимисловами,любаясимметричная(0, 1)-матрица является матрицей Грама, построенной для некоторого набора (0, 1)-векторов.Доказательство. Пусть A = [aij ] — симметричная матрица n-го порядканад полем GF (2). Рассмотрим симметричную матрицу Ã = [ãij ] порядка n сэлементамиa ,ijãij = 0,если i 6= j,если i = j,Матрицу Ã можно считать матрицей смежности обыкновенного графа G. Построим для этого графа матрицу инцидентности B (нумерация ребер графа Gпри этом может быть произвольной). Так как BB T = A + S, где S — диагональная матрица порядка n (sii равно 1, если степень i-й вершины нечетна, и0 в противном случае), то BB T — (0, 1)-матрица, отличающаяся от матрицы Aтолько элементами, стоящими по главной диагонали.171Если ajj 6= ãjj (j = 1, 2, .

. . , n), добавим еще один столбец к матрице B.Этот столбец имеет единственный ненулевой элемент, равный 1, который стоитв j-й строке. За конечное число шагов мы получим матрицу B̃, которая удовлетворяет требуемому равенству A = B̃ B̃ T .Рассмотрим теперь случай, когда количество столбцов в матрице B является существенным. В теореме 61 приводится вспомогательный результат относительно конгруэнтности матриц над полем GF (2), а теорема 62 позволяетнайти минимальную факторизацию матрицы простым и прямым способом.Для вычисления ранга матрицы A воспользуемся методом Гаусса, в котором за каждой элементарной операцией над строками матрицы следует аналогичная операция над ее стобцами.Замечание 32. Элементарные операции над полем GF (2) определяются, иметод Гаусса применяется точно так же, как и обычно, над полем вещественных чисел.Если элементарная операция выполняется над i-й и j-й строками, то аналогичная операция должна быть выполнена над i-м и j-м столбцами.

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

Характеристики

Список файлов диссертации