Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200

• Название: Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
• Анкор: Дискретная Математика
• Дата: 15.09.2022
• Размер: 6.37 Mb.
• Имя файла: S_D_Shaporev_-_Diskretnaya_matematika_-_2004.pdf
• Тип: Учебное пособие; #679116
• страница: 18 из 26

3.19. Практическое занятие № 8. Остовы графов, фундаментальные циклы.
Эйлеровы и гамильтоновы графы. Доминирующие множества и клики
3.19.1. Для графа G , заданного матрицей весов, построить минимальный по весу остов
/
G
и найти его вес
 
/
ω G .
1)











































2 3
14 2
5 1
8 5
6 1
4 3
6 3
2 5
1 1
3 6
8 4
2 6
10 14 5
10 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
2)











































12 11 8
12 10 7
10 10 9
15 11 9
7 9
12 7
15 7
13 15 8
9 13 7
10 12 15 7
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
3)











































12 6
7 12 11 12 12 11 9
10 14 12 9
12 9
6 10 12 10 11 7
9 10 10 12 14 11 10 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
4)











































11 9
4 9
7 11 9
8 7
8 6
7 8
5 6
9 7
5 10 5
4 8
6 10 3
6 5
3 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
5)











































12 6
15 11 12 8
10 15 8
9 19 13 6
9 8
10 15 10 19 7
15 8
7 8
11 13 10 8
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
6)









































7 10 9
5 7
8 5
7 8
6 8
9 10 5
6 7
12 9
8 7
11 8
5 9
12 11 6
7 8
6 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
7)











































9 10 4
8 7
6 9
8 5
6 3
7 5
4 6
10 6
4 7
8 4
6 7
3 6
3 8
3 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
8)









































11 6
15 11 12 12 8
11 12 11 9
12 11 10 12 15 6
9 10 14 10 15 8
12 14 9
11 15 10 9
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
9)











































6 5
6 6
4 7
5 5
4 8
10 9
7 8
6 6
5 10 6
7 9
9 6
7 8
6 9
8 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
10)









































8 6
8 8
7 6
9 6
6 7
5 10 6
5 7
6 9
9 7
11 4
8 10 6
11 8
6 9
4 8
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11)











































2 5
5 4
2 6
2 4
3 1
4 5
3 3
1 5
2 1
3 6
5 4
1 6
10 6
5 10 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12)









































6 5
11 8
8 6
3 6
5 3
7 8
11 7
4 7
14 6
8 4
5 11 8
7 5
5 8
14 11 5
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x

87 13)











































9 11 10 7
6 9
7 5
9 6
8 6
5 8
7 11 9
8 9
5 6
7 9
6 10 8
5 6
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
14)









































6 5
4 6
3 9
7 8
8 5
3 6
7 4
9 6
4 10 7
7 4
7 8
8 10 7
5 8
8 5
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
15)







































5 7
8 6
5 8
6 9
7 8
3 7
3 10 6
3 6
5 8
7 6
4 5
6 3
5 4
6 9
10 5
6 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
16)











































7 4
4 8
9 3
10 7
8 3
5 6
4 9
3 6
3 6
8 8
10 5
8 7
4 6
8 7
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
17)











































14 16 7
18 15 14 14 15 15 13 11 14 15 9
14 16 13 9
13 10 7
14 13 12 18 11 10 12 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
18)











































6 8
3 7
6 7
5 9
6 8
7 5
3 5
9 11 7
5 8
4 9
9 8
5 6
11 4
5 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
19)









































9 4
7 9
4 5
12 4
3 7
9 10 4
5 3
11 5
12 7
11 6
9 7
9 5
6 8
10 9
8 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
20)











































7 8
9 9
5 10 8
7 9
3 7
8 5
3 13 8
9 7
6 5
10 13 6
11 8
8 5
11 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
21)













































