Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.5. Подматрицы матриц разрезов, инциденций и циклов

В этом разделе мы охарактеризуем те подматрицы матриц которые соответствуют циклам, разрезам, остовам, коостовам, и изучим свойства этих подматриц.

Теорема 6.8. 1. Между столбцами матрицы разрезов соответствующими дугам цикла, существует линейная зависимость.

2. Между столбцами цикломатической матрицы соответствующими дугам разрезающего множества, существует линейная зависимость.

Доказательство. 1. Пусть — разбиение на столбцы; — циклический вектор. Тогда, согласно соотношению ортогональности, имеем или

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

Следствие 6.8.1. Между столбцами матрицы инциденций, соответствующими дугам цикла, существует линейная зависимость.

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

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

Доказательство. Необходимость. Рассмотрим столбцов невырожденной подматрицы А. Поскольку эти столбцы линейно-независимы, то, согласно следствию 6.8.1, цикл в соответствующем подграфе графа G не присутствует. А поскольку ациклический подграф содержит дуг, то теоремы 2.2 следует, что он является остовом графа

Достаточность следует из теоремы 6.1.

Таким образом, между остовами связного графа и невырожденными подматрицами матрицы А имеется взаимно-однозначное соответствие. Этот результат является фактически основой для получения формулы, определяющей число остовов графа, которая обсуждается в разд. 6.7.

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

Доказательство. Необходимость. Пусть столбцы матрицы Q расположены таким образом, что где невырожденная подматрица. Поскольку столбцы подматрицы QH линейно-независимы, то, согласно п. 7 теоремы 6.8, в соответствующем подграфе графа G не имеется цикла. Этот подграф без циклов имеет дугу и, следовательно, по теореме 2.2 является остовом.

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

Рассмотрим теперь двойственную теорему.

Теорема 6.11. Рассмотрим связный граф О на вершинах и m дугах. Пусть В — подматрица цикломатической матрицы графа G с строкой и рангом Квадратная подматрица В порядка является невырожденной тогда и только тогда, когда ее столбцы соответствуют дугам коостова.

Доказательство. Необходимость. Пусть столбцы матрицы В расположены так, что , где — невырожденная подматрица. Поскольку ее столбцы линейно-независимы, то, согласно п. 2 теоремы 6.8, соответствующий подграф не содержит разрезов графа G. Этот подграф имеет, кроме того, дугу. Таким образом, он является максимальным (почему?) подграфом графа G, не содержащим разрезов, и, следовательно, коостовом (упражнение 2.18).

Достаточность. Пусть столбцы матрицы В расположены таким образом, что при этом столбцы подматрицы соответствуют дугам коостова графа G. Базисная цикломатическая матрица В f по отношению к этому коостову имеет вид Поскольку строки матрицы В можно выразить в виде линейной комбинации строк матрицы представим матрицу В в виде поэтому

Но D — невырожденная матрица, так как матрицы В и имеют максимальный ранг Следовательно, невырожденная подматрица.

Для иллюстрации теорем 6.10 и 6.11 рассмотрим граф G на рис. 6.1, а, а также матрицы [выражения (6.9) и (6.11) соответственно]. Квадратными подматрицами порядка матрицы соответствующей остову порядка матрицы соответствующей коостову являются матрицы

Легко видеть, что определители этих матриц не равны нулю, следовательно, матрицы — невырожденные.

Завершая раздел, рассмотрим интересное свойство обращения невырожденной подматрицы усеченной матрицы инциденций.

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

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

остов Т графа G. Базисная матрица разрезающих множеств по отношению к остову Т будет представляться в виде

По теореме 6.3 всякий вектор разреза можно выразить в виде линейной комбинации строк матрицы инциденций. Поэтому множество можно представить в виде Следовательно,

Рассмотрим теперь строку матрицы . Пусть ей соответствует разрез при этом

Допустим, что разрез ориентирован от к Тогда из выражения (6.5) следует, что

где строка матрицы инциденций

Заметим, что соответствующая строка отсутствует в матрице А. Поэтому если , то для представления линейной комбинацией строк матрицы А мы должны записать в виде (6.18). Если то мы должны записать в виде (6.17). В обоих случаях все ненулевые коэффициенты равны 1 либо —1.

Таким образом, все ненулевые элементы в любой строке матрицы равны 1 или —1.

В доказательстве этой теоремы, по существу, предлагается следующая простая процедура нахождения

1. Построить дерево Т, для которого — матрица инциденций, усеченная по строке, соответствующей

2. Пометить дуги дерева таким образом, чтобы столбцу матрицы соответствовала Аналогично пометить вершины дерева так, чтобы строке матрицы соответствовала

3. Пусть столбец матрицы соответствует Для каждого удалим из дерева Т, получая компоненты ставшего несвязным графа. Пусть — множество вершин дерева — множество вершин дерева ориентирована от вершины из множества к вершине из множества . Если то приравнять —1 все элементы строки матрицы соответствующие вершинам множества а остальные элементы — нулю. Если то приравнять 1 все элементы строки, соответствующие вершинам множества а остальные элементы — нулю. Рассмотрим в качестве иллюстрации матрицу

Дерево Т, для которого является усеченной матрицей инциденций, представлено на рис. 6.6, а. Матрица усечена по строке, соответствующей вершине

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

Рис. 6.6. а — дерево Т; б — поддеревья .

Поскольку вершина, соответствующая усеченной строке, находится во множестве первая строка будет иметь значение —1 в элементах, соответствующих вершинам находящимся во множестве т. е. будет иметь вид

Аналогичным образом получаем остальные строки матрицы . В результате получится следующая матрица:

<< Предыдущий параграф Следующий параграф >>
Оглавление