Інформативний диктант 1.Графом називається сукупність … 2.Вершини, що сполучаються між собою ребром, називаються … 3.Вершина степеня 0 називається …. 4.Граф, який не має жодного циклу, називається … 5.Кілька дерев, які не мають спільних вершин, називаються … 6.Якщо ж у графі вказана ще й «вага» кожного ребра, то такий граф – …

Тема: Способи представлення графів Мета: навчальна: –розповісти учням про способи представлення графів; –охарактеризувати три основні способи подання графів; –навчати використовувати основні поняття теорії графів при розвязуванні задач. розвивальна: –розвивати самостійне творче ставлення до роботи; –розвивати системність мислення; –формувати навички представлення графів мовою програмування. виховна: –виховувати в учнів інформаційну культуру під час роботи з компютером; –формувати інтерес до теорії графів; –виховувати наполегливість бажання доводити розпочату справу до кінця.

Способи представлення графів у вигляді матриці суміжності; у вигляді списку ребер; у вигляді списку суміжних вершин.

Матриця суміжності Матриця суміжності – це квадратна таблиця (масив) розмірністю NxN, де N – кількість вершин у графі.

Матриця суміжності

Список ребер Список ребер – це структура, де зберігаються номери кінцевих вершин та вага кожного ребра

Список ребер

Список суміжних вершин Список суміжних вершин – це спосіб представлення графів, при якому кожен рядок структури містить перелік номерів суміжних вершин та вагу ребер, до них інцидентних.

Список суміжних вершин /30 5/7 1/30 2/12 2/7 1/8 6/8 4/12 4/2 3/2 4/5 3/7 6/7 5/5 4/12 6/12

Граф з n вершинами

Двоорієнтований граф

Незважений орграф, у якому присутні ребра-петлі

Зважений орграф

Ланцюжок запитань 1.Який вигляд матиме матриця суміжності графу, який складається з трьох ізольованих вершин? 2.Чи можна задати у вигляді списку суміжних вершин граф, який складається з однієї ізольованої вершини? 3.Чи симетричною буде матриця суміжності орієнтованого графі? 4.У якому випадку матриця суміжності графа міститиме відмінні від нуля числа на діагоналі?

Запис мовою програмування

Повідомлення домашнього завдання 1.Вивчити теоретичний матеріал до уроку. 2.Зобразити граф графічно та у вигляді матриці суміжності, списку ребер чи списку суміжних вершин для задачі 36. (Із посібника В.І. Мельник Інформатика. Олімпіадні завдання з розвязаннями)