Диссертация (1145311), страница 20
Текст из файла (страница 20)
Эта проблема важна, поскольку некоторые практические задачи теории графов для реберных графов решаются значительнопроще [78]. Имеется несколько различных алгоритмов распознавания реберного графа [78, 124, 127, 155], причем алгоритм, предложенный в статье [127]разработан совсем недавно. В статье [127] приводится обзор существующих алгоритмов.
Так, алгоритм Roussopoulos основан на следующей теореме: графявляется реберным тогда и только тогда, когда можно разбить его на кликитак, чтобы каждая вершина принадлежала не более чем двум кликам и любыедве клики имели не более одной общей вершины. Алгоритм Lehot используетследующий принцип: граф является реберным тогда и только тогда, когда онне содержит полного двудольного графа K1,3 в качестве порожденного подграфа, и если любые два нечетных треугольника∗ имеют общее ребро, то подграф,порожденный их вершинами, является полным графом K4 . Динамический алгоритм, представленный в [78], основан на модификации конструктивного доказательства Оре теоремы Уитни о том, что если два связных графа на четырехи более вершинах реберно изоморфны, то существует ровно один вершинныйизоморфизм, который порождает данный реберный изоморфизм. Данный алгоритм позволяет за линейное время проверить, сохраняет ли добавление илиудаление врешины или ребра свойство реберности или нет.
Представленный вдиссертации алгоритм использует разбиение графа на клики аналогично алгоритму Roussopoulos. Он, как и алгоритм Degiorgi и Simon, позволяет во многихслучаях не перестраивать всю матрицу корневого графа при добавлении илиудалении вершин или ребер рассматриваемого графа. Это может сократить время работы алгоритма, особенно для разреженных матриц.В диссертации представлен линейно алгебраический подход к решению∗Треугольник нечетный, если любая вершина графа смежна с одной или тремя вершинами этоготреугольника.150данной задачи. Предлагается достаточно простой алгоритм ее решения, который легко программируется. Используются только матрицы, связанные с данным графом.3.1. Линейные пространства над полем GF(2)Линейная алгебра изучает среди прочего общие свойства векторных пространств над произвольными полями. Необходимость отдельного изучения векторных пространств над полем Галуа характеристики два продиктована широким использованием этих пространств в теории обыкновенных графов [32, 34,80], теории кодирования [72, 160], математической логике [11] и других областяхзнания [22, 75].
Приведем здесь результаты, представленные в работе [18].Поскольку мы собираемся ограничиться n-мерными (n конечно и произвольно) пространствами над полем вычетов по модулю два, то можем рассматривать только одно изоморфное им всем n-мерное координатное пространство,т. е. пространство упорядоченных наборов из n элементов (координат), каждыйиз которых может принимать только два значения: 0 или 1.Так как упорядоченные наборы из одного и того же числа элементов легчевсего представлять себе в виде строк или столбцов, то в дальнейшем будем называть такие наборы столбцами или строками.
А поскольку элементами столбцов (строк) будут только 0 или 1, то будем называть их (0, 1)-столбцами или(0, 1)-строками. Мы будем чаще употреблять в качестве названия такого упорядоченного набора обозначение (0, 1)-столбец (координатный столбец). Полевычетов по модулю два будем, как принято, обозначать через GF (2), а элементы поля GF (2) 0 или 1 называть числами.Очевидно, что множество (0, 1)-столбцов из n элементов (что будем подразумевать в дальнейшем, не оговаривая специально) относительно операциисложения столбцов и умножения столбцов на числа из GF (2) (частный случай сложения матриц и умножения матриц на числа) образует векторное про-151странство.
Будем обозначать его через V . Очевидно также, что размерностьэтого пространства равна n. Столбцы n-мерного пространства будем иногданазывать n-столбцами. Базисом пространства n-столбцов, если не оговоренопротивное, будем считать столбцы единичной матрицы порядка n. Отметим,что элементы любого векторного пространства называются векторами. Потомудля (0, 1)-столбцов часто будем использовать также термин “вектор”, подчеркивая тем самым, что мы рассматриваем (0, 1)-столбец как элемент векторногопространства.Пусть A1 , A2 , . . . , Am ∈ V , тогдаmXxi Ai , где xi ∈ GF (2), как это при-i=1нято, будем называть линейной комбинацией системы (совокупности) вектоmkXXров ((0, 1)-столбцов) A1 , A2 , . . .
, Am . Ясно, чтоx i Ai =Aij , где ij ∈i=1j=1{1, 2, . . . , m}, 0 ≤ k ≤ m, xi1 = . . . = xik = 1, а остальные xi = 0. То естьлинейной комбинацией системы векторов A1 , A2 , . . . , Am является сумма векторов некоторой подсистемы этой системы либо нулевой вектор.Линейная независимость и линейная зависимость системы векторов (столбцов) определяются обычным образом.В дальнейшем нам понадобятся определения четных (нечетных) столбцов(строк).Определение 20. (0, 1)-столбец называется четным, если число единиц внем четное, или нечетным, если оно нечетное.Аналогичное определение дается для строк.Замечание 26. Число единиц в (0, 1)-векторе в теории кодирования называется весом Хэмминга этого вектора.Теорема 53.
Система (0, 1)-столбцов A1 , A2 , . . . , Am будет линейно зависимой над полем GF (2) тогда и только тогда, когда существует такая подсистема исходной системы, что у матрицы, построенной из столбцов этойподсистемы, все строки будут четные.152Отметим, что упомянутая подсистема может состоять как из одного нулевого столбца, если таковой принадлежит исходной системе, так и совпадать сисходной системой.Доказательство.
Необходимость. Пусть система (0, 1)-столбцов A1 , A2 ,mX. . ., Am линейно зависима. Это значит, чтоxi Ai = 0, когда не все коэффициенты xi линейной комбинацииmXi=1xi Ai равны нулю, т. е. существует непустаяi=1подсистема Ai1 , Ai2 , . . . , Aik (0 ≤ k ≤ m) системы A1 , A2 , . . .
, Am такая, чтоkXAij = 0. Последнее, очевидно, возможно тогда и только тогда, когда строкиj=1матрицы (Ai1 , Ai2 , . . . , Aik ) четные. Необходимость доказана.Достаточность. Пусть система (0, 1)-столбцов A1 , A2 , . . . , Am содержит некоторую подсистему Ai1 , Ai2 , . . . , Aik , где 0 ≤ k ≤ m, такую, что все строки матриkXцы (Ai1 , Ai2 , . . . , Aik ) четные. Но тогдаAij = 0, и это значит, что подсистемаj=1Ai1 , Ai2 , . . . , Aik линейно зависима. Но тогда линейно зависима и содержащая еесистема A1 , A2 , .
. . , Am . Достаточность и теорема в целом доказаны.Теорема 54. Система (0, 1)-столбцов A1 , A2 , . . . , Am будет линейно независимой тогда и только тогда, когда матрица любой подсистемы столбцов будет иметь ненулевое количество нечетных строк.Доказательство как необходимости, так и достаточности проводится методом от противного.Отметим еще одну особенность пространства (0, 1)-столбцов над полем вычетов по модулю два.
Пусть система ненулевых (0, 1)-столбцов A1 , A2 , . . . , AmmXтакова, чтоAi = 0. Будем называть такую систему 1-зависимой (все коi=1эффициенты линейной зависимости равны 1). В дальнейшем термин 1-зависимости будем применять только к системе ненулевых векторов. Очевидно, что153все строки матрицы, построенной из столбцов 1-зависимой совокупности, будутчетными.
Если 1-зависимая система содержит 1-зависимую подсистему, то подсистема, дополняющая упомянутую 1-зависимую подсистему до исходной системы, будет также 1-зависимой. Таким образом, 1-зависимая система различных(0, 1)-столбцов разбивается на непересекающиеся подмножества 1-зависимыхподсистем.Пусть теперь 1-зависимая система (0, 1)-столбцов A1 , A2 , . . . , Am не содержит 1-зависимой подсистемы, отличной от самой системы. Такую систему будемназывать минимальной 1-зависимой системой (0,1)-столбцов. Очевидно, чтоминимальная 1-зависимая система различных n-столбцов состоит более чем издвух столбцов, и удаление любого столбца из минимальной 1-зависимой системы будет превращать ее в линейно независимую.Приведенные выше рассуждения можно суммировать в виде следующейтеоремы.Теорема 55.
1-зависимаясистемаразличных(0, 1)-столбцовA1 , A2 , . . . , Am m > 2 либо является минимальной 1-зависимой системой, либо разбивается на непересекающиеся минимальные 1-зависимые подсистемы.Определения линейной комбинации, линейной зависимости и линейной независимости векторов позволяют вести речь о системе образующих и максимальной линейно независимой подсистеме данной системы векторов.
Базис системы векторов A1 , A2 , . . . , Am , как и в общем случае, может записываться тремяразличными способами: как минимальная система образующих, максимальнаялинейно независимая подсистема и линейно независимая система образующихсистемы векторов A1 , A2 , . . . , Am . Базис системы векторов как подсистема векторов исходной системы находится неединственным образом.
Все базисные совокупности векторов состоят из одного и того же числа векторов (число векторов базиса называют размерностью векторного пространства), и любой вектор154системы единственным образом представи́м в виде линейной комбинации векторов базисной совокупности.Вернемся вновь к пространству (0, 1)-столбцов над GF (2). Возможностьстроить матрицы из столбцов одинаковой размерности (длины) позволяет перейти к матричным записям и матричным формулировкам линейной комбинации, линейной независимости и линейной зависимости системы векторов.Рассмотрим линейную комбинацию системы векторов ((0, 1)-столбцов) A1 ,mXA2 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
