РГЗ по графам

4

РГЗ №1 «Исследование свойств графов. Построение основных матриц. Решение системы линейных алгебраических уравнений методом графов»

Задача 1.

1. Во всяком подграфе, являющемся путем, степени двух вершин равны 1, степени остальных вершин равны 2. Верно ли обратное: всякий подграф обыкновенного графа с таким свойством является путем? Почему?

2. Во всяком подграфе, являющемся циклом, степени всех вершин равны 2, Верно ли обратное: всякий подграф обыкновенного графа с таким свойством является циклом? Почему?

3. Доказать, что удаление циклического ребра графа не приводит к увеличению числа компонент связности графа.

4. Доказать, что если G' является остовом G , то G' - ациклический и имеет (n-1) ребер.

5. Всякий ли разрез является разрезающим множеством? А обратно? Почему?

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

7. Пусть G' G. Доказать, что никаких двух свойств G' (кроме 3) и 4)) недостаточно, чтобы G' являлся остовом G:

1) G' имеет n вершин; 2) G' связный; 3) G' имеет (n-1) ребер; 4) G' - ациклический.

8. Доказать, что любой разрез является объединением реберно-непересекающихся разрезающих множеств.

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

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

11. В графе К построить векторы базисных циклов и базисных разрезающих множеств относительно некоторого остова. Указать подграф, который нельзя представить кольцевой суммой подграфов из W(подпространства циклов) и W(подпространства разрезов).

12. Пусть все вершины графа G имеют степень k или k+1. Доказать, что если G имеет n вершин степени k и n вершин степени k+1, то n= (k+1)n - 2m.

13. Доказать, что если в графе существуют пути между вершинами a и b, а также между b и c, то существует путь между a и c.

14. Пусть Р и Р - два различных пути между вершинами графа. Доказать, что РР является циклом или объединением нескольких реберно-непересекающихся циклов.

15. Доказать, что замкнутая цепь, все вершины которой имеют степень 2, является циклом.

16. Показать, что если два различных цикла графа содержат ребро e, то в графе существует цикл, не содержащий е.

17. Доказать, что граф G является связным тогда и только тогда, когда для каждого разбиения (V,V) множества V с непустыми V и V существует ребро в G, соединяющее вершину из V с вершиной из V.

18. Пусть G - такой граф, что m< n-1. Доказать, что G - несвязный граф.

19. Доказать, что если для графа G выполняется неравенство mn, то G содержит циклическое ребро.

Задача 2.

По заданному орграфу (образцы по вариантам прилагаются) построить матрицы:

• инцидентности;

• БРМ;

• БЦ;

• смежности.

1. 2. 3.

1 3 1 2 1 3

4 3 2

5 7 8 4 5 6 7 4 5 6 7

9

6 2 8 9 8 9

4. 5. 6.

1 2 3 1 2 3 1 2 3

4

4 5 6 7 8 6 7 4 6 7

9 9

5 8 9 5 8

7. 8. 9.

1 2 3 1 5 1 4

4

5 7 8 6 2 7 4 5 6 2 3 8

7

9 6 8 3 9 9

15

10. 11. 12.

1 4 1 2 3 1 2

5 4 3

6 2 7 8 5 6 7 8 4 5 6 7

9

9 3 8 9

13. 14. 15.

1 2 3 1 2 3 1 2 3

4

4 5 6 7 4 5 6 7 8 6 7 8

9 9

8 9 5

16. 17. 18.

1 2 3 1 3 1 5

4 2 3 4