5.6. Матрица путей

Для связного графа, вершины которого перенумерованы, можно построить матрицу путей (или цепей) следующим образом: строки матрицы должны соответствовать путям из первой вершины в последнюю, а столбцы — ребрам графа. Следовательно, элемент матрицы принимает значение 1 или в зависимости от того, принадлежит ли данное ребро данному пути или нет. Например, граф, изображенный на рис. 5.8, имеет следующую матрицу путей между вершинами

Теорема 5.10. Произведение матрицы инцидеиций на транспонированную матрицу путей дает в результате матрицу, все строки которой, исключая первую и последнюю, содержат нули, а первая и последняя — единицы.

Рис. 5.8.

Доказательство. Элемент матрицы принимает значение 1 тогда и только тогда, когда некоторое ребро одновременно принадлежит данному пути и инцидентно первой или последней вершине. В

каждой цепи между двумя вершинами существует только одно такое ребро. Вершины любого пути, не являющиеся конечными, имеют степени или 2, и следовательно, все остальные элементы матрицы равны нулю по модулю 2 [21].

Замечание. Ранг матрицы путей графа с вершинами и ребрами равен где с — число независимых циклов в таких разделимых подграфах между конечными вершинами, удаление которых из графа не удаляет ни одной из конечных вершин. Из теоремы 5.10 следует, что ранг не превосходит Заметим также, что хорды деревьев в подграфах, описанных выше, не принадлежат ни одному пути.