Упражнения

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

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

6.3. Пусть Q — матрица, образованная независимыми строками матрицы разрезов связного ориентированного графа G, имеющего дуг. Покажите, что если F — произвольная матрица порядка и ранга имеющая элементы, равные 1, —1 и 0, и удовлетворяющая условию то каждая строка матрицы F соответствует циклу или объединению реберно-непересекающихся циклов

6.4. Пусть — подматрица матрицы разрезов связного неразделимого ориентированного графа G; каждая содержит только те строки которые соответствуют разрезам, разделяющим вершины х и у. Покажите, что содержит базисную матрицу разрезающих множеств графа G. (Более общий результат приведен в работе )

6.5. Пусть В — подматрица цикломатической матрицы планарного графа G, содержащая только те строки которые соответствуют ячейкам графа G. Покажите, что подматрица В унимодулярна. (Определение планарного графа и ячеек дано в гл. 7.)

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

6.7. Докажите теорему 4.11.

6.8. Докажите, что для связного ориентированного графа где — базисная цикломатическая матрица, a Q, — базисная матрица разрезающих множеств графа

6.9. Пусть Q — матрица, образованная любыми независимыми строками матрицы разрезов связного ориентированного графа G, матрица, образованная любыми р, (G) независимыми строками цикломатической матрицы G. Покажите, что матрица — невырожденная.

6.10. Докажите, что подпространства над полем GF (2) циклов и разрезов IFS связного неориентированного графа G являются ортогональными дополнениями векторного пространства тогда и только тогда, когда число остовов графа G нечетно.

6.11. Пусть для любого ребра е графа G произведение обозначает граф, полученный из графа G стягиванием ребра е. Покажите, что если граф G связный, то

6.12. Используя рекурсивную формулу из упражнения 6.11, найдите число остовов колеса на вершинах. (Определение колеса см. в разд. 8.4.)

6.13. Покажите, что если — ребро графа то

6.14. а) Пусть Н — граф на вершинах, в котором между всякой парой смежных вершин имеется k параллельных дуг. Пусть G— простой граф, лежащий в основе графа Н. Покажите, что

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

6.15. Покажите, что теорема 6.17 является частным случаем теоремы 6.24.

6.16. Граф G с весами на дугах называется взвешенным графом. Напомним, что весовое произведение подграфа графа G равно произведению весов его дуг и что если подграф имеет единственную изолированную вершину, то его весовое произведение по определению равно 1.

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

6.17. Матрица полустепеней исхода ориентированного графа G без петель определяется следующим образом:

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

6.18. Матрица полустепеней исхода взвешенного ориентированного графа без петель определяется следующим образом:

а) (Сумма весов дуг, направленных от вершины ), если .

б) (Сумма весов дуг, исходящих из вершины ). Докажите, что равен сумме весовых произведений всех входящих остовных деревьев графа О с корневой вершиной Примечание. Под корнем здесь понимается такая

вершина что из каждой другой вершины существует ориентированный путь в нее.

6.19. Решите систему уравнений:

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

6.21. Используя метод, предложенный в упражнении 6.20, приведите граф Мэзона, связанный с выражением (6.40), к графу, имеющему лишь вершины 4 и и решите систему относительно