Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема: Основні означення та поняття теорії графів. Орієнтовані
та неорієнтовані графи. Лема про рукостискання.
Мета: ввести поняття графу, ознайомити з його складовими та
видами; сформувати вміння застосовувати лему про
рукостискання для визначення степенів вершин та
кількості ребер графів.
План
1. Графи. їх класифікація та види.
2. Лема про рукостискання. Визначення степенів
вершин орієнтованого та неорієнтованого графів.
Вступ.
Теорія графів є однією з істотних частин математичного апарату інформатики та кібернетики. У термінах теорії графів формулюють велику кількість задач пов’язаних з дискретними об’єктами. Такі задачі виникають під час проектування інтегральних схем, схем керування, у дослідженні автоматів, в економіці, статистиці, теорії розкладів і дискретній оптимізації.
Термін „ граф ” уперше з’явився у книзі видатного угорського математика Д. Кеніга 1936, хоча перші задачі теорії графів пов’язані ще з іменем Ейлера (18 ст.), який у 1736 р. не тільки розв’язав на той час головоломку про кенігзберські мости, а й знайшов критерій існування в графі спеціального маршруту (ейлеревого циклу). Довгий час цей результат залишався єдиним результатом теорії графів, і лише в середині 19ст., зусиллями Кіргофа і Келлі були одержані нові результати в теорії графів. Приблизно в цей час виникла знаменита проблема чотирьох фарб.
Графи. Їх класифікація та види.
Означення:
Графом G=(V,E) називається сукупність двох множин: вершин V і ребер E, між якими встановлено відношення інцидентності -кожне ребро eE є інцидентне двом вершинам v; vV, які воно з’єднує (вершина v і ребро e називається інцидентними,якщо v є кінцем ребра e).
Простим графом називають пару G=(V,E) – де V – множина вершин, E – множина ребер або це граф неорієнтований без кратних ребер і без петель.
ребер V={}, а множина ребер
E={{},{,},{,}{}}/
Ребро, що з’єднує 2 вершини, може мати напрям від однієї вершини до другої і тоді воно називається напрямленим або орієнтованим, або дугою і зображується стрілкою, яка напрямлена від вершини, що називається початком до вершини, що називається кінцем.
Граф, що містить орієнтовані або направлені ребра (дуги) з початком називається орієнтованим (орграфом), а не напрямлений (неорієнтований або неограф) (мал.1).
( мал. )
Означення:
Якщо ребро е з’єднує вершини , тоді вони є для нього кінцевими точками і називаються суміжними вершинами. Два ребра називаються суміжними, якщо вони є інцидентні до загальної вершини.
Так, несуттєво є довжина, кривизна ребер, розташування вершин, принциповим є відношення інцидентності.
Приклад 1. Моделі а,б,в є однакові(мал.2).
(мал. )
У простому графі дану пару вершин може з’єднувати не більш ніж одне ребро. У деяких випадках розглядаються графи, у яких дві вершини можна з’єднати більше ніж одним ребром.
Ребра, які з’єднують одну й ту саму пару вершин називаються кратними (паралельними) ребрами.
Означення:
Ребро, що з’єднує деяку вершину саму із собою називається петлею.
Граф, що містить кратні ребра, називається мультиграфом, а граф, що містить кратні ребра і петлі називається псевдографом.
(мал. )
Множина ребер графа може бути порожньою. Такий граф називається порожнім (пустим).
Псевдограф — це найзагальніший тип неорієнтованого графа, бо може містити петлі і кратні ребра .
Мультиграф — це неорієнтований граф, який може містити кратні ребра, але не може містити петель.
Граф без петель і кратних ребер називається повним, якщо кожна пара його вершин з’єднана ребром. Повний граф з n вершинами позначається .
Приклад 1. На малюнку зображені повні графи .
Граф називається кінцевим, якщо множина його вершин і ребер звичайна.
Вершини u та v у неорієнтованого графа G називають суміжними, якщо {u,v}ребром. Два ребра суміжні, якщо вони мають спільний кінець. Вершина v і ребро e називають інцидентними, якщо v є кінцем ребра е.
Означення:
Доповненнням графа G називається граф, що має ті ж вершини, що і граф G і тільки ті ребра, які необхідно додати до графа G, щоб він став повним.
Приклад 2. Доповнити до графа G на (*) є граф (**). Повний граф (***) (мал.4).
(мал. )
Означення:
Степінь вершини v (deg(v)) – це кількість ребер інцидент них цій вершині, причому петлю враховують двічі.
Якщо deg(v)=0, то вершину v називають ізольованою.
Якщо deg(v)=1, то вершину v називають висячою.
Лема про рукостискання. Визначення степенів вершин орієнтованого та неорієнтованого графів.
2. Теорема.
Нехай G=(V,E) неорієнтований граф, що має m ребер. Тоді
(сума степенів вершин графа завжди парна).
У будь-якому графі кількість вершин непарного степеня завжди парна.
Приклад 3. Для неорієнтованого графа (мал.5) степені вершин такі: , , , , , . Отже, – ізольована, – висяча.
(мал. )
Приклад 4. Визначити степені вершин графа зображеного на малюнку 6.
( мал. )
У розглянутому графі є 9 ребер, а вершин непарного степеня .
Для орієнтованого графа визначаються дві степені вершин deg() – кількість ребер, що виходять із вершини v і deg() – кількість ребер, що входять в вершину v.
Петля дає внесок по одній одиниці в обидві степені. В орграфі суми степенів всіх вершин deg() і deg() рівні між собою і дорівнюють кількості ребер m цього графа:
Приклад 5. Визначити степені вершин орграфа зображеного на малюнку 7.
(мал. )
|
Типи графа |
Ребра |
Кратні ребра |
Петлі |
|
1.Простий граф |
Неорієнтовані |
Ні |
Ні |
|
2.Мультиграф |
Неорієнтовані |
Так |
Ні |
|
3.Псевдограф |
Неорієнтовані |
Так |
Так |
|
4.Орієнтований граф |
Орієнтовані |
Ні |
Так |
|
5.Орієнтований мультиграф |
Орієнтовані |
так |
Так |
Деякі спеціальні класи простих графів
Розглянемо деякі спеціальні класи простих графів, які часто використовують як приклади і які мають багато застосувань.
Повний граф з п вершинами (позначається як) – це граф, у якого будь-яка пара вершин з’єднана точно одним ребром
Кількість ребер у графі дорівнює =.
Приклад 6. Графи для п=1, 2, 3, 4, 5 є зображені
Граф називають порожнім, якщо Е=, тобто такий граф не має ребер. Порожній граф з п вершинами позначаються як Оп.
Граф G=(V,E) називають дводольним, якщо V можна розбити на дві підмножини: так, що кожне ребро з'єднує вершину з та вершину з . Дводольний граф називають повнив дводольним графом, якщо кожна вершина з з'єднана ребром з кожною вершиною з . Якщо =т, =п, то повний дводоль ний граф позначають як Ктп. Граф К1. п називають зіркою. Граф Кт п має п+т вершин та п∙т ребер.
Приклад7. Наведені деякі повні дводольні графи:
К1,5 К2,3 К3,3
Циклом Сп (п≥3) називають граф з множиною вершин V={v1, v2,..., vn} i множиною ребер E={{v1,v2},{v2,v3}, ..., {vn-1,vn},{vn,v1}}.
Приклад8. Цикли С3, С4, С5 та С6 зображені :
С3 С4 С5 С6
Колесом Wn називають граф, який одержують з циклу Сп додаванням ще однієї вершини, яку з’єднують з усіма п вершинами в Сп новими ребрами.
Приклад 9.Колеса W3, W4, W5, W6 зображені :
Простий граф, вершини якого зображають всі 2п бітових рядків довжини п, називають п-вимірним кубом і позначають Qn з’єднані ребром тоді й лише тоді, коли бітові рядки відрізняються точно в одному біті.
Приклад10. Графи Q1, Q2, та Q3 зображені :
Запитання для самоперевірки.
Література
К1 К2 К3 К4 К5
W3 W4 W5 W6
(101)
(111)
(110)
(100)
(000) (010)
(001) (011)
(01) (11)
(00) (10)
(0)
(1)
Q1 Q2
Q3