6.6. Унимодулярные матрицы

Матрица называется унимодулярной, если определитель любой ее квадратной подматрицы равен 1, —1 или 0. В этом разделе мы покажем, что матрицы унимодулярны.

Теорема 6.13. Матрица инциденций ориентированного графа унимодулярна.

Доказательство. Докажем теорему индукцией по порядку квадратной подматрицы

Очевидно, что определитель любой квадратной подматрицы порядка равен 1, —1 или 0. В качестве индуктивного предположения примем, что определитель любой квадратной подматрицы порядка менее k равен 1, —1 или 0.

Рассмотрим произвольную невырожденную квадратную подматрицу порядка k. Каждый ее столбец содержит не более двух ненулевых элементов (+1 и —1). Поскольку подматрица невырожденная, то не во всяком столбце имеются значения По этой же причине подматрица не имеет столбцов, состоящих только из нулевых элементов. Таким образом, существует столбец, содержащий точно один ненулевой элемент. Разлагая определитель подматрицы по этому столбцу и учитывая индуктивное предположение, получаем, что искомый определитель равен ±1.

Пусть — базисная матрица разрезов связного графа G на вершинах по отношению к некоторому остову Т, ветвями которого являются

Рис. 6.7.

Пусть G — граф, полученный из графа G отождествлением или замыканием концевых вершин одной из ветвей, например ветви . Тогда — остов G. Удалим теперь из матрицы Q строку, соответствующую ветви и получившуюся матрицу обозначим через Нетрудно показать, что — базисная матрица разрезающих множеств G по отношению к остову Таким образом, матрица, получившаяся в результате удаления из матрицы Q произвольной строки, является базисной матрицей разрезающих множеств некоторого связного графа. Обобщая этот результат, можно сделать вывод, что всякая матрица, образованная строками матрицы является базисной матрицей разрезающих множеств некоторого связного графа.

Рассмотрим, например, граф G на рис. 6.1, а. Базисная матрица разрезающих множеств представлена в (6.9). Подматрица, состоящая из двух строк матрицы которые соответствуют ветвям и имеет вид

Легко проверить, что эта матрица — базисная матрица разрезающих множеств графа, представленного на рис. 6.7, по отношению

к остову Этот граф получен из графа на рис. 6.1, а отождествлением концевых вершин

Теорема 6.14. Любая базисная матрица разрезающих множеств связного графа G унимодулярна.

Доказательство. Пусть — базисная матрица разрезающих множеств графа G по отношению к остову Т. Тогда Представим усеченную матрицу инциденций А графа в виде где столбцы соответствуют ветвям остова Т. Из теоремы 6.9 мы знаем, что — невырожденная подматрица. Запишем теперь матрицу в виде

Если С — произвольная квадратная подматрица матрицы порядка где — число вершин графа соответствующая подматрица матрицы А, тогда Поскольку или ±1, получаем

Рассмотрим произвольную квадратную подматрицу Н матрицы порядка менее чем Из предшествующих теореме рассуждений следует, что Н — подматрица базисной матрицы разрезающих множеств некоторого связного графа. Поэтому или 0, что доказывается так же, как и (6.19).

Таким образом, определитель всякой квадратной подматрицы матрицы Q равен ±1 или 0 и, следовательно, матрица — унимодулярна.

Покажем сейчас, что матрица также унимодулярна.

Теорема 6.15. Любая базисная цикломатическая матрица связного графа G унимодулярна.

Доказательство. Пусть и -базисные цикломатическая матрица и матрица разрезающих множеств графа G по отношению к остову Т. Если из (6-13) следует Так как матрица унимодулярна, то унимодулярна также и матрица Элементарным упражнением теперь остается показать, что и матрица унимодулярна.