Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Лекція Графи. Основні поняття І означення Хоча уявлення про об'єкти І методи теорії графів почало складатися вже в XVIII сто­річчі, сам термін

Скачати 499.08 Kb.

Лекція Графи. Основні поняття І означення Хоча уявлення про об'єкти І методи теорії графів почало складатися вже в XVIII сто­річчі, сам термін




Скачати 499.08 Kb.
Сторінка1/6
Дата конвертації31.03.2017
Розмір499.08 Kb.
ТипЛекція
  1   2   3   4   5   6

РОЗДІЛ 3. ТЕОРІЯ ГРАФІВ І МЕРЕЖ

У даному розділі будуть розглянуті об'єкти, методи, проблеми й алгоритми теорії гра­фів – традиційного розділу дискретного аналізу, що забезпечує дослідника засобами моде­лю­ван­­ня реальних об'єктів і систем.

Алгори́тм (латинізов. Algorithmi за араб. ім'ям узб. математика аль-Хорезмі) - набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі за скінченну кількість дій; система правил виконання дискретного процесу, яка досягає поставленої мети за скінченний час.
Тради́ція - досвід, звичаї, погляди, смаки, норми поведінки і т. ін., що склалися історично і передаються з покоління в покоління; звичайна, прийнята норма, манера поведінки, усталені погляди, переконання когось; узвичаєння, узвичаєність, неписаний закон.
Дослі́дник - людина, яка веде дослідження, займається науковими дослідженнями, вивченням, спостереженням, аналізом чого-небудь, сприяє отриманню нових знань.
Теорія графів - розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якої зліченної множини, а E - підмножина V × V.
У розділі виділені три теми, перша з яких присвячена зага­ль­­но­му аналізу графів, друга - спеціальним питанням, у першу чергу комбінаторним, що обу­мов­лює широке застосування графів у процесах розробки комп’ютеризованих систем, а третя – алгоритмам розв’язання проблем на графах.
Застосунок, застосовна програма, прикладна програма (англ. application, application software; пол. aplikacja; рос. приложение, прикладная программа) - користувацька комп'ютерна програма, що дає змогу вирішувати конкретні прикладні задачі користувача.



Тема 1. Загальні властивості графів


Початкові поняття теорії графів склалися при вирішенні головоломок і популярних задач. Але потім розвинена теорія графів стала дуже корисним інструментом вивчення склад­них систем. Це пов'язано з тим, що графи дуже зручно описують відносини між різними еле­мен­тами систем. Крім того, графи застосовуються для зображення алгоритмів, схем роботи пристроїв і систем, зокрема обчислювальної техніки, електротехніки, теорії надійності, оброблення даних, структури сполук, зокрема хімії, біохімії.
При́стрій (англ. device, appliance, нім. Vorrichtung f, Einrichtung f) - обладнання, конструктивно завершена технічна система, що має певне функціональне призначення і за допомогою якої виконується яка-небудь робота або спрощується, полегшується певний процес.
Електроте́хніка (рос. электротехника, англ. electrical engineering, нім. Elekrotechnik f) - галузь науки і техніки, пов'язана із застосуванням електричних і магнітних явищ для перетворення енергії, добування і зміни складу хімічних речовин, виробництва та обробки матеріалів; галузь, що охоплює питання отримання (виробництва), розподілу, перетворення і застосування електроенергії.
Інструме́нт (лат. instrumentum - знаряддя) - технологічне оснащення (знаряддя або пристрій), які в процесі праці безпосередньо стикаються з предметом праці з метою зміни чи контролю його форми, стану, властивостей тощо.
Популярність (від лат. populares, від populus - народ) - висока ступінь популярності чогось або когось у певній галузі. На виникнення популярності в деяких випадках впливає мода, і навпаки. Так само, як і мода, популярність прив'язана до певного і, як правило, невеликого відрізку часу.
Тео́рія наді́йності - наука, що вивчає закономірності розподілу відмов технічних пристроїв, причини і моделі їх виникнення.
Електро́нна обчи́слювальна маши́на (скорочено ЕОМ) - загальна назва для обчислювальних машин, що є електронними (починаючи з перших лампових машин, включаючи напівпровідникові тощо) на відміну від електромеханічних (на електричних реле тощо) та механічних обчислювальних машин.
Цей список можна продовжувати і продовжувати. У першу чергу ми приступаємо до графів з метою створення необхідного для інженера-системотехніка базису для розв’язання проблем у графовій постановці, що ви­ни­ка­ють у його професійній діяльності, а вже зараз - для оволодіння матеріалом, побудованим на графах, у курсах з комп'ютеризованих систем і мереж, програмування, організації баз даних і знань тощо. І більш віддалена, але не менш важлива мета - доповнення вашої математичної освіти дуже важливим розділом дискретної математики.
Матеріа́л - речовина, або суміш речовин, первинний предмет праці, який використовують для виготовлення виробу (основний матеріал), або які сприяють якимось діям. У останньому випадку уточнюють, що це допоміжний, чи витратний матеріал.
Дискре́тна матема́тика - галузь математики, що вивчає властивості будь-яких дискретних структур. Як синонім іноді вживається термін дискре́тний ана́ліз, що вивчає властивості структур скінченного характеру.

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

Хоча уявлення про об'єкти і методи теорії графів почало складатися вже в XVIII сто­річчі, сам термін «граф» і основні поняття сформувалися в закінченому вигляді лише в XX сторіччі. У даній лекції ми розглянемо базові поняття теорії графів, що дозволяють зрозуміти її об'єкт досліджень, познайомитися з її проблематикою і фундаментальними результатами.

Результат, пі́дсумок, (заст. ску́ток, вислід) - кінцевий наслідок послідовності дій. Можливі результати містять перевагу, незручність, вигоду, збитки, цінність і перемогу. Результат є етапом діяльності, коли визначено наявність переходу якості в кількість і кількості в якість.
Терміноло́гія - це: Сукупність термінів, тобто слів або словосполучень, що висловлюють специфічні поняття з певної галузі науки, техніки чи мистецтва, а також сукупність усіх термінів, наявних у тій чи іншій мові.
Дослі́дження, до́сліди - (широко розуміючи) пошук нових знань або систематичне розслідування з метою встановлення фактів; (вузько розуміючи) науковий метод (процес) вивчення чого-небудь.



  1. Графи, способи задання графів. Базуючись на дещо неформальному уявленні про гра­фи, сформованому у вступній лекції, введемо необхідні формальні означення для уточ­нення інтуїтивних понять.

Означення. Графом G = (V,E,Θ) назвемо трійку, що складається з множини V вершин, множини E ребер, функції Θ, що ставить у відповідність кожному ребру з множини E невпо­ряд­ковану пару вершин з множини V.

Таким чином, функцію Θ відповідно до символіки, прийнятої в першому розділі, варто записати у вигляді Θ: E  VV.

Си́мвол (англ. symbol символ) - знак, сутність, яка позначає іншу сутність.
Далі будемо позначати ребра символами e1, e2, …, а вершини – символами v1, v2,… .



Означення. Нехай функція Θ ставить у відповідність ребру ei з множини E невпоряд­ко­вану пару вершин (vk, vl). Тоді вершини vk і vl назвемо кінцевими вершинами ребра ei.

Допускається, щоб у множині Е було більш одного ребра з тими ж кінцевими вершина­ми. Такі ребра будемо називати паралельними.

Географічна паралель або рівнобі́жник (грец. παράλληλος - уздовж одне одного) - лінія перетину поверхні земної кулі площиною, паралельною (рівнобіжною) до площини екватора.
Якщо ребру еi функція Θ ставить у відповід­ність пару (vk, vk), то його будемо називати петлею.

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

Означення. Граф, що не містить петлі і паралельні ребра, будемо називати простим. Граф, що містить петлі і паралельні ребра, будемо називати мультиграфом. Граф, що не містить паралельні ребра, у тому числі і паралельні петлі, будемо називати графом Бержа. Граф, що не містить ребра, будемо називати порожнім (порожній графа на n вершинах іноді позначається On). Граф, що не містить вершини (і, отже, ребра), будемо називати нуль-графом.

Велике значення мають способи задання графів. З одного боку, простота деяких з них сприяла поширенню графів, з іншого боку, поява комп'ютерів вимагала простих і доступних комп'ютерам способів. Існують наступні три способи задання графів:

а) аналітичний: має ряд форм, що відрізняються способом задання функції Θ. У най­про­стішому вигляді її задають множиною невпорядкованих пар (vk,vl), що зображують кінцеві вер­шини ребер.

