Урок 08                                                                                                      Інформатика 11 (АП)

Практична робота № 2

«Способи подання графів»

Мета.  

Навчальна. навчитися представляти графи матрицею суміжності та списком суміжних вершин.

Розвиваюча. Розвивати логічне та алгоритмічне мислення, вміння застосовувати набуті знання.

Виховна. Виховувати наполегливість, самостійність, культуру оформлення

План

• Актуалізація опорних знань.
• ТБ.
• Практична робота.
• Приклади.
• Підсумки  уроку.
• Домашнє завдання.

Хід уроку

1. Актуалізація опорних знань.

1.  Що таке граф? З яких елементів він складається?
2. Які вершини називають інцедентними ребрам?
3. Які вершини називають суміжними?
4. Які вершини називають ізольованими?
5. Які вершини графа називають зв’язаними?
6. Що називають циклом у графі?
7. Який граф називають деревом, а який – лісом?
8. Який граф називають орієнтованим, або орграфом?
9. Який граф називають зваженим?
10. Які способи представлення графів ви знаєте?
11. В чому полягає спосіб представлення графа матрицею суміжності?
12. В чому полягає спосіб представлення графа списом суміжних вершин?

2. Інструктаж БЖД.

Інструктаж з ТБ при роботі з ПК та в комп’ютерному класі.

3. Практична робота № 1 «Основні поняття теорії графів»

Завдання до практичної роботи.

1.          Подати заданий граф матрицею суміжності та списком суміжних вершин:

2.          Подати заданий граф матрицею суміжності та списком суміжних вершин:

3.      Записати матрицю суміжності для даного графа та списком суміжних вершин:

 4.          Розробити і реалізувати у вигляді програми алгоритм, який за заданими вхідними даними, що описують деякий граф (кількістю вершин, кількістю ребер і пар вершин, які зада­ють ці ребра), створює відповідну матрицю суміжності.

І в. Виконати завдання  для неорієнтованого незваженого гра­фа, що не має петель та з кількістю вершин N = 5, вивівши результат виконання програми на екран.

ІІ в. Виконати завдання  для неорієнтованого зваженого графа, що не має петель та з кількістю вершин N=5, вивівши ре­зультат виконання програми на екран.

4. Підсумки уроку.

5. Домашнє завдання.

• Повторити “Способи представлення графів”.