Тема 2: «Основи теорії графів»


НазваТема 2: «Основи теорії графів»
Дата конвертації10.02.2013
Розмір445 b.
ТипПрезентации


Профільна інформатика

11 клас. АТП

Тема 2: «Основи теорії графів»

Основи теорії графів

Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину.

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



Узагальнююче повторення

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

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

Узагальнююче повторення

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

Наприклад, у вигляді графа можуть бути зображені:

 електричні і транспортні мережі;

 інформаційні і комп’ютерні мережі;

 карти автомобільних, залізничних і повітряних шляхів, газо- і нафтопроводів;

 моделі кристалів;

 структури молекул хімічних речовин;

 моделі ігор;

 різні математичні об’єкти (відношення, частково впорядковані множини, решітки, автомати, ланцюги Маркова, алгоритми і програми тощо);

 лабіринти;

 плани діяльності або плани виконання певних робіт (розклади);

 генеалогічні дерева тощо.

Узагальнююче повторення

Приклади застосування теорії графів:

 пошук зв’язних компонентів у комунікаційних мережах;

 пошук найкоротших, “найдешевших” та “найдорожчих” шляхів у комунікаційних мережах;

 побудова кістякового дерева: зв’язність з найменшою можливою кількістю ребер;

 пошук максимальної течії для транспортної мережі, в якій визначено вхідні та вихідні вершини та пропускні спроможності ребер;

 ізоморфізм графів: ідентичність структур молекул (ізометрія);

 знаходження циклів графів:

 гамільтонів цикл: обійти всі вершини графа, побувавши в кожній з них лише один раз (задача комівояжера);

 ейлерів цикл: обійти всі ребра (контроль дієздатності мережі);

 розфарбування графів: розфарбування географічних карт, укладання розкладів, розміщення ресурсів тощо;

 планарність графів: проектування друкованих електронних та електричних схем, транспортних розв’язок тощо;

 знаходження центрів графа: вершин, максимальна відстань від яких до всіх інших вершин графа є мінімальною (“столиць”).

Ейлеровий граф

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

Для зв’язного графа G еквівалентними є такі твердження:
  • G — ейлеровий граф;

  • кожна вершина G має парний степінь;

  • множину ребер графа G можна розділити на прості цикли.



Дерева

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

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

Часто при розв’язанні задачі про графи її спочатку досліджують на деревах.

Завдання для перевірки знань

 1. Яка кількість математичних характеристик визначає граф?

а) 0;

б) 1;

в) 2;

г) точної кількості не існує.

2. Виберіть неправильне твердження:

а) дві суміжні вершини інциденті одному ребру;

б) два суміжні ребра інциденті одній вершині;

в) ребро, інцидентне деякій вершині, має суміжне ребро;

г) вершина, інцидентна деякому ребру, має суміжну вершину.

3. Виберіть правильне твердження:

а) граф — це графічне зображення відношень на множині;

б) ізоморфізм графів є відношенням еквівалентності;

в) лише скінченні графи можна пронумерувати;

г) графи можуть мати лише графічне зображення.



Завдання для перевірки знань

4. Нехай  означає напрямок від загальнішого поняття до менш загального (наприклад, людина  чоловік). Виберіть з нижченаведених варіантів правильний:

а) маршрут  ланцюг  цикл  простий цикл;

б) маршрут  цикл  ланцюг  простий ланцюг;

в) маршрут  ланцюг  простий ланцюг  цикл;

г ) маршрут  цикл  простий цикл  ланцюг.

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

а) шлях;

б) сильна зв’язність;

в) симетрична пара;

г) показник всесуміжності;

д) остов;

е) всі стосуються.



Представлення графів

Ми розглядали графічне представлення графів. А як бути при складанні алгоритмів роботи з графами?

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

Помічений граф та його матриця суміжностей

На рис. показані помічений граф G та його матриця суміжностей А. Легко помітити, що суми елементів матриці за стовпцями дорівнюють степеням відповідних вершин графа G. Взагалі, завдяки відповідності між графами та матрицями будь-яке поняття теорії графів можна зіставити з деяким аналогом, пов’язаним з матрицею суміжностей.

Задання графа

1. Перший спосіб передбачає задання матриці суміжності, яка для графа з n вершинами представляється двовимірним масивом n*n.

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

Якщо матриця суміжності представляє неорієнтований незважений граф (а), то за наявності вершин I та j відповідні елементи матриці дорівнюють 1, тобто a[i,j]=a[j,i]=1, а у разі відсутності ребра між вершинами i та j – 0, тобто a[i,j]=a[j,i]=0 (б). Для неорієнтованого графа матриця симетрична, значення діагональних елементів дорівнюють 0 (оскільки у графі відсутні петлі)

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

В матриці суміжності зваженого графа можлива відсутність симетричності.

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

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

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

У випадку зваженого графа елементи матриці суміжності a[i,j], що відповідає такому графу, збігатимуться зі значеннями “ваги” ребер між вершинами i та j.

Списки суміжних вершин

Другий спосіб представлення графа є списки суміжних вершин.

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

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

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

Наприклад:

Подання графа у вигляді масиву суміжностей.

Подання графа у вигляді масиву суміжностей.

