Примерный перечень типовых задач

1. Изобразить диаграмму графа с вершинами и ребрами , , , . Указать смежные вершины, для каждой вершины перечислить инцидентные ей ребра, определить степени вершин, перечислить изолированные и висячие вершины (если они есть). Перечислить висячие ребра, кратные ребра и петли (если они есть).

2. Выяснить, существует ли граф со следующим набором степеней вершин: 0, 1, 3, 3, 5.

3. Выяснить какие из графов, представленные на рис. 1, своими диаграммами, изоморфны между собой.

Рис. 1

4. Найти все (с точностью до изоморфизма) обыкновенные графы с 3 вершинами.

5. Выписать матрицу смежности и матрицу инцидентности графа из упр. 1.

6. Изобразить диаграмму графа, матрица смежности которого имеет вид

а) ; б) .

7. Изобразить диаграмму графа, матрица инцидентности которого имеет вид:

а) ; б) .

8. На графе , изображенном на рис. 1, найти:

а) путь длины 7, не являющийся цепью;

б) цепь длины 5, не являющейся простой;

в) цикл, не являющийся простым;

г) простой цикл четной длины;

д) простой цикл нечетной длины.

9. Найти все (с точностью до изоморфизма) связные обыкновенные графы с 4 вершинами.

10. Сколько компонент связности имеет граф , заданный:

а) матрицей смежности	б) матрицей инцидентностей
;	?

11. Сколько ребер граф, диаграмма которого изображена на рис. являются мостами:

а) на рис. 2; б) на рис. 3; в) на рис. 4?

Рис. 2	Рис. 3	Рис. 4

12. Приведите пример связного обыкновенного графа с тремя ребрами

а) ни одно ребро которого не является мостом;

б) все ребра которого являются мостами.

13. Найти цикломатическое число графа:

а) ; б) ; в) ; г) рис. 3.

14. Представьте диаграммами все (с точностью до изоморфизма) деревья с шестью вершинами.

15. Изобразить диаграммами все леса с 3 ребрами и шестью вершинами.

16. Построить остовы графов , , , , изображенные на рис. 1.

17. Найдите число остовов, а также сами остовы, в помеченном графе .

18. Дан граф с вершинами , ребрами , , , , , , , , , , и весовым отображением , , , , , , , , , , , . Построить минимальный остов графа и вычислить его вес.

19. Построить бинарный код дерева, изображенного на рис. 5.

Рис. 5	Рис. 6

20. Построить дерево по коду .

21. Построить код Прюфера дерева, изображенного на рис. 6.

22. Построить дерево по коду [2 2 5 5 7].

23. а) Одной из диаграмм графа является трехмерный куб (рис. 7). Планарен ли данный граф?

б) Одной из диаграмм графа является трехмерный куб, в котором проведена диагональ (рис. 8). Планарен ли данный граф?

24. а) Одной из диаграмм графа является октаэдр (рис. 9). Планарен ли данный граф?

б) Одной из диаграмм графа является октаэдр, в котором проведена диагональ (рис. 10). Планарен ли данный граф?

Рис. 7	Рис. 9	Рис. 9	Рис. 10

25. Построить эйлеров цикл на графе, изображенном на рис. 11.

26. Построить эйлеров путь на графе, изображенном на рис. 12.

Рис. 11	Рис. 12

27. Показать, что на следующих графах есть гамильтоновы циклы:

а) ; б) .

28. а) Привести пример графа, который является эйлеровым, но не гамильтоновым.

б) Привести пример графа, который является гамильтонвым, но не эйлеровым.

в) Привести пример графа, который является как эйлеровым, таки гамильтоновым.

г) Привести пример графа, который не является ни гамильтонвым, ни эйлеровым.

29. Построить обыкновенный плоский граф с минимальным числом вершин, хроматическое число которого равно 4.

30. Для следующих графов найти хроматические числа и привести пример раскраски графов в соответствующее число цветов:

а) ; б) ; в) ; г) ;

д) граф Петерсона (рис. 11).

