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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ВІДОКРЕМЛЕНИЙ СТРУКТУРНИЙ ПІДРОЗДІЛ

«РОМЕНСЬКИЙ ФАХОВИЙ КОЛЕДЖ КИЇВСЬКОГО

НАЦІОНАЛЬНОГО ЕКОНОМІЧНОГО УНІВЕРСИТЕТУ 

ІМЕНІ ВАДИМА ГЕТЬМАНА»

 

 

 

 

ПЛАН-КОНСПЕКТ

ВІДКРИТОГО ЗАНЯТТЯ

З НАВЧАЛЬНОЇ ДИСЦИПЛІНИ

 «ДИСКРЕТНА МАТЕМАТИКА»

 

 

Спеціальність 123 Комп`ютерна інженерія

 

 

 

 

 

 

 

Підготувала  

викладач Антоніна РУДЕНКО  Розглянуто на засіданні циклової комісії комп`ютерної  інженерії Протокол №4  від  20 жовтня 2025 р.

Голова циклової комісії_________Юлія БАЛЯБА

 

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ВІДОКРЕМЛЕНИЙ СТРУКТУРНИЙ ПІДРОЗДІЛ

«РОМЕНСЬКИЙ ФАХОВИЙ КОЛЕДЖ КИЇВСЬКОГО

НАЦІОНАЛЬНОГО ЕКОНОМІЧНОГО УНІВЕРСИТЕТУ 

ІМЕНІ ВАДИМА ГЕТЬМАНА»

НАВЧАЛЬНО-МЕТОДИЧНА КАРТКА (ПЛАН) ЗАНЯТТЯ № 19

Навчальна дисципліна: Дискретна математика

Група: К-3-1

Дата: 03.11.2025 р.

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

Навчальна: сформувати в студентів знання про основні поняття теорії графів: визначення графів, елементи графа, класифікацію графів за різними ознаками. Ознайомити з методами побудови графів та поняттям метрики на графах. Навчити розв’язувати типові задачі, пов’язані з обчисленням метричних характеристик.

Розвивальна: розвивати логічне, аналітичне та просторове мислення студентів; уміння аналізувати структури зв’язків, будувати графи за умовою задачі, здійснювати порівняння та узагальнення. Формувати навички використання графічних моделей у практичних ситуаціях.

Виховна: виховувати уважність, відповідальність, наполегливість у розв’язанні навчальних завдань; формувати інтерес до математичного моделювання та його застосувань у професійній діяльності; сприяти розвитку колективної роботи й культури наукового мислення.

Забезпечення заняття:

Наочність: матеріал з презентації з теми заняття, програмне забезпечення

Python, інтерактивний сервіс linoit  

Роздатковий матеріал: опорний конспект з теми «Визначення графів. Класифікація графів. Методи побудови графів. Метрика на графах», картки  графів.

ТНЗ: мультимедійний комплекс Література:

1.     Бардачов Ю.М. Дискретна математика: Підручник  /  Ю.М. Бардачов, Н.А. Соколова, В.Є. Ходаков; за ред. В.Є. Ходакова. – К.: Вища шк., 2007. – 383 с.

2.     Бондарчук Ю. В., Олійник Б. В. Основи дискретної математики: – К.: «КиєвоМогилянська академія», 2009. – 159 с.

3.     Трохимчук Р. М. Дискретна математика. – К.: Персонал, 2010. – 525 с.

 

ХІД ЗАНЯТТЯ

І. Організаційна частина заняття.

Привітання. Облік присутніх, налаштування на співпрацю і взаєморозуміння.

Епіграфом заняття буде вислів «Граф — це спосіб побачити порядок у хаосі зв’язків». Тож сьогодні на занятті спробуємо переконатися в цьому, бажаю плідної праці, творчого мислення, уваги та вдалих оцінок.

ІІ. Повідомлення теми, мети, та основних завдань заняття. Мотивація навчальної діяльності.

У сучасному світі майже всі процеси можна подати у вигляді взаємопов’язаних елементів — від доріг між містами до зв’язків між користувачами в соціальних мережах. Саме такі системи зручно описувати за допомогою графів.