Приклад 1. Множина V = {v1, v2, v3, v4}, множина E= {e1, e2, e3, e4}, множина пар {(v1,v2), (v2,v3), (v1,v4), (v4,v3)} задають граф. Однак, при цьому втрачається інформація про те, з якими вершинами зв'язані ребра. Щоб цю інформацію не утратити, функцію Θ можна задати в традиційному вигляді: Θ(e1) = (v1, v2); Θ(e2) = (v2, v3); Θ(e3) = (v1, v4); Θ(e4) = (v4, v3).

Цю же інформацію можна задати, прийнявши, що множина Е і множина пар кінцевих вершин однаково впорядковані.

Іншою формою аналітичного способу може бути задання множин V, E і відображення F кожної вершини vk  V у множину підмножин V. Наприклад, граф з прикладу 1 можна задати в такий спосіб: V= {v1,v2,v3,v4}, E= {e1,e2,e3,e4}, Fv1 = {v2,v4}, Fv2 = {v1,v3}, Fv3 = {v2,v4}, Fv4 = {v1,v3}.

Цей метод зручно використовувати в комп'ютерах.

б) геометричний: кожна вершина зображується точкою, кожне ребро – лінією, що з'єднує кінцеві вершини. Саме цим способом ми скористалися у вступній лекції. Через його про­стоту і наочність геометричний спосіб приніс популярність графам. Заданий вище ана­літич­ним способом граф геометрично можна задати у вигляді:

