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


НазваТема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину
Дата конвертації06.02.2013
Розмір445 b.
ТипПрезентации


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

11 клас. АТП

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

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

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

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



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

Теорія графів — розділ математики, що дає змогу формалізувати взаємозв'язки між різноманітними видами інформації, організувати абстрактне їх представлення.

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

Якщо ребро з'єднує дві вершини, то кажуть, що воно інцидентне цим вершинам, а вершини, які з'єднані таким ребром, називають суміжним.

Петля

Якщо кінці ребра належать одній вершині, то таке ребро називається петлею.

Ізольовані вершини

Вершини, які не належать кінцям жодного з ребер у графі, називаються ізольованими.

Вершина А – приклад ізольованої вершини.

Нуль-граф

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

В графі ребро без вершин існувати не може.

Порожній граф

Граф називається порожнім, якщо

,

тобто граф не має ребер

Повний граф

Граф, у якому будь-яка пара вершин з'єднана ребрами, називається повним.

Визначення кількості вершин у графа

Природно виникає питання: скільки є різних графів з множиною вершин Х, якщо N(X)=n.

Теорема.

Число усіх різних графів з n вершинами дорівнює

Плоский граф

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

Степінь вершини

Степенем вершини будемо називати число ребер, яким належить ця вершина. Позначається степінь вершини а як Р(а).

Наприклад,вершина А має степінь 3, а вершина В - степінь 1: Р(А)=3; Р(В)=1.

Степенем вершини xi графа називається число вершин xj, які інцидентні вершині xi (число відрізків які виходять з вершини xi).

Степенем вершини xi графа називається число вершин xj, які інцидентні вершині xi (число відрізків які виходять з вершини xi).

Якщо степінь вершини дорівнює 1, то вершина називається кінцевою вершиною графа.

Якщо степінь вершини дорівнює 0, то вершини називається ізольованою.

Шлях

Нехай задано граф з N вершинами, х1, х2, …, хN. Кажуть, що існує шлях від вершини хi до вершини хj, якщо існує послідовність ребер, яка з'єднує вершини хi і хj. У свою чергу вершини хi та хj є зв'язними, якщо існує шлях від хi до хj.

Шлях

Зв'язні вершини

Зв'язний граф (повний, неповний)

Граф називатимемо зв'язним, якщо будь-яка його вершина зв'язна.

Повний граф завжди зв'язний, але не всякий зв'язний граф є повним.

Цикл

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

На малюнку зображено граф, який для кожної вершини має по кілька циклів. Наприклад, для вершини 1 існує 6 циклів: (1-2, 2-5, 5-3, 3-1), (1-3, 3-7, 7-4, 4-1), (1-3, 3-5, 5-6, 6-3, 3-1), (1-2, 2-5, 5-6, 6-3, 3-1), (1-2, 2-5, 5-6, 6-3, 3-7, 7-4, 4-1), (1-3, 3-5, 5-6, 6-3, 3-7, 7-4, 4-1).

Простий шлях

Якщо цикл через кожну вершину проходить лише один раз, то такий шлях називається простим.

З малюнку видно, що для вершини 1 існує 4 простих цикли:
  • (1-2, 2-5, 5-3, 3-1),

  • (1-3, 3-7, 7-4, 4-1),

  • (1-2, 2-5, 5-6, 6-3, 3-1),

  • (1-2, 2-5, 5-6, 6-3, 3-7, 7-4, 4-1).



Довжина шляху

Довжиною шляху (циклу) називається кількість ребер цього шляху (циклу) На малюнку для кожного вказаного циклу вершини 1 неважко порахувати довжину: 4, 4, 5, 5, 7, 7.

Дерево

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

Ліс

Кілька дерев, які не мають спільних вершин, називають лісом.

Орієнтований граф

Граф, у якому для всіх ребер вказано напрям, називається орієнтованим, або орграфом.

В орієнтованому графі для вершини 1 існує тільки два орієнтовані цикли:
  • (1-2, 2-5, 5-3, 3-1),

  • (1-4, 4-7, 7-3, 3-1).



Неограф

Неорієнтований граф (неограф) — це граф, для кожного ребра якого несуттєвий порядок двох його кінцевих вершин

Орієнтований граф

Для орієнтованих графів специфічним є визначення степенів вершин.

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

Сума вхідного і вихідного степенів вершини орієнтованого графа називається степенем цієї вершини.

Орграф

Орієнтований граф (орграф) — це граф, для кожного ребра якого істотний порядок двох його кінцевих вершин.

Залежно від типу ребер відрізняють типи графів.



Зважений граф

Якщо у графі вказана “вага” кожного ребра, то такий граф називається зваженим.

Існують неорієнтовані зважені графи та орієнтовані зважені графи.

Змішаний граф

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

Загальний випадок графа