Знання теорії графів допомагає:

✓  розуміти принципи роботи комп’ютерних мереж, Інтернету, навігаційних систем;

✓  розв’язувати практичні задачі оптимізації — наприклад, знаходити найкоротший шлях або мінімальні витрати;

✓  створювати ефективні алгоритми в програмуванні, штучному інтелекті, аналізі даних;

✓  мислити структуровано та логічно, що є важливою навичкою для будь-якого фахівця технічного профілю.

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

 

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

Фронтальне опитування

Перш ніж розпочати вивчення нової теми, давайте пригадаємо раніше вивчений матеріал.

1.                 Що таке множина? Наведіть приклади. 

2.                 Якими способами можна задавати множини?

3.                 Що таке об’єднання, перетин, різниця та доповнення множин?

4.                 Що таке універсальна множина?

5.                 Що таке відношення між множинами?

6.                 Які типи відношень існують (бінарні, рефлексивні, симетричні, транзитивні, антисиметричні)?

7.                 Як зображають відношення графічно (матриця, граф, список пар)?

IV Вивчення нового матеріалу.

План  

1.   Графи. Основні поняття і визначення

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

3.   Способи представлення  графів

4.   Метрика на графах

          4.1. Графи. Основні поняття і визначення

Графічне подання рішення різних прикладних задач нам добре відомо. До графічних подань у широкому змісті можуть бути віднесені малюнки, креслення, графіки, діаграми, блок-схеми і т.п. З їхньою допомогою наочно ілюструються залежності процесів і явищ, логічні, структурні, причинно-наслідкові і інші взаємозв'язки. Однак теорія графів має свою власну проблематику. У дискретній математиці граф є найважливішим математичним поняттям. На основі теорії графів будуються моделі різноманітних задач, таких як маршрутизації, розподілу ресурсів, дискретної оптимізації, сіткового планування і керування, аналізу і проектування організаційних структур, аналізу процесу їх функціонування і багато іншого.

 Визначення.Графом G називається сукупність двох множин V точок і E ліній, між якими визначене відношення інцидентності, причому, кожен елемент

eE інцидентний рівно двом елементам v,vV . Елементи множини V називаються вершинами, а елементи множини E - ребрами графа. Вершини і ребра графа називаються його елементами, тому найчастіше пишуть vG і eG

         Визначення. Якщо ребро e з'єднує вершини v, v, тоді вони є для нього кінцевими точками і називаються суміжними вершинами. Два ребра називаються суміжними, якщо вони інцидентні до загальної вершини.

 Визначення. Напрямлені ребра називають орієнтованими ребрами або дугами, перша по черзі вершина називається початком дуги, а друга – її кінцем. Граф, що містить напрямлені ребра, називається орієнтованим графом або орграфом (рис.1, а), а граф, що не містить напрямлених ребер – неорієнтованим або н-графом (рис.1, б).  

                                                   

                                 (а)                                                   (б)

Рис.2.

 Визначення. Ребро, що з'єднує деяку вершину саму із собою, називається петлею (рис.2,а).

 Визначення. Ребра, інцидентні до однієї і тієї ж вершини, називаються кратними (рис.2,б). Граф, що містить кратні ребра, називається мультиграфом, а граф, що містить кратні ребра і петлі – псевдографом.

 Визначення. Граф називається кінцевим, якщо множина його вершин і ребер звичайна.   Множина ребер графа може бути порожньою (рис.2,в). Такий граф називається порожній.

          

                                     

                  (а)                                    (б)                                         (в)

Рис.2.

 Визначення. Граф без петель і кратних ребер називається повним, якщо кожна пара його вершин з'єднана ребром. Повний граф з n вершинами позначається K_n .

                   Приклад. На рис.3 зображені повні графи K₂, K₃, K₄, K₅ і K₆ відповідно:

                                 

Рис.3.

          

4.2. Степені вершин графа

