Боднарчук Ю.В., Олійник Б.В. Методичні рекомендації. Дискретна математика
Подождите немного. Документ загружается.
7. Нехай у графi G з n вершинами i m ребрами є p вершин степеня t, а всi
iншi вершини мають степiнь t + 1. Довести, що p = (t + 1)n − 2m.
8. Чи iснує граф з n вершинами, усi вершини якого є кiнцевими, якщо
a) n = 10;
b) n = 11;
c) n = 2k;
d) n = 2k + 1.
9. Побудувати кубiчний граф, що має
a) 6 вершин;
b) 4 вершини;
c) 8 вершин;
10. Визначити, чи серед пар графiв, зображених на малюнках є iзоморфнi.
a)
b)
c)
d)
131
e)
f)
g)
h)
i)
j)
132
k)
l)
m)
n)
o)
11. Довести, що iзоморфiзм є вiдношенням еквiвалентностi на множинi всiх
графiв.
12. Побудувати чотири попарно неiзоморфнi самодоповнювальнi (тобто такi,
що iзоморфнi своєму доповненню) графи з вiсьмома вершинами.
13. Перевiрити, чи будуть iзоморфними графи G
1
i G
2
, що заданi матрицями
сумiжностi A
1
i A
2
вiдповiдно.
133
a) A
1
=
0 1 1 1 1 1
1 0 1 1 1 1
1 1 0 1 1 0
1 1 1 0 0 1
1 1 1 0 0 0
1 1 0 1 0 0
A
2
=
0 0 1 1 0 1
0 0 1 1 1 1
1 1 0 1 1 1
1 1 1 0 1 1
0 1 1 1 0 0
1 1 1 1 0 0
,
b) A
1
=
0 1 1 0 1 0 1
1 0 1 0 0 1 0
1 1 0 0 0 0 1
0 0 0 0 1 0 1
1 0 0 1 0 1 0
0 1 0 0 1 0 0
1 0 1 1 0 0 0
A
2
=
0 1 1 1 1 0 0
1 0 1 1 0 0 0
1 1 0 0 0 1 0
1 1 0 0 1 0 0
1 0 0 1 0 0 1
0 0 1 0 0 0 1
0 0 0 0 1 1 0
.
14. Зобразити всi попарно неiзоморфнi графи з n вершинами, якщо
a) n = 2;
b) n = 3;
c) n = 4;
d) n = 5.
15. Знайти в графi K
5
цикли довжини
a) 3;
b)
4
;
c) 6;
d) 9;
e) 10.
Якi з цих циклiв є простими?
16. Довести, що зв’язний граф є простим циклом тодi i тiльки тодi, коли сте-
пiнь кожної вершини дорiвнює двом.
17. Скiльки ребер мiстить
a) простий ланцюг iз k вершин;
b) простий цикл iз k вершин;
c) найкоротший простий цикл?
18. Зобразити кубiчний граф з 2n вершинами (n ≥ 3), який не має трикутни-
кiв.
134
19. Довести, що граф є дводольним тодi i тiльки тодi, коли всi його цикли
мають парну довжину.
20. Довести, що для довiльного графа G або вiн сам, або його доповнення G є
зв’язним графом.
21. Скiльки iснує попарно неiзоморфних графiв, якi мають
a) 6 вершин, 7 ребер i 2 компоненти зв’язностi;
b) 8 вершин, 6 ребер i 2 компоненти зв’язностi;
c) 8 вершин, 6 ребер i 3 компоненти зв’язностi?
22. Побудувати три попарно неiзоморфнi графи з вiсьмома вершинами, якi
мають ейлеровi цикли.
23. Перевiрити, чи будуть графи з прикладу 13 ейлеровими, напiвейлеровими,
гамiльтоновими, напiвгамiльтоновими.
24. Перевiрити, чи будуть такi графи ейлеровими, напiвейлеровими, гамiльто-
новими, напiвгамiльтоновими:
a)
b)
25. На малюнку зображено схеми музеїв. Вершинами графiв позначено зали
музеїв, а ребрами — переходи мiж залами. З якого залу потрiбно розпочати
маршрут екскурсiї i в якому закiнчити для того, щоб вiдвiдувачi побували
в кожнiй зала i пройшли по кожному переходу один раз. Визначити один
з таких маршрутiв.
135
a)
b)
26. Побудувати граф iз вiсьмома вершинами, який не має ейлерового циклу,
але має ейлерiв ланцюг.
27. Довести, що в повному графi K
n
, n ≥ 3, iснує гамiльтонiв цикл. Якщо про-
нумерувати вершини цього графа, то скiльки рiзних гамiльтонових циклiв
має K
n
? Скiльки ейлерових?
28. Навести приклад графа, що є ейлеровим i не є гамiльтоновим, а також
приклад гамiльтонового графа, що не є ейлеровим.
29. Охарактеризувати графи, що є одночасно ейлеровими i гамiльтоновими.
30. Побудувати всi попарно неiзоморфнi зв’язнi графи без циклiв з п’ятьма
вершинами.
31. Побудувати всi попарно неiзоморфнi зв’язнi графи без циклiв з шiстьма
вершинами.
32. Побудувати всi попарно неiзоморфнi дерева з трьома, чотирма i п’ятьма
вершинами.
33. Побудувати всi попарно неiзоморфнi дерева, що мають
a) 6 ребер i 3 кiнцевi вершини;
136
b) 6 ребер i 4 кiнцевi вершини;
c) 8 вершин та 3 вершини степеня 3?
34. Довести, що будь-яке дерево має принаймнi 2 кiнцевi вершини.
35. Довести, що дерево має тiльки двi кiнцевi вершини тодi i тiльки тодi, коли
воно є простим ланцюгом.
36. Описати всi дерева, доповнення яких також є деревами.
37. Побудувати кiстяковi дерева для графiв з прикладу 13. Обчислити циклi-
чний ранг графiв.
38. Довести, що в деревi кожне ребро є мостом.
39. Про групу з 50 студентiв вiдомо, що серед довiльної четвiрки студентiв
завжди знайдеться один студент, знайомий з трьома iншими. Довести, що
тодi обов’язково знайдеться студент, знайомий з кожним з групи.
137
Рекомендована лiтература
[1] Ф.А. Новиков Дискретная математика (для программистов).—СПб: Пи-
тер, 2000.—304с.
[2] М.Й. Ядренко. Дискретна математика. Навчально-методичний посiбник,—
Київ: Вид.-полiграф. цент "Експрес", 2003р.—244с.
[3] Р. Грэтхем, Д. Кнут, О. Паташник. Конкретная математика. —Москва,
Мир, 1998.
[4] А.Я. Оленко, М.Й. Ядренко. Дискретна математика. Навчально-
методичний посiбник, Видавництво НаУКМА-1996.
[5] Н.Я. Виленкин. Индукция. Комбинаторика. — Москва: Просвещение,
1976.
[6] Н.Я. Виленкин, А.Н. Виленкин, П.А. Виленкин. Комбинаторика. —
Москва: ФИМА, МЦНМО, 2006.— 400с.
[7] Р. Уилсон Введение в теорию графов М.Мир — 1977. 7. Р. Столл Множе-
ства, логика, аксиоматические теории, "Просвещение"Москва, 1963.
[8] В.I. Андрiйчук, М.Я. Комарницький, Ю.Б. Iщук. Вступ до дискретної ма-
тематики. Львiв: Видавничий центр ЛНУ iменi Iвана Франка, 2003.– 254с.
[9] Ю.В. Капiтонова, С.Л. Кривий,О.А. Летичевський,Г.М. Луцикий, М.К.
Песурiн. Основи дискретної математики. Київ: "Наукова думка— 2002.
[10] М. Холл Комбинаторика, — Москва, Мир, 1970.
138