v1 e2 v4

e1 e4

v2 e2 v3

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

Кори́стува́ч - той, хто користується чим-небудь - майном, землею, комп'ютером тощо.
Геоме́трія (від дав.-гр. γη - Земля і μετρέω - вимірюю; землеміряння) - розділ математики, наука про просторові форми, відносини і їхні узагальнення.

в) матричний: для задання функції Θ застосовуються матриці, елементи яких харак­те­ри­зують зв'язки вершин чи вершин і ребер. Для уточнення матричного способу введемо відповідні означення.



Означення. Назвемо вершину vi і ребро ej інцидентними, якщо Θ(ej) = (vk,vi) або Θ(ej) = (vi, vl) або Θ(ej) = Θ(ej) = (vi, vi). Вершини vi і vj назвемо суміжними, якщо існує хоча б одне ребро, інцидентне їм обом.

Тоді граф можна задати у вигляді матриць:

1) суміжності: R=║rij║, де елемент rij = n – число ребер з кінцевими вершинами vi, vj. Для графа з прикладу 1 матриця суміжності має вигляд:

Очевидно, матриця суміжності графа - це квадратна матриця mm, де m - число вершин графа;

Квадра́т - чотирикутник, у якого всі сторони рівні і всі кути прямі. Для задання квадрата необхідно і достатньо задати дві точки на координатній площині, які відповідатимуть будь-яким двом кутам та врахувати їх суміжність.
Матриця суміжності - один із способів представлення графа у вигляді матриці.

2) інцидентності: A=║aij║, де елемент aij = 1, якщо ребро ej інцидентне вершині vi, 0, у протилежному випадку. Для графу з прикладу 1 матриця інцидентності має вигляд:

Очевидно, матриці інцидентності графа завжди має розмірність pm, де p - число вер­шин графа, а m – число його ребер.

Ма́триця інциде́нтності (англ. Incidence matrix) - одна з форм представлення графа, в якій вказуються зв'язок між інцидентними елементами графа (ребро (дуга) і вершина). Стовпці матриці відповідають ребрам, рядки - вершинам.
Задання графів матрицями дозволяє алгоритми розв’язання проблем, поставлених як проблеми над графами, представити в зручному вигляді алгоритмів над матрицями. Також задання графів матрицями дозволяє в зручній формі перевіряти їхні особливості, наприклад, про наявність петель у графі говорять одиниці на головній діагоналі матриці суміжності, а матриця суміжності повного графа складається, за винятком нульової головної діагоналі, тільки з одиниць.
Повний граф - простий граф, в якому кожна пара різних вершин суміжна, тобто існує ребро, що сполучає ці вершини. Повний граф зазвичай позначається Kn.

Зазначимо, що при використанні матриць суміжності, на відміну від матриць інцидент­нос­ті, втрачається інформація про те, з якими вершинами зв'язані ребра.

Іноді множина усіх вершин графа G = (V,E,Θ), суміжних із зафіксованою вершиною vi, називається оточенням вершини vi і позначається N(vi).

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

Означення. Нехай V не порожня множина.