Визначення. Степенем вершини v (degv) називається кількість ребер, інцидентних цій вершині. Вершина степеня 0 називається ізольованою. У графі з петлями петля дає внесок в 2 одиниці у степінь вершини.

          Приклад. Визначити степені вершин графа, зображеного на рис.4.

 

Рис.4.

 

Рішення: degv₁ = 2; degv₂ =2; degv₃ = 3; degv₄ =4; degv₅ =3; degv₆ =4.

degv = 2+ 2+3+ 4+3+ 4 =18 = 29 = 2m. У розглянутому графі дев’ять

vG ребер, а вершин непарного степеня дві: v₃; v₅.

 Визначення. Для орієнтованого графа визначаються дві степені вершин: degv - кількість ребер, що виходять із вершини v і degv - кількість ребер, що входять у вершину v . Петля дає внесок по одиниці в обидві степені.

 В орграфі суми степенів всіх вершин degv і degv рівні між собою і дорівнюють кількості ребер m цього графа: degv = degv = m.

                                                                                                                        vG                               vG

Приклад. Визначити степені вершин орграфа, зображеного на рис.5.

 

Рис.5.

          Рішення:

 dega =1, degb = 2; degc = 3; degd = 2; dege = 2;  dega = 2, degb =1; degc = 2; degd = 2; dege =3;

degv =1+ 2+3+ 2+ 2 =10 = degv == 2+1+ 2+ 2+3 =10 = m.

                 vG                                                                                                                   vG

 

 

4.3. Способи представлення  графів

            Матриця інцидентності _ij – це матриця розміром mn, де

вертикально вказуються вершини i =1,n, а горизонтально – ребра j =1,m. На перетині i -того і j -того рядків число _ij дорівнює:

          а) у випадку неорієнтованого графа

                                                      1, якщо ребро e інцидентно вершині v ;_{i         j}

_ij = 0, якщо ребро e не інцидентно вершині v ;_{i      j} , якщо ребро e_i − петля( 0 і      1 .)

          б) у випадку орієнтованого графа

−1, якщо v_i − початок ребра e ;_j

^{ij =} ^10,,якщо vякщо вони не інцидентні;_i − кінець ребра e ;_j                    



_, якщо e_j − петля, а v_i −інцидентна їй вершина.

           Матриця суміжності   -  це  квадратна  матриця  розміром nn,   де  

вертикально і горизонтально вказуються вершини графа i =1,n і j =1,n. На перетинанні i -того і j -того рядків елемент дорівнює:

-   числу ребер, що з'єднують ці вершини у випадку неорієнтованого графа;  - числу ребер з початком в i -тій вершині і кінцем в j -тій вершині у випадку орієнтованого графа.

 Список ребер графа – це таблиця, що складається із трьох рядків. У першому перераховані всі ребра; у другому і третьому – інцидентні їм вершини:

-   у   випадку неорієнтованого графа порядок вершин у рядку довільний;

-   у випадку орієнтованого графа першою записується вершина, де починається ребро (другий рядок); вершина, де закінчується ребро, записується у третій рядок.

 Якщо графи рівні, то їх матриці суміжності і інцидентності, а також список ребер, однакові.  

Приклад. Задати матрицями інцидентності і суміжності, а також списком ребер, неорієнтований граф, зображений на рис. 6.

 

 

 

Рис. 6.

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

1 2 3 4 5 6 7 8 9 10 a 1 0 1 0 0 0 0 0 0 0 b 1 1 0 0 0 0 0 0 0 0 c 0 1 1 1 1 0 1 0 0 0

a b c d e f g a 0 1 1 0 0 0 0 b 1 0 1 0 0 0 0 c 1 1 0 2 1 0 0

d 0 0        0        1        1        2        0        1        0        0        d        0        0        2        1        1        0        0 e 0   0        0        0        0        0        1        1        1        1        e        0        0        1        1        0        1        1 f 0   0        0        0        0        0        0        0        1        0        f 0      0        0        0        1        0        0 g 0 0        0        0        0        0        0        0        0        1        g        0        0        0        0        1        0        0

= 2.

Список ребер

Ребро		1	2	3	4	5	6	7	8	9	10
Вершини	початок	a	b	a	c	c	d	c	d	e	e
	кінець	b	c	c	d	d	d	e	e	f	g