Для кожної вершини u із V список містить всі вершини v, такі що (u, v) належать Е, тобто список складається з усіх вершин, суміжних з u.

Вершини у кожному списку зазвичай зберігаються в довільному порядку. Як для орієнтованих, так і для неорієнтованих графів представлення у вигляді списків вимагає обсяг пам'яті, рівний O (V + E).

Представлення у вигляді матриці суміжностей:

0 1 0 0 1

1 0 1 1 1

0 1 0 1 0

0 1 1 0 1

1 1 0 1 0

Передбачається, що вершини пронумеровані в певному порядку 1, 2,..., V. У такому разі подання графа являє собою матрицю розміром VxV, що таку:
  • A [i,j] = 1 - якщо є ребро від i до j (або навпаки, якщо не орієнтований граф).

  • A [i,j] = 0 в іншому випадку.



Орграф і його матричне подання: а - орграф; б - матриця суміжності



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

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

При подальшому будемо припускати, що вершини графа пронумеровані від 1 до N, а ребра - від 1 до M. Кожному ребру і кожній вершині зіставлена вага - ціле додатне число.

Для кожного способу зберігання будемо визначати просторову складність і часову складність наступних операцій:
  • перевірка суміжностей вершин x і y;

  • перерахування всіх вершин суміжних з x;

  • визначення ваги ребра (x, y);

  • визначення ваги вершини x;

  • перерахування всіх ребер (x, y);

  • перерахування ребер, інцидентних вершині x;

  • перерахування вершин, інцидентних ребру s.



Матриця суміжностей це двовимірний масив розміром N*N:





Списки суміжних

Списки суміжних це одновимірний масив розміром N, що містить список вершин суміжних з даною.

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

Цей спосіб зберігання краще всіх інших підходить для операції «перерахування всіх вершин суміжних з x»

Типи задач

Під час дослідження задач, що пов'язані з обробкою інформації, яку можна представити у вигляді графів, постає питання пошуку:

Завдання 1

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

Завдання 2

Виконати завдання 1 для неорієнтованого незваженого графа, що немає петель та з кількістю вершин N=5, вивівши результат виконання програми.

Завдання 3

Виконати завдання 1 для орієнтованого незваженого графа, що немає петель та з кількістю вершин N=5, вивівши результат виконання програми.

Завдання 4

Виконати завдання 1 для неорієнтованого зваженого графа, що немає петель та з кількістю вершин N=5, вивівши результат виконання програми.

Завдання 5

Виконати завдання 1 для орієнтованого зваженого графа, що немає петель та з кількістю вершин N=5, вивівши результат виконання програми.


Схожі:

Тема 2: «Основи теорії графів» iconТема № математичні основи теорії алгоритмів. 4 Елементи теорії графів
Широко використовується теорія графів при рішенні різних задач на обчислювальних машинах. Вірогідно і те, що теорія графів служить...
Тема 2: «Основи теорії графів» iconТема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину
Теорія графів — розділ математики, що дає змогу формалізувати взаємозв'язки між різноманітними видами інформації, організувати абстрактне...
Тема 2: «Основи теорії графів» iconТема № математичні основи теорії алгоритмів. 3 Елементи математичної логіки, теорії предикатів
Уперше правила міркувань систематизував грецький філософ Аристотель ( 384-322 р до н е.) виклав закони логічного виведення, запропонував...
Тема 2: «Основи теорії графів» iconОсновні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом
Лінія на графі, яка не проходить вздовж жодного його ребра більш ніж один раз, називається
Тема 2: «Основи теорії графів» iconТеорія графів – спеціальний розділ математичного програмування, який вивчає кількісні і якісні характеристики графів
Певна вершина може бути з’єднана ребром сама з собою, тоді таке ребро називається
Тема 2: «Основи теорії графів» iconОснови теорії ймовірності та математичної статистики План лекції Основні поняття теорії ймовірностей
Теорія ймовірностей вивчає масові випадкові події, які характеризуються стійкою частотою їх появи
Тема 2: «Основи теорії графів» iconОснови теорії ймовірності та математичної статистики проф. В. П. Марценюк План лекції Основні поняття теорії ймовірностей
Теорія ймовірностей вивчає масові випадкові події, які характеризуються стійкою частотою їх появи
Тема 2: «Основи теорії графів» iconТема 14. Теорії валютних курсів Тема 14. Теорії валютних курсів
Проте нерідко використовується для позначення коштів, виражених в грошових одиницях тільки іноземних держав чи міжнародних організацій...
Тема 2: «Основи теорії графів» iconОснови теорії держави І права план основні теорії виникнення держави І права
Держава як класове явище І як суспільний договір (порівняння концепції Енгельса І гоббса)
Тема 2: «Основи теорії графів» iconТеорії кислот іоснов Теорії кислот іоснов
Якщо ступінь дисоціації кислот (основ) не перевищує 5%, то рН можна розраховувати із загальної концентрації кислоти (основи)

Додайте кнопку на своєму сайті:
dok.znaimo.com.ua


База даних захищена авторським правом ©dok.znaimo.com.ua 2013
звернутися до адміністрації
dok.znaimo.com.ua
Головна сторінка