Особливість, або сингулярність в математиці - це точка, в якій математичний об'єкт (зазвичай функція) не визначений або має нерегулярну поведінку (наприклад, точка, в якій функція недиференційована).
Ото́чення - ізоляція частини сил (декількох підрозділів, частин, з'єднань тощо) противника від сусідніх і розташованих в його тилу військ з метою знищення або полонення. Оточення досягається охопленням флангів і обходом певного угрупування противника з швидким наступом за напрямками, що сходяться, і виходом у його тил.
Озна́чення, ви́значення чи дефіні́ція (від лат. definitio) - роз'яснення чи витлумачення значення (сенсу) терміну чи поняття. Слід зауважити, що означення завжди стосується символів, оскільки тільки символи мають сенс що його покликане роз'яснити означення.
Наукова публікація - це опублікований опис наукового дослідження, що містить аналіз сутності певної наукової проблеми, методи і результати її дослідження, науково обґрунтовані висновки. Завданням наукових публікацій є знайомити науковий світ з результатами досліджень окремих вчених та груп науковців.
Порожня множина в математиці - множина, яка не містить жодного елемента. Така множина позначається як Ø або .
Пара (V, Е), де Е – довільна підмножина множини V2, називається графом (неорієнтованим графом). Елементи множини V назива­ють­ся вершинами графа, а елементи множини Е - ребрами.

Отже, відповідно до цього означення граф - це скінченна множина V вершин і скін­чен­на множина Е ребер такі, що Е  V2.

Скінченна множина - це множина, кількість елементів якої є скінченна, тобто існує натуральне число k, що є числом елементів цієї множини. В протилежному випадку множина є нескінченною. Визначення 2. Множина, що не має рівнопотужної з нею власної підмножини, а також порожня множина, називається скінченною
Множини вершин і ребер графа G позначаються в цьому випадку символами VG і EG відповідно. Вершини і ребра графа називаються його елемен­та­ми. Число |VG| вершин графа G називається його порядком і позначається через |G|. Якщо |G| = n, |EG| = m, то G називають (n,m)-графом.

Легко підрахувати число всіх графів з фіксованою множиною вершин V. Ці графи роз­різ­няються своїми ребрами, і тому їхнє число дорівнює кількості підмножин у V2, тобто 2k, де k = n(n – 1)/2, n = |V|.

Кількість - в Арістотелівській логіці друга з 10 категорій (класів, розрядів, які спрощують процес розумового визначення будь-якої речі), побічна обставина матеріальних речей , за допомогою якої вони поширюються в просторі, вимірюються якоюсь математичною нормою і здатні бути поділеними на окремі частини.
Однак ці графи не завжди варто розрізняти. Як у застосуваннях теорії графів, так і в самій цій теорії частіше істотно лише те, що є об'єкти (вершини графа) і зв'язки між цими об'єктами (ребра). З цих позицій графи, що утворюються один з іншого зміною найменувань вершин, розумно не розрізняти. Це приводить до поняття ізоморфізму графів.

Означення. Нехай G і H - графи, а : VG  VH - бієкція. Якщо для будь-яких вершин u і v графа G їхні образи (u) і (v) суміжні в Н тоді і тільки тоді, коли u і v суміжні в G, то ця бієкція називається ізоморфізмом графа G на граф Н. Якщо такий ізоморфізм існує, то ми пишемо G  Н (тоді і Н  G) і говоримо, що графи G і Н ізоморфні.

Наприклад, три графи, зображені на рис.3.1, ізоморфні, а графи на рис.3.2 не ізо­мор­ф­ні. Питання про те, чи ізоморфні дві даних графи, у загальному випадку виявляється склад­ним. Підходи до його вирішення наведені в літературі, що рекомендується.



Рис.3.1


Рис.3.2


Очевидно, що відношення ізоморфізму графів є відношенням еквівалентності, тому що во­но симетричне, транзитивне і рефлексивне.
Логічна еквівалентність (еквіваленція) - двомісна логічна операція, що має значення «істина» тоді і тільки тоді, коли обидва операнди мають однакове значення. В інших випадках еквіваленція буде хибною.
Рефле́кс - автоматична цілісна стереотипна реакція організму на певний подразник, на зміни зовнішнього середовища або внутрішнього стану, яка здійснюється при обов'язковій участі центральної нервової системи.
Отже, множина усіх графів розбивається на кла­си еквівалентності: графи з одного класу попарно ізоморфні; графи з різних класів не ізо­мо­рф­ні. Ізоморфні графи природно ототожнювати, вважати співпадаючими, тому що їх мож­на зо­бразити одним рисунком. Вони могли б розрізнятися конкретною природою своїх елемен­тів, але саме це ігнорується при введенні поняття «граф» описаним вище другим способом.

У деяких ситуаціях усе-таки доводиться розрізняти ізоморфні графи, і тоді використо­ву­ється «вершинно-позначений граф». Граф порядку n називається вершинно-позначеним, як­що його вершинам присвоєні деякі позначки, наприклад, номери 1,2,...,n. Ототожнивши кож­ну з вершин графа з її номером (і, отже, множину вершин - з множиною чисел (1,2,...,n), ви­зна­чимо рівність вершинно-позначених графів G і Н того самого порядку: G = Н тоді, коли EG = EH. На рис.3.3 зображені три різних вершинно-позначених графи.


1

2

3








3

2

1

3

1


2

Рис.3.3
При необхідності підкреслити, що розглянуті графи розрізняються лише з точністю до ізоморфізму, говорять: «абстрактний граф».

Необхідність - система зв'язків і відносин, що зумовлює зміну, поступальний рух, розвиток у жорстко визначеному напрямку з жорстко визначеними результатами. Іншими словами, необхідність - це такий зв'язок, що обов'язково призводить до певної події.
Строго говорячи, абстрактний (чи непозна­чений) граф - клас ізоморфних графів. Число gn непозначених графів порядку n визначається складно. Відома формула Пойа



gn  2k / n!,

що дає асимптотику числа gn. Тут k визначається як і в описаному вище випадку непозначе­них графів. Ця формула означає, що дві функції g(n) = gn і f(n) = 2k/n! асимптотично рівні, тобто lim g(n)/f(n) = 1.

n

Отже, число вершинно-позначених графів порядку n «приблизно» у n! раз більше чис­ла непозначених. Цей факт здається інтуїтивно ясним: існує рівно n! позначень множини, що складає з n вершин. Однак, не треба думати, що з кожного непозначеного графа виходить n! вершинно-позначених. Наприклад, усі позначки порожнього графа приведуть до одного і того ж позначеного графу; простий ланцюг Рз породжує три, а не шість позначених графів (рис. 3.3). Але все-таки, як правило, кожен непозначений граф приводить до n! вершинно-позна­чених графів.



Якщо ми хочемо розрізняти конкретну природу елементів графа, причому не тільки вершин, але і ребер, що ігнорується при введенні поняття «граф» описаним вище другим означенням графів, то тоді будемо застосовувати перше з означень, що дозволяє позначати і вершини, і ребра. Особливо справедливо це для мультиграфів, у означенні яких по другому способу Е уточнюється не як довільна підмножина множини V2, а як сім’я підмножин мно­жи­ни V2.
Справедливість - мораль та чеснота, вразливість як на суспільне добро, так і на суспільне зло. За Платоном, справедливість - це найвища чеснота, що утримує мужність, поміркованість та мудрість в повній рівновазі й гармонії («кожному своє»).
Саме це уточнення дозволяє формально допустити паралельні (кратні) ребра в муль­ти­гра­фах. Але це аж ніяк не дозволяє розрізняти ці ребра, як це дозволяє реалізувати перше з означень графів.

Далі ми будемо використовувати перше з означень графів, але в тих випадках, коли по­знач­ки ребер (ребер і вершин) не важливі, ми будемо застосовувати (це буде зрозуміло з кон­тексту) і друге означення вершинно-позначених (непозначених) графів.

3. Ступені вершин графа і їхні властивості. Уведемо важливе для аналізу властивостей графів поняття ступеня вершини і розглянемо деякі важливі властивості графів, обумовлені ступенями.

Означення. Число інцидентних вершині vi ребер будемо називати ступенем вершини і позначати d(vi). Вершину з нульовим ступенем назвемо ізольованою, а зі ступенем рівним 1, - висячою. Ребро, інцидентне висячій вершині, також називається висячим.

Очевидно, петля додає до ступеня вершини 2.



Приклад 2. Нехай граф заданий геометрично.

v2 e2 v3



e3

e4

e1 v5

. e5

v1 v4

Тоді визначимо ступені його вершин і розподілимо вершини по класах:

d(v1) = 1, отже вершина v1 - висяча;

d(v2) = 3, d(v3) = 3, d(v4) = 3;

d(v5) = 0, отже вершина v5 – ізольована.

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


Найменування характеристики

Приклад 1

Приклад 2

Число ребер графа

4

5

Сума ступенів усіх вершин

8

10

Число вершин непарного ступеня

0

4

Легко помітити, що для розглянутих у прикладах графів: а) сума ступенів вершин до­рів­нює 2m, де m - число ребер графа;

Додавання - бінарна арифметична операція, суть якої полягає в об'єднанні математичних об'єктів.
б) число вершин непарного ступеня парне.

Виявляється сума ступенів завжди вдвічі більша числа ребер будь-якого графа, а кіль­кість вершин непарного ступеня парна в будь-якому графі. Справедлива наступна

  1   2   3   4   5   6


Скачати 499.08 Kb.