ЗМІСТ ПРАКТИЧНОГО ЗАНЯТТЯ. ЗАКРІПЛЕННЯ ВИВЧЕНОГО І ОЦІНЮВАННЯ РІВНЯ ЗНАНЬ. ДОМАШНЄ ЗАВДАННЯ

 

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. Зобразити орієнтовані графи за матрицями суміжності.

а) ;     б)

 

ЗАКРІПЛЕННЯ ВИВЧЕНОГО І ОЦІНЮВАННЯ РІВНЯ ЗНАНЬ

 

Оцінювання знань студентів здійснюється шляхом оцінювання правильності відповідей, правильності розв’язування задач, активності на занятті.

ДОМАШНЄ ЗАВДАННЯ

 

Задача 1.  Задати графи задачі 7 списком пар.

Задача 2. Нехай V={a,b,c,d,e}. Граф G =(V,E ) задано за допомогою матриці суміжності A.

а) A= ;          б) A= ;

Визначити множину ребер E графа G. Побудувати діаграму та матрицю інцидентності графа G.

 

 

ВИКЛАДАЧ – Данилова В.А.

ПРАКТИЧНЕ ЗАНЯТТЯ №10

ТЕМА:   Використання теорії дерев (2 год.)

МЕТА:

навчальна: вчити студентів визначати різні кореневі дерева в одному й тому ж графі, визначати висоту дерева, виконувати обхід дерев;

розвиваюча: розвивати логічне мислення;      

виховна: виховувати інтерес до комп’ютерної математики.       

ОБЛАДНАННЯ: олівці, лінійки

ПЛАН

1 Розв’язування задач на  зображення кореневих дерев

2 Розв’язування задач на впорядкування вершин дерев

⇐ Предыдущая12

Поделиться: