X Код для використання на сайті:
Ширина px

Скопіюйте цей код і вставте його на свій сайт

X Для завантаження презентації, скористайтесь соціальною кнопкою для рекомендації сервісу SvitPPT Завантажити собі цю презентацію

Презентація на тему:
Елементи теорії графів алгоритмів

Завантажити презентацію

Елементи теорії графів алгоритмів

Завантажити презентацію

Презентація по слайдам:

Слайд 1

Тема № 2. МАТЕМАТИЧНІ ОСНОВИ ТЕОРІЇ АЛГОРИТМІВ. 2.4 Елементи теорії графів А ну, пізнання людські, подивимося, хто-кого! (Ж.-П. Сартр)

Слайд 2

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

Слайд 3

Слайд 4

Леона рд Э йлер (нем. Leonhard Euler; 4 (15) апреля 1707), Базель, Швейцария — 7 (18) сентября 1783, Санкт-Петербург, Российская империя) — российский и швейцарский математик, внёсший значительный вклад в развитие математики, а также механики, физики, астрономии и ряда прикладных наук.

Слайд 5

Проблема четырёх красок — математическая задача, предложенная Гутри (англ.) в 1852 году. Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета.

Слайд 6

Історична ремарка Роком виникнення теорії графів одностайно вважається рік 1736, коли Леонард Ейлер опублікував розв’язок так званої задачі про кенігсберзькі мости, а також знайшов загальний критерій існування ейлерового циклу в графі. Хоча сам термін «граф» вперше з’явився в книзі угорського математика Д.Кьоніга в 1936 році. Отримання дальших суттєвих результатів у цій галузі датують серединою ХIХ століття. Однак початок проведення активних систематичних досліджень та становлення теорії графів як окремішного авторитетного розділу сучасної математики відбулося ще майже 100 років по тому, тобто в середині ХХ століття. Саме з цього часу граф стає однією з найпоширеніших і найпопулярніших математичних моделей у багатьох сферах науки і техніки. Картинка у вигляді набору точок на площині та ліній, проведених між деякими з них, стала зручною і наочною формою зображення найрізноманітніших об’єктів, процесів та явищ

Слайд 7

Визначення 2.4.1 . Графом назива-ється модель , де R – бінарне відношення множин V і E, таке, що кожен елемент e E знаходиться в відношенні R або рівно з одним, або рівно з двома елементами множини V. При цьому елементи множини V називаються вершинами графа, елементи множини E називаються ребрами графа, а відношення R – відношенням інцидентності. Вершини, інциденті одному і тому самому ребру, називаються суміжними.

Слайд 8

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

Слайд 9

ТЕОРІЯ ГРАФІВ Дещо спрощено відмінність різних підходів до однієї й тієї ж проблеми, пов’язаної з графами, можна продемонструвати на прикладі задачі перевірки ізоморфності двох заданих графів. Класична (абстрактна) теорія алгоритмів констатує, що ця проблема є розв’язною. Класична теорія графів уточнює, що для її розв’язання потрібно перебрати і перевірити не більше, ніж n! варіантів (n кількість вершин в обох графах). Прикладна теорія алгоритмів (і зокрема, її розділ під назвою "Алгоритми на графах") займається конструюванням нетривіальних процедур, що дозволяють визначити, чи є задані графи ізоморфними, і в більшості випадків здійснити цю перевірку достатньо ефективно за рахунок суттєвого скорочення перебору можливих варіантів.

Слайд 10

Теорія графів 1. Поняття графа. Способи завдання графів Нехай V деяка непорожня скінченна множина, а V (2) множина всіх двохелементних підмножин (невпорядкованих пар різних елементів) множини V. Графом (неорієнтованим графом) G називається пара множин (V,E ), де E довільна підмножина множини V (2) (E ÍV (2)); позначається G =(V,E ). Елементи множини V називаються вершинами графа G, а елементи множини E ребрами графа G. Відповідно V називається множиною вершин і E множиною ребер графа G. Традиційно ребра {v,w} записуються за допомогою круглих дужок (v,w) (іноді просто vw). Граф, який складається з однієї вершини, називається тривіальним.

