Методичка (дискретка)
.pdfa)маршрут довжиною 5;
b)ланцюг довжиною 5;
c)простий ланцюг довжиною 5. Навести приклади.
19.Якщо два різні цикли графа G містять ребро e , то в графі G існує цикл, серед ребер якого немає ребра e . Довести.
20.Побудувати всі дерева з 6 вершинами (з точністю до ізоморфізму).
21.Довести, що в дереві T (V , E) |
з n вершинами виконується рівність |
|
(v) 2n 2 , де (v) |
степінь вершини v . |
|
v V |
|
|
22.Яку дерево з n
найбільшу і найменшу кількості кінцевих вершин може мати вершинами? Яку структуру мають такі дерева?
23.Описати всі дерева, доповнення яких також є деревами. 24.Описати всі дерева, які є самодоповнювальними графами.
25.Скільки основних дерев має повний граф
Kn
?
26.Побудувати орієнтований граф, який має 8 вершин, 2 стоки та одне джерело.
27.Побудувати повний орієнтований граф з шістьма вершинами.
|
|
|
|
|
C7 |
|
|
|
|
1. |
Нехай |
A – матриця суміжності графа |
G з n вершинами. Довести, |
||||||
що i -й діагональний елемент матриці A |
2 |
дорівнює степеню i -ї вершини |
|||||||
|
|||||||||
графа |
G, |
i 1, 2,..., n . |
|
|
|
|
|
|
|
2. |
Навести приклад графа, в якому існує простий ланцюг з вершини v1 |
||||||||
в вершину v |
та з вершини v |
2 |
у вершину v |
, але не існує простого ланцюга |
|||||
|
|
2 |
|
|
3 |
|
|
||
з вершини v |
у вершину v через вершину v |
2 |
. |
||||||
|
|
1 |
3 |
|
|
|
|
|
|
3.Довести, що якщо зі зв’язного графа видалити довільне ребро, що міститься в деякому простому циклі, то граф залишиться зв’язним.
4.Довести, що в зв’язному графі будь-які два прості ланцюги максимальної довжини мають принаймні одну спільну вершину.
5.Задача Рамсея. Довести, що серед довільних шести осіб знайдуться або троє попарно знайомих, або троє попарно незнайомих.
51
6. |
З’ясувати, чи будуть ізоморфними графи: |
|
|
|||||
|
a |
|
|
|
b |
2 |
|
3 |
|
|
|
|
|
|
|||
|
|
|
|
e |
f |
|
5 |
6 |
|
|
|
|
|
|
|||
|
a) |
|
|
|
|
|
|
|
|
|
|
h |
|
g |
|
8 |
7 |
|
|
|
|
|
|
|||
|
d |
|
|
|
c |
1 |
|
5 |
|
a |
|
|
|
b |
|
3 |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
f |
|
|
|
|
|
b) |
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
d |
|
|
|
c |
1 |
|
2 |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
||
|
a |
|
|
|
b |
|
3 |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
c) |
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
d |
|
|
|
c |
1 |
|
2 |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
||
|
|
|
|
d |
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
e |
|
|
c |
5 |
|
3 |
|
d) |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
a |
b |
|
1 |
|
2 |
|
|
|
|
|
|
|||
|
|
1 |
|
2 |
3 |
|
a |
d |
|
|
|
|
|
||||
|
e) |
|
|
4 |
|
|
b |
c |
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
e |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
2 |
3 |
|
a |
b |
|
f) |
|
|
4 |
|
|
c |
d |
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
e |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
52 |
|
|
9. Довести, що в графі з ребро, є принаймні один цикл.
n
вершинами, який має більше ніж
n 1
10.Описати у термінах теорії графів наступні бінарні відношення на
скінченній множині: |
a) транзитивні відношення; |
b) |
відношення |
||
еквівалентності; |
c) |
відношення часткового порядку; |
d) |
відношення |
|
лінійного порядку. |
|
|
|
|
|
11.Описати відношення, що відповідають: |
a) орієнтованим графам без |
||||
петель; b) неорієнтованим графам без петель; |
c) орієнтованим графам з |
||||
петлями. |
|
|
|
|
|
СПИСОК ВИКОРИСТАНОЇ ТА РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ
1.Бондаренко М.Ф., Белоус Н.В., Руткас А.Г. Компьютерная дискретная математика. – Харьков: Компания СМИТ, 2004. – 476 с.
2.Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печурін М.К. Основи дискретної математики. – Київ: Наукова думка,
2002. – 580 с.
3.Кук Г., Бейз Д. Компьютерная математика. – М.: Наука, 1990. – 400 с.
4.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 2001. – 234 с.
5.Мороховець М.К. Дискретний аналіз. Курс лекцій для студентів спеціальностей, пов’язаних з інформаційними технологіями та захистом інформації. Частина 1. Множини та відношення. – Київ: НТУУ “КПІ”, 2006. – 65 с.
6.Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. Дискретна математика. – Київ: Видавнича група BHV, 2007. – 367 с.
7.Столл Р. Множества. Логика. Аксиоматические теории. – М.: Просвещение, 1968. – 231 с.
8.Трохимчук Р.М. Основи дискретної математики. Практикум. – Київ:
МАУП, 2004. – 163 с.
53