У загальному випадку множина ребер може складатися із трьох непересічних підмножин: підмножини ланок, підмножини дуг і підмножини петель

Граф як геометрична конфігурація

Наочно граф можна уявляти як геометричну конфігурацію, яка складається з точок (вершин графу 1,2,3,4,5,6) і ребер (ліній або відрізків №1(1-3), №2(3-4), №3(4-5), №4(3-5), №5(2-3), №6(2-5), №7(5-6), №8(6-2), №9(2-1), які сполучають деякі точки (вершини) за вибраним алгоритмом

Ейлерів граф

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

Ойлер (Euler)

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

Особливість цієї теорії - у геометричному підході до вивчення об'єктів.

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

Перша робота з теорії графів належить Леонарду Ойлеру. Вона з’явилась в публикаціях Санкт-Петербургзської Академії наук у 1736 році.



Кенігзберзькі мости

Праця Ойлера розпочиналася з розгляду однієї ломиголовки так званої „задачі про кенігзберзькі мости”

Сім мостів Кеніґсберґа — видатна історична задача з математики. Доведення неможливості її розв'язання Леонардом Ейлером в 1735 призвело до створення теорії графів і передувало ідеї топології.

Місто Кенігзберг (нині Калінінград) розташоване на берегах річки Прегель і двох островах. Різні частини міста сполучені сімома мостами. Щонеділі жителі міста любили здійснювати прогулянки по місту. Ойлер поставив питання: чи можна здійснити прогулянку, вийшовши з дому і повернувшись до нього, таку, щоб по кожному мосту пройти рівно один раз.

Формалізуємо задачу про мости

Схематична карта міста зображена на рисунку 1.

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



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

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

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

Це дало початок системному математичному підходу до побудови та вивчення властивості графів.

Зв'язний граф за Ойлером

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

Такий ланцюг називають ойлеровим ланцюгом, або ойлеровим циклом

Ейлерів ланцюг

В теорії графів, ейлерів ланцюг — ланцюг в графі, що проходить кожне ребро рівно один раз. Схожим чином, ейлерів цикл — ейлерів ланцюг, що починається і завершується в одній вершині. Вперше розглянуті Леонардом Ейлером під час розв'язання відомої задачі кенігсберзьких мостів в 1736. Математично задача звучить так:

Чи можливо, для графа на малюнку праворуч, побудувати ланцюг (або цикл), що проходить кожне ребро рівно однин раз?

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

Гамільтонів граф

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

Завдання додому

  • Вчити основи теорії Графів

  • Підібрати умови задач, які розв'язував Ейлер (Ойлер)

  • Підготувати повідомлення про практичне застосування графів



Схожі:

Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину iconТема 2: «Основи теорії графів»
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину iconТема № математичні основи теорії алгоритмів. 4 Елементи теорії графів
Широко використовується теорія графів при рішенні різних задач на обчислювальних машинах. Вірогідно і те, що теорія графів служить...
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину iconУрок Пошук у ширину та глибину
Одним із найпоширеніших способів представлення графа є матриця суміжності. Саме на перегляді цієї матриці і базується метод пошуку...
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину iconОсновні поняття теорії графів Сукупність точок та ліній, зображена на малюнку і є графом
Лінія на графі, яка не проходить вздовж жодного його ребра більш ніж один раз, називається
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину iconТеорія графів – спеціальний розділ математичного програмування, який вивчає кількісні і якісні характеристики графів
Певна вершина може бути з’єднана ребром сама з собою, тоді таке ребро називається
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину iconАлгоритми, а заодно і їх теорію й аналіз. Основними математичними складової теорії алгоритмів виявилися теорія множин, математична логіка й теорія графів
Пізнання завжди шукало способи опису алгоритмів. І застосовуючи природну мову пізнання математикові, необхідно визначити у ній ті...
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину iconПредставлення моделей. Представлення моделей
Для представлення будь-якої моделі необхідні основні синтаксичні елементи і способи їх з'єднання. Тип використовуваного синтаксису...
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину iconВплив родини графів Браницьких на економічний, соціальний, культурний розвиток Білоцерківщини браницьк І
Вплив родини графів Браницьких на економічний, соціальний, культурний розвиток Білоцерківщини
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину iconПлан Поняття про фармакогнозію. Історична довідка Основні поняття і терміни фармакогнозії
Фармакогнозія. Основні поняття та завдання фармакогнозії. Способи заготівлі, сушіння та зберігання лрс
Тема: Основні поняття теорії графів. Способи представлення графів. Пошук у ширину та глибину iconУрок Поняття алгоритму; властивості алгоритмів Урок пр. Способи представлення алгоритмів Урок Виконавець та система команд
Урок пр. Способи представлення алгоритмів Урок Виконавець та система команд виконавця

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


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