Слайд 11

Теорія графів Нехай задано граф G =(V,E ). Якщо (v,w)ÎЕ, то кажуть, що вершини v i w є суміжними, у противному разі вершини v i w є несуміжними. Якщо е=(v,w) ребро графа, то вершини v i w називаються кінцями ребра е. У цьому випадку кажуть також, що ребро е з’єднує вершини v i w. Вершина v і ребро е називаються інцидентними, якщо v є кінцем е. Два ребра називаються суміжними, якщо вони мають спільну вершину. Існує декілька способів завдання графів. Одним зі способів завдання графа G =(V,E ) є завдання кожної з множин V і E за допомогою переліку їх елементів. Приклад 3.1. Граф G1=(V1,E1), V1={v1,v2,v3,v4} і E1={(v1,v3), (v1,v4),(v2,v3),(v2,v4),(v3,v4)} це граф із чотирма вершинами і п’ятьма ребрами. А граф G2=(V2,E2), V2={v1,v2,v3,v4,v5} і E2={(v1,v2),(v2,v4),(v1,v5), (v3,v2),(v3,v5),(v4,v1),(v5,v4)} граф із п’ятьма вершинами і сімома ребрами.

Слайд 12

Теорія графів Граф G =(V,E ) зручно зображати за допомогою рисунка на площині, який називають діаграмою графа G. Вершинам графа G ставляться у бієктивну відповідність точки площини; точки, що відповідають вершинам v i w, з’єднуються лінією (відрізком або кривою) тоді і тільки тоді, коли v i w суміжні вершини. Зрозуміло, що діаграма графа змінюватиме свій вигляд у залежності від вибору відповідних точок на площині.

Слайд 13

Теорія графів

Слайд 14

Теорія графів Графи можна задавати також за допомогою матриць. Занумеруємо всі вершини графа G натуральними числами від 1 до n. Матрицею суміжності A графа G називається квадратна матриця, в якій елемент aij i-го рядка і j-го стовпчика дорівнює 1, якщо вершини vi та vj з номерами i та j суміжні, і дорівнює 0 у противному разі.

Слайд 15

Теорія графів Занумеруємо всі вершини графа G числами від 1 до n і всі його ребра числами від 1 до m. Матрицею інцидентності B графа G називається nхm-матриця, в якій елемент bij i-го рядка і j-го стовпчика дорівнює 1, якщо вершина vi з номером i інцидентна ребру ej з номером j, і дорівнює 0 у противному разі.

Слайд 16

Теорія графів Нарешті, ще одним способом завдання графів є списки суміжності. Кожній вершині графа відповідає свій список. У список, що відповідає вершині v, послідовно записуються всі суміжні їй вершини. Вибір та зручність того чи іншого зі способів завдання графів залежать від особливостей задачі, яка розв’язується.

Слайд 17

Теорія графів . Підграфи. Ізоморфізм графів. Алгебра графів Граф G1=(V1,E1) називається підграфом графа G =(V,E ), якщо V1 ÍV i E1 ÍE. Важливі класи підграфів складають підграфи, які отримуються в результаті застосування до заданого графа операції вилучення вершини і/або операції вилучення ребра. Операція вилучення вершини v з графа G =(V,E ) полягає у вилученні з множини V елемента v, а з множини E всіх ребер, інцидентних v. Операція вилучення ребра e з графа G =(V,E ) це вилучення елемента e з множини E. При цьому всі вершини зберігаються.

Слайд 18

Теорія графів Графи G1=(V1,E1) і G2=(V2,E2) називаються ізоморфними, якщо існує таке взаємно однозначне відображення j множини вершин V1 на множину вершин V2, що ребро (v,w)ÎE1 тоді і тільки тоді, коли ребро (j (v),j (w))ÎE2. Відображення j називається ізоморфним відображенням або ізоморфізмом графа G1 на граф G2. Таким чином, ізоморфні графи відрізняються фактично лише ідентифікаторами (іменами) своїх вершин. З точки зору теорії графів ця відмінність не є суттєвою, тому звичайно ізоморфні графи ототожнюють і, зображаючи графи у вигляді діаграм, або зовсім не ідентифікують їхні вершини, або нумерують вершини натуральними числами.

Слайд 19

Теорія графів Ізоморфне відображення графа G на себе називається автоморфізмом графа G. Автоморфізм j графа G =(V,E ), при якому для кожної вершини v ÎV виконується j (v)=v, називається тривіальним автоморфізмом. Відношення ізоморфізму є відношенням еквівалентності на сукупності графів. Теорема 2.4.2 Графи G1 та G2 ізоморфні тоді і тільки тоді, коли матрицю суміжності (матрицю інцидентності) одного з цих графів можна одержати з матриці суміжності (матриці інцидентності) іншого графа за допомогою відповідних перестановок рядків та стовпчиків.

Слайд 20

Теорія графів Граф G =(V,E ) називається повним, якщо будь-які дві його вершини суміжні (тобто E=V  (2)). Повний граф з n вершинами позначається Kn. Очевидно, що будь-яка підстановка множини вершин повного графа Kn є автоморфізмом цього графа. Тому кількість усіх можливих автоморфізмів графа Kn дорівнює n!

Слайд 21

Теорія графів Для графів можна означити операції об’єднання, перетину і доповнення. Об’єднанням графів G1=(V1,E1) і G2=(V2,E2) називається граф G =(V1U V2,E1 U E2); позначається G =G1 U G2. Об’єднання G =G1 U G2 називається прямою сумою графів G1 i G2, якщо V1 V2=Ø. Перетином і різницею графів G1=(V,E1) i G2=(V,E2) з однаковими множинами вершин називаються графи G  =(V,E1 E2) i G  =(V,E1\E2) відповідно; позначаються G  =G1 G2 і G  = G1\G2. Доповненням графа G =(V,E ) називається граф Gd=(V,V  (2) \E ). Отже, граф має ту саму множину вершин V, що і граф G, а вершини графа суміжні тоді і лише тоді, коли вони несуміжні в G. Для графа G з n вершинами виконується Gd=Kn\G. Таким чином можна означити алгебру графів A= (типу (2,2,1)), носієм якої є множина Г всіх графів. Iснують й інші операції для графів, отже, сигнатуру алгебри A можна розширювати.

Слайд 22

Теорія графів 3. Графи та бінарні відношення Між множиною всіх графів із множиною вершин V і множиною всіх антирефлексивних симетричних бінарних відношень на V існує взаємно однозначна відповідність: графу G =(V,E ) відповідає відношення R на V таке, що (v,w) R тоді і тільки тоді, коли (v,w) E, v,w  V. Зокрема, порожньому графу G =(V, ) відповідає порожнє відношення на V (R =  ), а повному графу відношення (V  V )\iV, де iV відношення рівності: iV ={(v,v) | v  V  }. Очевидно, що операціям об’єднання, перетину і доповнення графів відповідають аналогічні операції для відношень. Якщо графам G1 i G2 відповідають відношення R1 i R2 то графам G1 G2, G1 G2, Gd відповідатимуть відношення R1 R2 R1 R2 i Gd\iV =(V  V )\(R1 iV). Якщо R транзитивне відношення, то у відповідному графі G для кожної пари ребер (v,w),(w, u) E існує замикаюче ребро (v, u) E.  

Слайд 23

Теорія графів 4. Степені вершин графа Степенем d(v) вершини v називається кількість ребер, інцидентних вершині v. Вершина степеня 0 називається ізольованою, а вершина степеня 1 кінцевою (або висячою) вершиною. Кубічним графом називається граф, степені всіх вершин якого дорівнюють 3. Нижченаведені твердження містять прості, але важливі властивості графів. Теорема 3.3. У будь-якому графі G =(V,E ) Σd(v)=2|E |. Справедливість цього твердження випливає з того, що кожне ребро графа інцидентне двом вершинам і, значить, у суму степенів усіх вершин воно вносить дві одиниці. Теорема . У будь-якому графі G =(V,E ) кількість вершин непарного степеня парна. Лема . Кількість ребер у повному графі Kn з n вершинами дорівнює n(n  1)/2.