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

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

«Основні поняття теорії графів»

Мета.  

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

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

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

План

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

Хід уроку

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

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

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

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

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

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

1.          Побудувати граф із 3 вершин: ізольованих вершин немає, вершина 1 містить петлю.

2.          Дано дві вершини графа. Побудувати нуль-гаф з даними вершинами.

3.          Дано повний граф із 5 вершинами. Побудувати даний граф, обчислити кількість його ребер.

4.          Знайти кількість ребер у повного графа з 8 вершинами.

5.          Зобразити плоский та просторовий граф із 4 вершинами.

6.          Знайти степінь кожної вершини даного графа.

7.          Для заданого графа записати прості цикли для вершини А та довжину шляху в кожному з них.

8.      В даному орієнтованому графі знайти степінь кожної вершини.

9.      В даному орієнтованому графі для вершини 1 записати можливі орієнтовані цикли

10.  Задано 5 вершин. Зобразити довільно: мультиграф, псевдо граф, звичаний граф, орграф, змішаний граф, орієнтований зважений граф.

11.  Зобразити Ейлерів граф.

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

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

• Повторити “Основні поняття теорії графів”.