31. Найти все (с точностью до изоморфизма) обыкновенные орграфы с тремя вершинами и не более чем тремя дугами.

32. Выписать матрицу смежности и инцидентности для орграфа с вершинами , , , и дугами , , , .

33. Изобразить все (с точностью до изоморфизма) турниры с четырьмя вершинами. Сколько среди них сильно связных?

34. В сети, изображенной на рис. 13, найти расстояние от вершины до остальных вершин и указать кратчайший путь от вершины до вершины .

35. В сети, изображенной на рис. 14, найти расстояние от вершины до остальных вершин и указать кратчайший путь от вершины до вершины .

Рис. 13	Рис. 14

36. Найти максимальный поток и минимальный разрез для сети, изображенной:

а) на рис. 15; б) на рис. 16.

Рис. 15	Рис. 16

37. Построить схемы в базисе , реализующие основные элементарные функции двух переменных.

38. Построить схемы в базисе , реализующие функции:

а) ;

б) .

Ответы:

1. Диаграмма графа изображена на рис. 17. 2. Диаграмма графа изображена на рис. 3. 3. , и изоморфны, им не изоморфен. 4. Всего таких графов 4. 5. ; . 6. а) см. рис. 18; б) см. рис. 2. 7. а) см. рис. 18; б) см. рис. 19.

Рис. 17	Рис. 18	Рис. 19

8. а) например, ; б) например, ; в) не существуют; г) например, ; д) не существуют. 9. Таких графов всего 6. 10. а) две; б) три. 11. а) одно; б) одно; в) четыре. 13. а) 4; б) 6; в) 2; г) 4. 14. а) Рис. 20. 15. Рис. 21. 17. Имеется 4 остова; на рис. 22 изображен помеченный граф и его остовы. 18. Например, минимальным остовом является граф с вершинами , ребрами и весом 6. 19. . 20. Рис. 23. 21. [2 2 4 6 4 2 4]. 22. Рис. 24.

Рис. 20
Рис. 21
Рис. 22

Рис. 23	Рис. 24

23. а) Исходная и плоская укладки графа представлена на рис. 25 (соответствующие вершины помечены одинаковыми буквами). б) Непланарен.

Рис. 25

24. а) Исходная и плоская укладки графа представлена на рис. 26 (соответствующие вершины помечены одинаковыми числами). б) Непланарен.

Рис. 26	Рис. 27	Рис. 28

25. Один из эйлеровых циклов задается последовательностью вершин с индексами: 1, 8, 7, 6, 5, 4, 3, 7, 4, 8, 3, 2, 1. 26. Одна из эйлеровых цепей задается последовательностью вершин с индексами: 2, 4, 6, 5, 4, 3, 5, 1, 3, 7, 4, 8, 7, 1, 8, 2, 1. 27. а)Один из гамильтоновых циклов задается последовательностью вершин с индексами (рис. 27): 1, 2, 3, 4, 5, 1. б)Один из гамильтоновых циклов задается последовательностью вершин с индексами (рис. 28): 1, 2, 3, 4, 5, 6, 1. 28. а) ; б) ; в) ; г) . 29. . 30. а) ; б) ; в) ; г) ; д) 3. 31. См. рис. 29.

Рис. 29

32.

; .

33. См. рис. 30 (последняя диаграмма соответствует сильно связному графу).

Рис. 30

34. Расстояние от вершины до равно 5, от до равно 2, от до равно 4, от до равно 7, от до равно 5, от до равно 9. Кратчайший путь от вершины до вершины проходит последовательно через вершины . 35. Расстояние от вершины до равно 3, от до равно 3, от до равно 2, от до равно 4, от до равно 5, от до равно 6. Кратчайший путь от вершины до вершины проходит последовательно через вершины . 36. а) Один из максимальных потоков изображен на рис. 31. Этому потоку соответствует минимальный разрез , . Величина максимального потока и пропускная способность минимального разреза равна 16. потока. б). Один из максимальных потоков изображен на рис. 32. Этому потоку соответствует минимальный разрез , . Величина максимального потока и пропускная способность минимального разреза равна 16. потока.