Приклад. Задати матрицями інцидентності, суміжності, списком ребер орієнтований граф, зображений на рис. 7

 

 

Рис. 7

Матриця інцидентності                              

	1	2		3	4	5	6	7	8	9	10
a	2	−1		1	0	0	0	0	0	0	0
b	0	1		−1	−1	0	0	0	0	0	0
c	0	0		0	1	−1	−1	0	0	0	0
d	0	0		0	0	1	0	−1	1	0	0
e	0	0		0	0	0	1	1	0	1	0
f	0	0		0	0	0	0	0	−1	−1	−1
g	0	0		0	0	0	0	0	0	0	1

 

 

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

b                                                          c               d               e                f                     g

a	1	1		0		0		0		0		0
b	1	0		1		0		0		0		0
c	0	0		0		1		1		0		0
d	0	0		0		0		1		0		0
e	0	0		0		0		0		0		0
f	0	0		0		1		1		0		1
g	0	0		0		0		0		0		0

 

Список ребер

Ребро	1	2	3	4	5	6		7	8	9	10
початок Вершини	a	a	b	b	c	c		d	f	f	f
кінець	a	b	a	c	d	e		e	d	e	g

 

4.4. Метрика на графах

Відстанню d(v,v) між вершинами v і v графа G називається мінімальна довжина простого ланцюга з початком у вершині v і кінцем у вершині v. Якщо вершини v і v не з'єднані ланцюгом, тобто належать  різним компонентам, то покладається, що d(v,v)= .

         У зв'язному графі G відстань між вершинами задовольняє наступним умовам:

1)   v,vG, d(v,v)0 і d(v,v)=0 тоді і тільки тоді, коли v = v;

2)   v,vG, d(v,v)= d(v,v);

3)   v,v,vG, d(v,v) d(v,v)+d(v,v).

Функція d(v,v), що задовольняє трьом перерахованим умовам, називається метрикою графа.

Центром графа називається вершина, від якої максимальна з відстаней до інших вершин була б мінімальною.

Периферійною точкою графа називається вершина, від якої максимальна з відстаней до інших вершин була б максимальна.

Максимальна відстань від центра графа G до його вершин називається радіусом графа r(G)

Визначення. Відхилення центра називається радіусом графа r(G), а відхилення периферійної точки – діаметром графа D(G).

 Алгоритм знаходження відстаней від даної вершини v₀ до інших вершин графа G :

1)    позначаємо через A₀ =v₀;

2)    позначаємо індексом 0 всі вершини, суміжні з вершиною v₀, виписуємо множину A₁ всіх цих вершин з їхніми позначками;

3)    кожну вершину, що не належить множині A₀  A₁ і суміжну з кожною з вершин, що належать множині A₁, позначаємо індексом v; виписуємо множину A₂ всіх цих вершин з їхніми позначками …;

n) повторюємо описану процедуру доти, поки множина непомічених вершин не виявиться порожньою.

Приклад. Визначити відстань від вершини 7 (для зручності запису позначимо вершини графа арабськими цифрами) до всіх вершин графа G , зображеного на рис 8.

 

Рис. 8

 

         Рішення. Згідно алгоритму відстань від вершини 7 будемо шукати в такий спосіб:

        1) A₀ =7;  2) A₁ =1₇,3₇,6₇;  3) A₂ ⁼2_1,3,5_3,6,4₃.

          

Більше непомічених вершин немає. Тобто відстані від вершини 7 до кожної з вершин графа такі:  d(7,1)= d(7,3)= d(7,6)=1; d(7,2)= d(7,4)= d(7,5)= 2.

 Для визначення центра і радіуса графа необхідно побудувати для нього матрицю відстаней A, кожен елемент якої a_ij описує відстань між вершинами  i    і   j   графа  G ,  тобто  a_ij =d(v_i ,v_j ).  Очевидно,  що  матриця  відстаней  A симетрична щодо головної діагоналі (елементи якої дорівнюють нулю, тому що d(v_i ,v_i )= 0).

