Презентація на тему "Визначення графів. Класифікація графів. Методи побудови графів. Метрика на графах"

Тема: Визначення графів. Класифікація графів. Методи побудови графів. Метрика на графах. Підготувала викладач ВСП «РФК КНЕУ ім. В. Гетьмана. Антоніна РУДЕНКО «Граф — це спосіб побачити порядок у хаосі зв’язків»

План1. Графи. Основні поняття і визначення2. Степені вершин графа3. Способи представлення графів4. Метрика на графах

Необхідно знайти такий маршрут через місто, щоб пройти всі сім мостів і кожним мостом пройти рівно один раз. На острів не можна було потрапити інакше як через міст. Ейлер довів, що розв'язку не існує. Задача про 7 мостів

1. Графи. Основні поняття і визначення. Граф G=(V,E) – це сукупність непорожньої множини вершин V та множини ребер E. Неорієнтований граф - це граф, ребра якого не мають напрям. Орієнтований граф (орграф) - це граф, ребра якого мають напрям.

Звичайний граф з n вершинами, будь-яка пара вершин якого з'єднана ребром, називається повним і позначається Kn. Кількість ребер в повному графі дорівнює𝑚=𝑛𝑛−12 Граф, який може бути зображено на площині без перетину ребер, називається планарним.

Моделі з погляду теорії графів однаковіПетля Кратні ребра Порожній граф

Мультиграф – це граф із кратними ребрами. Псевдограф – це граф з петлями. Граф, що не містить петель і кратних ребер, називається простим графом

Кратні ребра. V1 V2 V3 V4 V5 V6 ПетляІзольована вершина. Суміжні вершини. Висяче ребро. Висяча вершина. V7

2. Cтепені вершин графа

Визначити суму степенів вершин неорієнтованого графаdeg(V1) = 4deg(V2) = 4deg(V3) = 2deg(V4) = 4deg(V5) = 3deg(V6) = 0deg(V7) = 1 Сума степенів вершин графа = 2m. V1 V2 V3 V4 V5 V6 V7

Визначити суму степенів вершин орієнтованого графа

Графічне задання Матриця суміжності Матриця інцидентності Список ребер 3. Способи представлення графів

Матриця суміжності орієнтованого графа

Матриця інцидентності орієнтованого графа

Таблиця ребер орієнтованого графа

4. Метрика на графах. Маршрут, усі ребра якого різні, називається ланцюгом. Ланцюг, що не перетинає себе, тобто не має вершин, що повторюються, називається простим.

Визначити центр, радіус і периферійні вершини графа

Домашнє завдання1. Опрацювати лекційний матеріал[1, с. 243-251][2, с. 129-135]2. Визначити степені вершин графів. Графічно розв’язати задачу: В одному коледжі сталася загадкова подія. У навчальному корпусі перестала працювати комп’ютерна мережа — сервер не може з’єднатися з аудиторіями. Відомо лише, що система маршрутизації була побудована за принципами теорії графів, але хтось «пошкодив» її структуру, видаливши кілька вузлів і ребер. Завдання: Розшифрувати повідомлення адміністратора:«У нашій мережі є 6 вузлів і 8 з’єднань. Але після збою залишилося лише 5 вузлів і 5 ребер»– Який тип графа могла утворювати мережа спочатку?– Як визначити, чи залишився граф зв’язним після втрати частини елементів?Побудувати граф.