Закріплення вивченого і оцінювання рівня знань
Оцінювання знань студентів здійснюється шляхом оцінювання правильності відповідей, правильності розв’язування задач, активності на занятті.
Домашнє завдання
Задача. Побудувати машину Т, яка застосовна до всіх слів у алфавіті {а, b} і яка кожне слово х1х2…хn-1хn в початковій конфігурації перетворює на слово хn хn-1…х2х1 в заключній конфігурації.
ВИКЛАДАЧ – Данилова В.А.
Практичне заняття №9
ТЕМА: Задачі теорії графів (2 год.)
МЕТА:
навчальна: вчити студентів зображувати графи різними способами, будувати графи за їх матрицями суміжності, інцедентності, визначати степені вершин графів, ;
розвиваюча: розвивати логічне мислення;
виховна: виховувати інтерес до комп’ютерної математики.
ОБЛАДНАННЯ: олівці, лінійки
ПЛАН
1 Використання основних властивостей графів
2 Розв’язування задач на побудову графів за їх матрицями суміжності, інцедентності, списком пар
Зміст практичного заняття
1 Використання основних властивостей графів
Задача 1. Нехай задано граф G =(V,E ):
а) V = {1,2,3,4}, E = {(1,3),(2,3),(3,4),(4,1),(4,2)};
б) V = {a,b,c,d,e},E = {(a,d),(b,c),(b,e),(c,e),(d,b),(d,e),(e,a)};
в) V = {1,2,3}, E = {(1,2),(1,3),(2,3)};
г) V = {A,B,C,D}, E = {(A,B),(A,D),(B,C),(B,D),(C,A),(C,D)}.
Побудувати діаграму, матриці суміжності та інцидентності для кожного із заданих графів.
Розв'язання
а) діаграма
Матриця суміжності
Матриця інцедентності
-
(1,3)
(2,3)
(3,4)
(4,1)
(4,2)
1
1
0
0
1
0
2
0
1
0
0
1
3
1
1
1
0
0
4
0
0
1
1
1
Задача 2. Розглянути турнір між чотирма футбольними командами, в якому кожні дві команди зіграли між собою не більше одного матчу. Подати турнір графом, вершинами якого є команди.
Задача 3. Визначити кількість вершин, ребер та степені вершин графів
Задача 4. Зобразити всі підграфи графа.
Задача 5 Знайти об’єднання графів
Задача 6. Кілька осіб (більше двох) проводять шаховий турнір в одне коло. У деякий момент виявилося, що тільки двоє шахістів зіграли однакову кількість партій. Довести, що тоді є або тільки один учасник, який не зіграв жодної партії, або тільки один, який зіграв усі партії.
Доведення
Мовою теорії графів задача перекладається наступним чином. У графі з n (n > 2) вершинами тільки дві вершини мають однакові степені. Довести, що є або лише одна вершина степеня 0, або лише одна степеня n-1. Розглянемо всі можливі заперечення цього твердження. Якщо припустити, що немає вершин степеня як 0, так і n-1, то n вершин мають степені від 1 до n-2, тобто серед них є або дві пари вершин, або три вершини з однаковими степенями, що суперечить умові. Отже, вершини степеня 0 або степеня n-1 є. За теоремою 1 одночасно таких бути не може. Якщо є дві вершини степеня 0, то залишається n-2 вершин з попарно різними степенями від 1 до n-3, а це неможливо. Так само неможливо, що за двох вершин степеня n-1 решта n-2 вершин мають попарно різні степені від 2 до n-2.
2 Розв’язування задач на побудову графів за їх матрицями суміжності, інцедентності, списком пар
Задача 7. Зобразити неорієнтовані графи за матрицями суміжності
а)
;
б)
Розв’язання
а)
Задача 8. Зобразити орієнтовані графи за матрицями суміжності.
а)
;
б)