Приклад. Визначити центр, периферійні вершини, радіус і діаметр графа G , зображеного на рис. 9.

 

Рис. 9.

Матриця відстаней графа G має вигляд.

	1	2	3	4	5		6	7		8	9	l	r
1 2 3 4 5 6 7 8 9	0 1 1 2 3 4 4 4 4	1 0 1 1 2 3 3 3 3	1 1 0 1 2 3 3 3 3	2 1 1 0 1 2 2 2 2	3 2 2 1 0 1 1 1 1		4 3 3 2 1 0 1 1 2	4 3 3 2 1 1 0 1 1		4 3 3 2 1 1 1 0 1	4 3 3 2 1 2 1 1 0	4
												3
												3
												2	2
												3
												4
												4
												4
												4

 

 

Знайдемо максимальну відстань від кожної з вершин графа l(v_i ) як maxa_ij :

1 j9 l(1)= 4; l(2)= 3; l(3)=3; l(4)= 2; l(5)=3; l(6)= 4;l(7)= 4 ; l(8)= 4; l(9)= 4.

Отже, згідно з визначенням, центром графа є вершина 4; периферійні вершини – 1, 6, 7, 8, 9. Радіус графа r(G)= 2, а діаметр графа D(G)= 4.

V.       Узагальнення та систематизація вивченого матеріалу

5.1 Контрольні запитання

Графи. Основні поняття і визначення

1.     Що таке граф?

2.     Які бувають види графів?

3.     Що таке вершини та ребра графа?

4.     Як визначають суміжні вершини та інцидентні ребра?

5.     Чим відрізняється орієнтований граф від неорієнтованого?

6.     Що таке петля та кратні ребра?

7.     Які приклади графів можна зустріти в реальному житті?

Степені вершин графа

1.     Що таке степінь вершини в неорієнтованому графі?

2.     Як знайти вершини з парними та непарними степенями?

Способи представлення графів

1.     Які основні способи представлення графів існують?

2.     Що таке матриця суміжності?

3.     Що таке матриця інцидентності?

Метрика на графах

1.     Що таке відстань між вершинами графа?

2.     Як визначається найкоротший шлях у графі?

3.     Що таке діаметр графа?

4.     Що таке радіус графа та центр графа?

5.     Яке практичне значення мають метричні характеристики графів?

Виконати тестування 

 

 

VI.   Підбиття підсумків заняття та оцінювання знань  студентів

Повернімося до поставленої на початку заняття мети. Чи досягли ми її?

Чи все зрозуміли?

Отже, теорія графів — це розділ математики, що вивчає властивості та закономірності графів, тобто структур, які складаються з вершин (точок) і ребер (зв’язків) між ними. 

Теорія графів дає змогу моделювати та аналізувати складні системи зв’язків — від соціальних мереж до транспортних маршрутів. Вона лежить в основі сучасних алгоритмів пошуку, оптимізації та аналізу даних.

Сфера застосування графів різноманітна:

✓  у комп’ютерних науках (мережі, алгоритми, бази даних, штучний інтелект);

✓  у транспорті (планування маршрутів, навігація);

✓  у біології (моделювання генетичних або нейронних зв’язків);

✓  у соціології (аналіз соціальних мереж);

✓  у економіці (оптимізація витрат і ресурсів).

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

Пропоную, дописати     декілька      речень         і         залишити    свої   враження    на  інтерактивному сервісі linoit.com 

1.     було цікаво…

2.     було важко…

3.     були виконані  завдання…

4.     я зрозумів, що…

5.     я навчився…

6.     у мене вийшло …

7.     мене здивувало…

  

VII. Пояснення домашнього завдання

1.     Опрацювати лекційний матеріал

[1, с. 243-251]

[2, с. 129-135]

2.     Визначити степені вершин графів:

          

 

          (а)                         (б)                        (в)                                (г)

 

              (д)                              (е)                          (ж)                        (з)

 

