Введение в теорию графов. Индивидуальные задания (66
.pdfЗадание 12 Гамильтоновы циклы
1. Проверьте для графов Н1 , Н2 , Н3 выполнение достаточного условия существования в графе гамильтонова цикла: (u) ( ) p для любых двух не смежных вершин u и графа.
2.Найдите гамильтоновы циклы графов Н1 , Н2 , Н3 . Если достаточное
условие выполняется, то используйте известный алгоритм перестройки порядка вершин в последовательности A0 , A1 , A2 ,..., AP 1 .
3.Укажите номер графа, который доказывает, что сформулированное достаточное условие не является необходимым.
4.Докажите, используя метод от противного, что граф является связным, если выполняется достаточное условие его гамильтоновости.
5.Приведите по одному примеру графов 4 видов:
а) эйлеров и гамильтонов, б) эйлеров, но не гамильтонов,
в) гамильтонов, но не эйлеров, г) не эйлеров и не гамильтонов.
6. Приведите примеры практических задач, сводящихся к поиску гамильтоновых циклов в графах.
21
Варианты задания
22
23
Задание 13 Поиск наибольших паросочетаний в двудольном графе
1) Постройте двудольные графы, соответствующие первым двум системам различных представителей множеств À,Â,Ñ, ... . Первоначальный выбор представителей отмечен двойным подчеркиванием. Выясните, какие из заданных паросочетаний являются наибольшими, а остальные доведите до наибольших.
2)Найдите наибольшее паросочетание для третьей системы представи-
телей.
3)Приведите примеры практических задач, сводящихся к поиску наибольших паросочетаний.
Варианты задания
Вариант 1
а) A(1,4), B(2,5),C(1,4,6), D(2,3,6), E(1,4,7), F(1,5,6),G(1,7)
б) A(1,7), B(3,7),C(2,3,4,5,6), D(1,7), E(1,3,7)
в) A(1,2), B(3,4,5),C(2,3), D(3,4,5), E(2,3,4)
Вариант 2
а) A(2,6), B(1, 2,3,5),C(3,4,7), D(1,7), E(3,5), F(4,6)
б) A(1,2,3,4), B(1,2,3,4),C(1,2,3,4), D(5,6), E(5,6), F(5,6)
в) A(2), B(1,2,3,4),C(3,4), D(2,5), E(4,5)
Вариант 3
а) A(1,4), B(2,3,5,6),C(2,5), D(1,4), E(3,5,7), F(1,2,4,5)
б) A(1,2,3,4), B(2,3),C(2,3), D(2,3), E(3)
в) A(1,2), B(2,4),C(1,2,3,5), D(4), E(3,5)
24
Вариант 4
а) A(1,3,5,6,7), B(2,3),C(4), D(1,3,5), E(2,6), F(3,4,6),G(5,7)
б) A(1,2,3), B(1, 2,3),C(1,2,3), D(1,2), E(4,5,6), F(4,5,6)
в) A(1,3,4,5), B(2,3,4,5),C(1,2), D(2,3), E(2,3)
Вариант 5
а) A(2, 4), B(1, 2),C(2,3,5), D(3,6), E(2,5), F(1,6),G(3,4)
б) A(1), B(1, 2,3,4),C(1,2,3,4,5), D(1)
в) A(1), B(1,3,5),C(2,3,4,5), D(2,4,5), E(2,4)
Вариант 6
а) A(1,4,6), B(2,3,6),C(2,5), D(1,4,6), E(2,3,5,6), F(2),G(5)
б) A(1,4,5), B(3),C(2,3,5), D(3), E(3), F(3),G(1,2,5)
в) A(2), B(1,2,4),C(2,3), D(2,3,5), E(4,5)
Вариант 7
а) A(1,4,6), B(4,5),C(2,3,6), D(2,3), E(2,3,7), F(3,5,6),G(3, 7)
б) A(1,2,3, 4,5), B(6),C(6), D(1, 2,3,4,5), E(5,6) в) A(1,3), B(1,2,3),C(3,5), D(2,4), E(3,5)
Вариант 8
а) A(1,3,6), B(5, 6),C(4,6), D(2,3), E(1,6), F(2,5),G(3,4) б) A(1,2,3,4), B(1,2),C(1, 2), D(1,2)
в) A(4), B(2,4,5),C(3,4), D(1,3,4), E(1,2)
25
Вариант 9
а) A(3,4,5), B(2,1,5),C(1,2,5, 6), D(3,4,5), E(2,6), F(2),G(6)
б) A(1,4,5), B(3),C(2,3,5), D(3), E(3), F(3),G(1,2, 4,5)
в) A(1,2,3,4,5,6), B(2,4),C(4,6), D(2,4,6), E(1,4,6), F(1,3)
Вариант 10
а) A(3,6,7), B(4,5,6),C(2,4,6), D(2,4), E(1,2, 4), F(3,5),G(1,4) б) A(2,3,4,5), B(2,5),C(2,5), D(2,5), E(1,2, 6)
в) A(1,5), B(1,2,4),C(1,6), D(1,2,3,4,5), E(1), F(1,3,4,5)
26
Задание 14 Система фундаментальных циклов по Кирхгофу
В данном графе укажите число вершин, ветвей и хорд, выделите в нем два остова и определите системы фундаментальных циклов, определяемых выбранными остовами.
Вариант 1 |
Вариант 6 |
Вариант 2 |
Вариант 3
Вариант 4 |
Вариант 5 |
Вариант 7 |
Вариант 8 |
Вариант 9
Вариант 10
27
Задание 15 Экстремальное дерево
I. Выберите на карте 8 городов, никакие 4 из которых не лежат на одной прямой, перенесите их на бумагу, сохраняя измеренные в условных единицах расстояния межу ними. Составьте матрицу расстояний и определите по ней наиболее экономичное дерево, соединяющее города. Предполагается, что стоимость прокладки дороги пропорциональна ее длине. Постройте полученное дерево на приготовленной вами карте с отмеченными городами.
II. Взаимопонимание между членами коллектива, состоящего из 6 человек, оценено по 10-тибалльной системе. Оценки представлены в таблице с номером вашего варианта. Найдите дерево максимального взаимопонимания и постройте его диаграмму.
1 |
A |
B |
C |
D |
E |
F |
A |
Х |
9 |
1 |
2 |
8 |
3 |
B |
|
Х |
4 |
5 |
8 |
4 |
C |
|
|
Х |
7 |
2 |
10 |
D |
|
|
|
Х |
7 |
1 |
E |
|
|
|
|
Х |
3 |
2 |
A |
B |
C |
D |
E |
F |
A |
Х |
6 |
1 |
5 |
8 |
2 |
B |
|
Х |
4 |
7 |
3 |
1 |
C |
|
|
Х |
6 |
9 |
3 |
D |
|
|
|
Х |
5 |
6 |
E |
|
|
|
|
Х |
10 |
3 |
A |
B |
C |
D |
E |
F |
A |
Х |
7 |
10 |
6 |
6 |
1 |
B |
|
Х |
10 |
5 |
8 |
2 |
C |
|
|
Х |
10 |
9 |
3 |
D |
|
|
|
Х |
8 |
8 |
E |
|
|
|
|
Х |
7 |
4 |
A |
B |
C |
D |
E |
F |
A |
Х |
6 |
7 |
1 |
2 |
5 |
B |
|
Х |
8 |
9 |
3 |
1 |
C |
|
|
Х |
10 |
4 |
6 |
D |
|
|
|
Х |
9 |
7 |
E |
|
|
|
|
Х |
2 |
5 |
A |
B |
C |
D |
E |
F |
A |
Х |
5 |
3 |
10 |
8 |
7 |
B |
|
Х |
1 |
2 |
4 |
6 |
C |
|
|
Х |
3 |
9 |
8 |
D |
|
|
|
Х |
5 |
1 |
E |
|
|
|
|
Х |
2 |
6 |
A |
B |
C |
D |
E |
F |
A |
Х |
4 |
5 |
10 |
2 |
3 |
B |
|
Х |
8 |
8 |
3 |
7 |
C |
|
|
Х |
4 |
6 |
7 |
D |
|
|
|
Х |
2 |
4 |
E |
|
|
|
|
Х |
9 |
7 |
A |
B |
C |
D |
E |
F |
A |
Х |
10 |
6 |
5 |
2 |
4 |
B |
|
Х |
5 |
9 |
7 |
8 |
C |
|
|
Х |
5 |
4 |
4 |
D |
|
|
|
Х |
3 |
2 |
E |
|
|
|
|
Х |
6 |
8 |
A |
B |
C |
D |
E |
F |
A |
Х |
7 |
8 |
4 |
3 |
2 |
B |
|
Х |
8 |
9 |
8 |
6 |
C |
|
|
Х |
10 |
6 |
5 |
D |
|
|
|
Х |
10 |
10 |
E |
|
|
|
|
Х |
7 |
28
9 |
A |
B |
C |
D |
E |
F |
A |
Х |
4 |
7 |
6 |
2 |
5 |
B |
|
Х |
9 |
5 |
4 |
3 |
C |
|
|
Х |
10 |
9 |
2 |
D |
|
|
|
Х |
8 |
7 |
E |
|
|
|
|
Х |
6 |
10 |
A |
B |
C |
D |
E |
F |
A |
Х |
3 |
4 |
8 |
6 |
7 |
B |
|
Х |
5 |
9 |
5 |
8 |
C |
|
|
Х |
4 |
3 |
10 |
D |
|
|
|
Х |
4 |
2 |
E |
|
|
|
|
Х |
5 |
Задание 16 Построение символа α(Т) дерева Т, покрывающего данный граф,
и решение обратной задачи (алгоритм Пруфера)
Даны диаграмма дерева T1 и символ дерева (T2 ) . Найти (T1 ) и T2 .
Вариант 1 |
|
|
3 |
|
|
|
T1 |
11 |
4 |
7 |
|
1 |
|
10 |
|
|
5 |
|
8 |
9 |
2 |
6 |
|
|
|
|
(T2 ) {2, 3, 3, 7,12, 7, 2,12, 2, 7}
Вариант 2
Вариант 6 |
|
|
||
7 |
2 |
T1 |
|
|
11 |
3 |
|||
|
5 |
|||
|
|
|||
9 |
|
6 |
||
4 |
|
|||
1 |
|
|
||
12 |
10 |
8 |
(T2 ) {5, 5, 5, 2, 3, 8, 3, 3, 1,12,1}
Вариант 7
|
T1 |
|
3 |
|
|
1 |
|
4 |
7 |
|
|
8 |
6 |
|
|
|
|
||
5 |
2 |
9 |
|
11 |
|
10 |
|
||
|
|
|
|
(T2 ) {11, 6,12, 6, 6, 8, 8, 8, 6,13,13}
Вариант 3
6 |
1 |
|
T1 |
10 |
|
13 |
3 |
|
|
5 |
8 |
9 |
||
12 |
|
|
11 |
|
|
|
|
4 2 7
(T2 ) {10, 8,10,11,12, 8, 3, 3,1,1}
|
T1 |
2 |
|
4 |
|
13 |
5 |
6 |
|||
|
|||||
|
|
|
|||
1 |
|
3 |
8 |
||
|
7 |
||||
12 |
|
|
|
||
|
10 |
9 |
|
||
11 |
|
|
|||
|
|
|
|
(T2 ) {7, 5, 5, 9, 5, 5, 4,1, 9, 9}
Вариант 8
10 |
12 |
1 |
T1 |
7 |
|
11 |
|
8 |
2 |
6 |
4 |
|
|
|
|
13
9 5
3
(T2 ) {2, 5, 7, 7, 7, 2, 9,1}
29
Вариант 4
2 |
T1 |
|
7 |
|
|
|
|
|
9 |
6 |
11 |
||
|
3 |
4 |
|
|||
|
|
|
|
|
1 |
8 |
10 |
5 |
12
(T2 ) {5, 5,1,13,14,13, 3,14, 2, 2, 8, 8}
Вариант 5
|
|
3 |
2 |
|
9 |
|
7 |
|
|
|
|
|
6 |
8 |
|
|
T1
10 1
5 |
4
(T2 ) {5, 6, 6, 6, 2, 8,12,1, 8, 9}
Вариант 9 |
|
|
|
||
|
|
|
9 |
|
6 |
|
|
|
|
|
|
|
|
T1 |
13 |
1 |
5 |
|
|
|
|
|
|
12 |
2 |
8 |
|
|
4 |
|
|
14 |
3 |
||
|
|
|
|
||
|
|
11 |
|
|
10 |
|
|
7 |
|
|
|
|
|
|
|
|
|
(T2 ) {3, 3, 4, 4, 8,10, 6, 6,10, 5}
Вариант 10
7 |
12 |
11 |
6 |
|
|
1 |
|
T1 |
|
|
3 |
|
|
|
|
8 |
|
|
2 |
10 |
|
9 |
|
|
|
|
||
|
5 |
|
|
4 |
(T2 ) {12,13,12,12,12,13, 9, 9, 8, 3,13}
Задание 17.
Планарные графы и их плоские укладки
Определите, какой из двух заданных в варианте графов не является планарным. Перерисуйте граф с указанием его номера (1 или 2) и выделите другим цветом подграф, свидетельствующий о непланарности графа. Укажите вид ( K5 или K33 ) выделенного подграфа.
Перерисуйте другой граф и рядом постройте его плоскую укладку с прямолинейными ребрами, сохранив метки вершин. Для проверки сосчитайте у графа и его плоской укладки число ребер q и степени вершин. Определите, какие ребра можно добавить в заданном графе, сохраняя его планарность. Постройте плоскую укладку графа с добавленными ребрами.
30