4 7
3 10 7
4 8
4 7
5 6
5 8
7 5
12 3
4 6
11 8
5 12 10 8
11 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
22)













































11 7
8 6
11 9
5 9
6 3
10 11 7
6 3
12 10 8
3 3
5 10 12 6
11 10 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
23)











































7 9
7 7
8 9
8 8
4 6
5 14 9
9 4
7 10 8
6 7
12 5
7 5
12 14 10 12 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
24)








































5 8
4 16 5
5 6
11 5
10 7
9 7
4 6
10 5
12 11 7
5 4
8 9
4 3
16 7
12 8
3 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
25)













































9 3
10 4
5 15 11 9
4 12 6
8 3
5 12 5
17 10 6
5 7
15 8
17 11 7
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
26)











































3 12 6
11 3
4 4
6 8
12 4
5 5
7 4
2 9
6 6
5 2
6 11 8
5 9
6 7
7 6
5 4
3 2
1 7
6 5
4 3
2 1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
27)







































3 12 7
10 15 3
6 8
7 12 6
13 5
6 9
7 8
13 4
11 10 7
5 4
8 15 6
11 3
9 8
3 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
28)









































5 4
15 20 5
8 10 11 14 8
12 7
5 7
4 10 12 6
11 7
6 3
15 14 5
3 4
20 7
4 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
29)













































4 10 9
10 4
4 3
6 10 4
5 4
3 8
7 9
6 5
1 10 4
8 1
2 7
2 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
30)











































4 18 7
4 11 5
13 18 11 8
15 16 7
5 8
8 2
13 15 8
4 5
4 10 16 2
5 10 7
6 5
4 3
2 1
7 6
5 4
3 2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
3.19.2. Используя матричную теорему Кирхгофа, найти число остовных деревьев в полном двудольном графе
n
m
K
,

88 3.19.3. Найти матрицы фундаментальных циклов, радиусы и диаметры графов, изображенных на рисунке 3.43. Являются ли изображенные графы эйлеровыми или гамильтоновыми? а)
1
x
2
x
3
x
4
x б)
1
x
2
x
3
x
4
x в)
1
x
2
x
3
x
4
x г)
1
x
2
x
3
x
4
x
8
x
7
x
6
x
5
x
8
x
7
x
6
x
5
x
8
x
7
x
6
x
5
x
8
x
7
x
6
x
5
x
Рис. 3.43.
3.19.4. Доказать, что если для любых двух несмежных вершин x и
y
связного n - вершинного графа выполняется условие
   
n
y
P
x
P


, то граф имеет гамильтонов цикл.
3.19.5. По алгоритму Флери найти эйлеров цикл в графах, изображенных на рисунке
3.44.
5
x а)
3
x б)
1
x
3
x
1
x
4
x
6
x
2
x
9
x
2
x
12
x
8
x
7
x
4
x
11
x
10
x
6
x
5
x
Рис. 3.44.
3.19.6. Найти наибольшее независимое множество вершин в графе Петерсена

(см. рис. 3.45).
2
x
8
x
1
x
3
x
7
x
9
x
6
x
10
x
5
x
4
x
Рис. 3.45. Граф Петерсена.
3.19.7. Показать, что граф Петерсена негамильтонов.
3.19.8. Найти число доминирования
 
G
δ
и наименьшее доминирующее множество следующих графов: а)
2
x б)
8
x в)
1
x
2
x
3
x
4
x
3
x
2
x
3
x
7
x
9
x
1
x
7
x
4
x
8
x
7
x
6
x
5
x
5
x
1
x
4
x
5
x
6
x
Рис. 3.46.
3.19.9. Построить дерево поиска клик, матрицу клик и найти наибольшие клики графов, изображенных на рисунках 3.44 а), 3.45 и 3.46 б), в).

Джулиус Петер Христиан Петерсен (1839 - 1910) – датский математик

89 3.19.10. Приведите пример графа, в котором наименьшее доминирующее множество не является независимым.