3.Графічно розв`язати задачу

  Передісторія: «Зниклий мережевий маршрут»

В одному коледжі сталася загадкова подія. У навчальному корпусі перестала працювати комп’ютерна мережа — сервер не може з’єднатися з аудиторіями. Відомо лише, що система маршрутизації була побудована за принципами теорії графів, але хтось «пошкодив» її структуру, видаливши кілька вузлів і ребер.

  Мета детективного розслідування

1.     Засвоїти основні поняття теорії графів: вершина, ребро, степінь вершини, шлях, цикл, зв’язність.

2.     Навчитися будувати й аналізувати графи.

3.     Розв’язувати практичні задачі з використанням графових структур.

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

  Хід «розслідування»

Завдання: Розшифрувати повідомлення адміністратора:

«У нашій мережі є 6 вузлів і 8 з’єднань. Але після збою залишилося лише 5 вузлів і 5 ребер»

Питання до студентів:

–   Який тип графа могла утворювати мережа спочатку?

–   Як визначити, чи залишився граф зв’язним після втрати частини елементів? Доказ:

Студенти створюють оригінальний граф (G) із 6 вершинами. Потім вилучають одну вершину та три ребра, аналізуючи, чи залишився граф зв’язним.

Розв’язавши, студенти роблять висновок:

Якщо граф після вилучення елементів не містить ізольованих вершин і між будь-якими двома вершинами існує шлях — мережа ще функціонує.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ДОДАТОК 1  Що таке граф?

A)  Набір чисел

B)   Система вершин і ребер, що їх з’єднують

C)   Таблиця даних

D)  Алгоритм обчислень

  Правильна відповідь: B

Як називаються вершини, з’єднані спільним ребром?

A)  Суміжні

B)   Віддалені

C)   Інцидентні

D)  Ізольовані

  Правильна відповідь: A

Що характеризує орієнтований граф?

A)  Ребра не мають напрямку

B)   Ребра мають напрямок

C)   Граф не має вершин

D)  Ребра утворюють замкнене коло

  Правильна відповідь: B

Як називається граф, у якому будь-які дві вершини з’єднані шляхом?

A)  Повний

B)   Зв’язний

C)   Орієнтований

D)  Ізольований

  Правильна відповідь: B

Що таке степінь вершини в неорієнтованому графі?

A)  Кількість ребер у графі

B)   Кількість вершин, що з’єднані з даною

C)   Кількість ребер, інцидентних вершині

D)  Довжина шляху між вершинами

  Правильна відповідь: C

Що показує вхідна степінь вершини в орієнтованому графі?

A)  Кількість вихідних дуг

B)   Кількість ребер, що входять у вершину

C)   Кількість сусідніх вершин D) Кількість циклів у графі

  Правильна відповідь: B

Яке співвідношення існує між сумою степенів усіх вершин і кількістю ребер у неорієнтованому графі?

A)  Σdeg(v) = m

B)   Σdeg(v) = 2m

C)   Σdeg(v) = m/2

D)  Σdeg(v) = n

  Правильна відповідь: B

Які вершини називають ізольованими?

A)  Ті, що мають степінь 1

B)   Ті, що мають нульовий степінь

C)   Ті, що мають петлі

D)  Ті, що з’єднані з усіма іншими

  Правильна відповідь: B

Що таке матриця суміжності графа?

A)  Таблиця з координатами вершин

B)   Таблиця, що показує зв’язки між вершинами

C)   Таблиця із степенями вершин

D)  Таблиця із довжинами шляхів

  Правильна відповідь: B

Який елемент матриці суміжності дорівнює 1?

A)  Якщо вершини не суміжні

B)   Якщо вершини суміжні

C)   Якщо вершини ізольовані

D)  Якщо вершини мають петлі

  Правильна відповідь: B

Що містить матриця інцидентності?

A)  Інформацію про суміжність вершин

B)   Відомості про зв’язок між вершинами та ребрами

C)   Координати вершин

D)  Список степенів

  Правильна відповідь: B

Як називається найбільша відстань між будь-якими двома вершинами графа? A) Радіус

B)   Діаметр

C)   Центр

D)  Ексцентриситет

  Правильна відповідь: B

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ДОДАТОК 2