Дослідження на тему теорії графів. Графи

Тема графів – це цікава, корисна та лякаюча тема. Теорія графів - "Жах студента". Алгоритми на графах - приголомшливий розум людей, які їх відкрили.

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

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

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

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

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

Напевно, ви читали підручники і бачили такий запис G(V,E) або щось схоже. Так ось, V — це якийсь один об'єкт із безлічі об'єктів. У нашому випадку безліч об'єктів — це міста, отже, V — це якесь певне місто. Так як об'єкти не обов'язково міста, а слово об'єкт може заплутати, то такий об'єкт із множини можна називати точкою, пунктом, якось ще, але найчастіше його називають вершиною графа і позначають буквою V.
У програмуванні це зазвичай стовпець або рядок двовимірного масиву, де масив називається або матрицею суміжності або матрицею інцендентності.

У літературі, в інтернеті і взагалі скрізь, де щось написано про графи, ви зустрічатимете такі поняття, як дуги та ребра. На цьому малюнку зображено ребра графа. Тобто. це три ребра Е1, Е2 та Е3.

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

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

Ви часто зустрічатимете поняття суміжності та інцендентності. На малюнку червоним кольором відмічені два ребра, які йдуть в одну точку. Такі ребра, як і вищеописані вершини, також називаються суміжними.

Багато чого не описано, але ця частина інформації може бути комусь допоможе.

МУНІЦИПАЛЬНЕ АВТОНОМНЕ ЗАГАЛЬНООСВІТНИЙ ЗАКЛАД СЕРЕДНЯ ЗАГАЛЬНООСВІТНЯ ШКОЛА № 2

Підготував

Легкокінець Владислав, учень 10А класу

Практичне застосуванняТеорії Графів

Керівник

Л.І. Носкова, учитель математики

ст.Брюховецька

2011 р.

1.Введение………………………………………………………………………….………….3

2.Історія виникнення теорії графів………………………………………….………..4

3.Основні визначення та теореми теорії графів……………………………….………6

4.Завдання, що вирішуються за допомогою графів……………………………..……………………..8

4.1 Знамениті завдання………………………………….………………………...8

4.2 Декілька цікавих завдань………………………………….……………..9

5. Застосування графів у різних областяхжиття людей……………………………...11

6.Рішення задач……………………………………………………………………………...12

7. Висновок………………….…………………………………………………………….13

8. Список літератури………….……………………………………………………………14

9.Додаток…………………………………………………………………….…………15

Вступ

Народившись при вирішенні головоломок та цікавих ігор, Теорія графів стала в даний час простим, доступним і потужним засобом вирішення питань, що належать до широкого кола проблем. Графи буквально всюдисущі. У вигляді графів можна, наприклад, інтерпретувати схеми доріг та електричні ланцюги, географічні картита молекули хімічних сполук, зв'язки між людьми та групами людей. За останні чотири десятиліття теорія графів перетворилася на один з найбільш бурхливих розділів математики. Це викликано запитами області додатків, що стрімко розширюється. Застосовується при проектуванні інтегральних схем та схем управління, при дослідженні автоматів, логічних ланцюгів, блок-схем програм, в економіці та статистиці, хімії та біології, в теорії розкладів. Тому актуальністьтеми обумовлена з одного боку популярністю графів та пов'язаних з ними методів досліджень, а з іншого, не розроблена, цілісна системаїї реалізації.

Рішення багатьох життєвих завданьвимагає довгих обчислень, інколи ж і ці обчислення не приносять успіху. У цьому полягає проблема дослідження. Виникає питання: чи не можна для їх вирішення знайти просте, раціональне, коротке та витончене рішення. Чи спрощується вирішення завдань, якщо використовувати графи? Це визначило тему мого дослідження: «Практичне застосування теорії графів»

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

Гіпотеза дослідження.Метод графів дуже важливий і широко застосовується у різних галузях науки та життєдіяльності людини.

Завдання дослідження:

1.Вивчити літературу та ресурси мережі Інтернет з цієї проблеми.

2. Перевірити ефективність методу графів під час вирішення практичних завдань.

3. Зробити висновок.

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

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

Історія виникнення теорії графів

Родоначальником теорії графів прийнято вважати математику Леонарда Ейлера (1707-1783). Історію виникнення цієї теорії можна простежити з листування великого вченого. Ось переклад латинського тексту, який узятий з листа Ейлера до італійського математика та інженера Маріноні, відправленого з Петербурга 13 березня 1736 року.

"Колись мені було запропоновано завдання про остров, розташований у місті Кенігсберзі і оточений річкою, через яку перекинуто сім мостів.

[Додаток рис.1]Постає питання, чи може хтось безперервно обійти їх, проходячи тільки одного разу через кожен міст. І тут мені було повідомлено, що ніхто ще досі не міг це зробити, але ніхто і не довів, що це неможливо. Питання це, хоч і банальне, здалося мені, проте, вартим уваги тим, що для його вирішення недостатні ні геометрія, ні алгебра, ні комбінаторне мистецтво. Після довгих роздумів я знайшов легке правило, засноване на цілком переконливому доказі, за допомогою якого можна у всіх завданнях такого роду відразу ж визначити, чи може бути здійснений такий обхід через будь-яке число і як завгодно розташованих мостів або не може. Кенігсберзькі мости розташовані так, що їх можна представити на наступному малюнку [Додаток рис.2], де A позначає острів, а B ,C іD – частини континенту, відокремлені друг від друга рукавами річки

З приводу виявленого ним способу вирішувати завдання подібного роду Ейлер писав:

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

Тож чи можна обійти Кенігсберзькі мости, проходячи лише один раз через кожен із цих мостів? Щоб знайти відповідь, продовжимо листа Ейлера до Мариноні:

"Питання полягає в тому, щоб визначити, чи можна обійти всі ці сім мостів, проходячи через кожен тільки один раз, чи не можна. Моє правило призводить до наступного рішенняцього питання. Насамперед, потрібно дивитися, скільки є ділянок, розділених водою, – таких, які не мають іншого переходу з одного на інший, окрім як через міст. У даному прикладітаких ділянок чотири - A, B, C, D. Далі потрібно розрізняти, чи є кількість мостів, які ведуть до цих окремих ділянок, парних чи непарних. Так, у нашому випадку до ділянки A ведуть п'ять мостів, а до інших – по три мости, тобто число мостів, що ведуть до окремих ділянок, непарне, а цього вже достатньо для вирішення завдання. Коли це визначено, застосовуємо таке правило: якби кількість мостів, які ведуть до кожного окремій ділянці, було парним, то тоді обхід, про який йде мова, був би можливим, і в той же час можна було б почати цей обхід з будь-якої ділянки. Якщо ж із цих чисел два були б непарні, бо тільки одне бути непарним не може, то і тоді міг би відбутися перехід, як це наказано, але тільки початок обходу неодмінно має бути взято від однієї з тих ділянок, до яких веде не парне числомостів. Якби, нарешті, було більше двох ділянок, до яких веде непарна кількість мостів, то тоді такий рух взагалі неможливий… якщо можна було привести тут інші, більш серйозні завдання, цей метод міг би принести ще більшу користь і їм не слід було б нехтувати. .

Основні визначення та теореми теорії графів

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

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

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

Надалі вершини графа ми позначатимемо латинськими літерами A, B, C, D. Іноді граф загалом позначатимемо однією великою літерою.

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

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

Позначення: O "- граф з вершинами, що не має ребер

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

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

Визначення 5.Ступінню вершини називається число ребер, яким належить вершина.

Визначення 6.Граф, ступеня всіх k вершин якого однакові, називається однорідним графом ступеня .

Визначення 7.Доповненням даного графа називається граф, що складається з усіх ребер та їх кінців, які необхідно додати до вихідного графа, щоб отримати повний граф.

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

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

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

Визначення 10.Путемот A доX називається послідовність ребер, що веде від A до X така, що кожні два сусідні ребра мають загальну вершину, і ніяке ребро не зустрічається більше одного разу.

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

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

Визначення 13.Довжиною шляху , прокладеного на циклі , називається число ребер цього шляху.

Визначення 14.Дві вершини A і B у графі називаються зв'язковими, якщо в ньому існує (не існує) шлях, що веде з A в B .

Визначення 15.Граф називається зв'язковим, якщо кожні дві його вершини зв'язкові; якщо ж у графі знайдеться хоча б одна пара незв'язкових вершин, то граф називається незв'язним.

Визначення 16.Деревомназивається зв'язковий граф, що не містить циклів.

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

Визначення 17.Нескладний граф, що складається виключно з дерев, називається лісом.

Визначення 18.Дерево, всі n вершин якого мають номери від 1 до n називають деревом з перенумерованими вершинами.

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

Завдання розв'язувані за допомогою графів

Відомі завдання

Завдання комівояжера

Завдання комівояжера є одним із знаменитих завдань теорії комбінаторики. Вона була поставлена в 1934 році, і про неї обламували зуби найкращі математики.

Постановка завдання така.
Комівояжер (бродячий торговець) повинен вийти з першого міста, відвідати по разу у невідомому порядку міста 2,1,3..n і повернутися до першого міста. Відстань між містами відома. У якому порядку слід обходити міста, щоб замкнутий шлях (тур) комівояжера був найкоротшим?

Метод вирішення завдання комівояжера

Жадібний алгоритм "Йди в найближче (до якого ще не входило) місто".
"Жадібним" цей алгоритм названий тому, що на останніх кроках доводиться жорстоко розплачуватися за жадібність.
Розглянемо для прикладу мережу на малюнку [Додаток рис.3], що становить вузький ромб. Нехай комівояжер стартує з міста 1. Алгоритм “йди в найближче місто” виведе його до міста 2, потім 3, потім 4; на останньому кроці доведеться платити за жадібність, повертаючись довгою діагоналі ромба. В результаті вийде не найкоротший, а найдовший тур.

Завдання про Кенігсберзькі мости.

Завдання формулюється в такий спосіб.
Місто Кенігсберг розташоване на берегах річки Прегель та двох островах. Різні частини міста були з'єднані сімома мостами. У неділю городяни здійснювали прогулянки містом. Питання: чи можна здійснити прогулянку таким чином, щоб, вийшовши з дому, повернутися назад, пройшовши точно один раз по кожному мосту.
Мости через річку Прегель розташовані як на малюнку[Додаток Рис.1].

Розглянемо граф, який відповідає схемі мостів [Додаток рис.2].

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

Декілька цікавих завдань

1. "Маршрути".

Завдання 1

Як ви пам'ятаєте, мисливець за мертвими душамиЧичиков побував у відомих поміщиків одного разу в кожного. Він відвідував їх у такому порядку: Манилова, Коробочку, Ноздрьова, Собакевича, Плюшкіна, Тентетникова, генерала Бетрищева, Півня, Констанжолго, полковника Кошкарьова. Знайдено схему, на якій Чичиков накидав взаємне розташуваннямаєтків та путівців, що з'єднують їх. Встановіть, який маєток комусь належить, якщо жодної з доріг Чичиків не проїжджав більше одного разу [Додаток рис.4].

Рішення:

За схемою доріг видно, що подорож Чичиков почав з маєтку Е, а закінчив маєтком О. Зауважуємо, що в маєтки В і С ведуть лише дві дороги, тому цими дорогами Чичиков повинен був проїхати. Зазначимо їх жирною лінією. Визначено ділянки маршруту, що проходять через А: АС та АВ. Дорогами АЕ, АК та АМ Чичиков не їздив. Перекреслимо їх. Зазначимо жирною лінією ЕD; перекреслимо DK. Перекреслимо МО та МН; відзначимо жирною лінією MF; перекреслимо FO; відзначимо жирною лінією FH, НК та КО. Знайдемо єдино можливий за даної умови маршрут. І отримуємо: маєток Е – належить Манілову, D – Коробочці, С – Ноздрьову, А – Собакевичу, В – Плюшкіну, М – Тентетникову, F – Бетрищеву, Н – Півню, К – Констанжолго, Про – Кошкареву [Додаток рис.5].

Завдання 2

На малюнку зображено схему місцевості [Додаток рис.6].

Пересуватися можна лише у напрямку стрілок. У кожному пункті можна бути не більше одного разу. Скільки способами можна потрапити з пункту 1 до пункту 9? Який маршрут найкоротший і який найдовший.

Рішення:

Послідовно "розшаровуємо" схему в дерево, починаючи з вершини 1 [Додаток рис.7]. Отримаємо дерево. Число можливих способіввлучення з 1 до 9 дорівнює числу "висячих" вершин дерева (їх 14). Очевидно, найкоротший шлях-1-5-9; найдовший - 1-2-3-6-5-7-8-9.

2 "Групи, знайомства"

Завдання 1

Учасники музичного фестивалю обмінялися конвертами з адресами. Доведіть, що:

а) всього було передано парне число конвертів;

б) число учасників, які обмінялися конвертами непарне число разів, парно.

Рішення: Нехай учасники фестивалю А1, А2, А3. . . , А n – вершини графа, а ребра з'єднують пари вершин, що зображають хлопців, які обмінялися конвертами [Додаток рис.8]

Рішення:

а) ступінь кожної вершини А i показує кількість конвертів, які передав учасник А i своїм знайомим. Загальне числопереданих конвертів N дорівнює сумі ступенів усіх вершин графа N = степ. А 1+степ. А 2 + +. . . + Степ. А n –1 + степ. А n, N = 2p, де p - Число ребер графа, тобто. N – парне. Отже, було передано парне число конвертів;

б) рівності N = степ. А 1+степ. А 2 + +. . . + Степ. А n –1 + степ. А n сума непарних доданків має бути парною, а це може бути тільки в тому випадку, якщо число непарних доданків парне. І це означає, що кількість учасників, обмінялися конвертами непарне число раз, парне.

Завдання 2

Якось Андрій, Борис, Володя, Даша та Галя домовилися ввечері піти у кіно. Вибір кінотеатру та сеансу вони вирішили узгодити телефоном. Було також вирішено, що якщо з кимось зателефонувати не вдасться, то похід у кіно скасовується. Увечері біля кінотеатру зібралися не всі, тож відвідування кіно зірвалося. Наступного дня почали з'ясовувати, хто комусь дзвонив. Виявилося, що Андрій дзвонив Борису та Володі, Володя дзвонив Борису та Даші, Борис дзвонив Андрію та Даші, Даша дзвонила Андрію та Володі, а Галя дзвонила Андрію, Володі та Борису. Хто не зумів зателефонувати і тому не прийшов на зустріч?

Рішення:

Намалюємо п'ять точок та позначимо їх літерами А, Б, В, Г, Д. Це перші літери імен. З'єднаємо ті точки, які відповідають іменам хлопців, що зізвонилися.

[Додаток рис.9]

З малюнка видно, що кожен із хлопців – Андрій, Борис та Володя – зателефонували з усіма іншими. Тому ці хлопці й дійшли кінотеатру. А Галя та Даша не зуміли зателефонувати між собою (точки Г і Д не з'єднані відрізком) і тому відповідно до домовленості в кіно не прийшли.

Застосування графів у різних сферах життя людей

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

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

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

Молекулярні графи та дерева: [Додаток рис.10]а, б - мультиграфи соотв. етилену та формальдегіду; в-мовляв. ізомерів пентану (дерева 4, 5 ізоморфні дереву 2).

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

Білкові мережі

Білкові мережі - групи фізично взаємодіючих білків, які функціонують у клітині спільно та скоординовано, контролюючи взаємопов'язані процеси, що відбуваються в організмі [Додаток рис. 11].

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

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

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

Приклад генеалогічного дерева моєї родини [Додаток рис.12].

Ще один приклад. На малюнку показано біблійне генеалогічне дерево [Додаток рис.13].

Розв'язання задач

1.Транспортне завдання. Нехай у місті Краснодарі знаходиться база з сировиною, яку потрібно розвести по містах Кримськ, Темрюк, Слов'янськ-на-Кубані та Тимашевську одним заїздом, витративши при цьому якнайменше часу та палива і повернувшись назад до Краснодара.

Рішення:

Для початку складемо граф усіх можливих шляхівпроїзду [Додаток рис.14]з огляду на реальні дороги між даними населеними пунктами та відстань між ними. Для вирішення цього завдання нам потрібно буде скласти ще один граф, деревоподібний [Додаток рис.15].

Для зручності рішення позначаємо міста цифрами: Краснодар – 1, Кримськ – 2, Темрюк – 3, Слов'янськ – 4, Тимашевськ – 5.

У результаті вийшло 24 рішення, але нам потрібні лише найкоротші шляхи. З усіх рішень задовольняють лише два, це 350 км.

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

Логічне завдання на переливання.У відрі 8 л води і є дві каструлі ємністю 5 і 3 л. потрібно відлити в п'ятилітрову каструлю 4 л води та залишити у відрі 4 л, тобто розлити воду порівну у відро та велику каструлю.

Рішення:

Ситуацію у кожен момент можна описати трьома числами [Додаток рис.16].

В результаті отримуємо два рішення: одне в 7 ходів, інше в 8 ходів.

Висновок

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

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

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

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

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

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

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

Література

Берж До.Теорія графів та її застосування. -M.: ІІЛ, 1962.

Кемені Дж., Снелл Дж., Томпсон Дж.Введення у кінцеву математику. -M.: ІІЛ, 1963.

Оре О.Графи та їх застосування. -M.: Світ, 1965.

Харарі Ф.Теорія графів. -M.: Світ, 1973.

Зиков А.А.Теорія кінцевих графів. -Новосибірськ: Наука, 1969.

Березіна Л.Ю.Графи та їх застосування. -M.: Просвітництво, 1979. -144 с.

"Соросівський освітній журнал" №11 1996 (ст. "Плоскі графи");

Гарднер М. "Математичні дозвілля", М. "Світ", 1972 (глава 35);

Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Старовинні цікаві завдання", М. "Наука", 1988 (частина 2, розділ 8; додаток 4);

прикладна програма

Рис. 6

Рис. 7

Рис. 8

ридання

прикладна програма

Рис. 14

ридання

прикладна програма

Книга К.Бержа – перша з теорії графів російською мовою. Тим часом у останні рокиінтерес до теорії різко посилився як з боку математиків, так і представників самих різних дисциплін. Це тим, що методи теорії графів успішно вирішують численні завдання теорії електричних ланцюгів, теорії транспортних ланцюгів, теорії інформації, кібернетики та ін.
У книзі Бержа теорія графів викладається послідовно, починаючи з основ. Передбачається, що читач має дуже скромні математичні знання, хоча і має деяку математичну культуру. У текст включені численні, часто кумедні, приклади. Книжку можна використовувати для початкового вивчення теорії графів. Математики-професіонали також знайдуть у ній багато цікавого.

Алгорифм для безпосереднього виявлення ейлерового циклу.
[Флерн (Fleury)]. Розглянемо зв'язковий мультиграф G, усі вершини якого мають парний ступінь, і постараємося намалювати його одним розчерком, не вдаючись у процесі побудови до виправлень вже накресленої частини траєкторії. Достатньо дотримуватися наступного правила:
1 Виходимо з довільної вершини а; кожне пройдене ребро закреслюємо.
2 Ніколи не йдемо по такому ребру і, яке в даний момент є перешийком (тобто при видаленні якого граф, утворений незакресленими ребрами, розпадається на дві компоненти зв'язності, що мають хоча б по одному ребру),

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

Зміст
Вступ
Глава 1. Основні визначення
Множини та багатозначні відображення
Граф. Шляхи та контури
Ланцюги та цикли
Глава 2. Попереднє вивчення квазіупорядкованості
Квазіпорядок, що визначається графом
Індуктивний граф та бази
Глава 3. Порядкова функція та функція
Гранді для нескінченного графа
Загальні міркування щодо нескінченних графів
Порядкова функція
Функції гранді
Операції над графами
Глава 4. Основні числа теорії графів
Цикломатичне число
Хроматичне число
Число внутрішньої стійкості
Число зовнішньої стійкості
Розділ 5. Ядра графа
Теореми існування та єдиності
Додаток до функцій Гранді
Розділ 6. Ігри на графі
Гра Нім
Загальне визначення гри (з повною інформацією)
Стратегії
Глава 7. Завдання про найкоротший шлях
Процеси за етапами Деякі узагальнення
Глава 8. Транспортні мережі
Завдання про найбільший потік Завдання про найменший потік
Завдання про потік, сумісний з безліччю значень
Нескінченні транспортні мережі
Глава 9. Теорема про напівступеня
Півступеня результату та заходу
Глава 10. Пароспоєднання простого графа
Завдання про найбільше паросполучення
Дефіцит простого графа
Угорський алгоритм
Узагальнення на нескінченний випадок
Додаток до теорії матриць
Розділ 11. Фактори
Гамільтонові шляхи та гамільтонові контури
Знаходження фактора
Знаходження часткового графа із заданими напівступенями
Розділ 12. Центри графа
Центри
Радіус
Розділ 13. Діаметр сильно зв'язного графа
Загальні властивості сильно зв'язкових графів без петель
Діаметр
Глава 14. Матриця суміжності графа
Застосування звичайних матричних операцій
Завдання на підрахунок
Завдання про лідера
Застосування булевих операцій
Розділ 15. Матриці інцидентів
Цілком унімодулярні матриці
Цілком унімодулярні системи
Цикломатичні матриці
Глава 16. Дерева та прадерева
Дерева
Аналітичне дослідження
Прадерева
Розділ 17. Завдання Ейлера
Ейлерові цикли Ейлерові контури
Глава 18. Паросопоєднання довільного графа
Теорія ланцюгів, що чергуються.
Знаходження часткового графа із заданими ступенями вершин
Досконале паросполучення
Додаток до внутрішньої стійкості
Глава 19. Фактороїди
Гамільтонові цикли та фактороїди
Необхідне та достатня умоваіснування фактороїду
Глава 20. Зв'язність графа
Точки зчленування
Графи без зчленувань
h-зв'язкові графи
Розділ 21. Плоскі графи
Основні властивості
Узагальнення
Додавання
I. Off загальної теорії, ігор
ІІ. Про транспортні завдання
ІІІ. Про використання, поняття потенціалу у транспортних мережах
IV. Невирішені завдання та недоведені припущення
V. Про деякі основні принципи підрахунку (Ж. Рига)
VI. Доповнення до російського перекладу (А.А. Зиков та Г.І. Кожухін)
Література
Теорія графів та книга К. Бержа (післямова до російського перекладу)
Вказівник символів
Іменний покажчик
Предметний покажчик.

Безкоштовно завантажити електронну книгуу зручному форматі, дивитися та читати:
Скачати книгу Теорія графів та її застосування, Берж К. - fileskachat.com, швидке та безкоштовне скачування.

ВОЛОДИМИРСЬКИЙ ДЕРЖАВНИЙ ПЕДАГОГІЧНИЙ УНІВЕРСИТЕТ

РЕФЕРАТ

«ТЕОРІЯ ГРАФІВ»

Виконала:

Зудіна Т.В.

Володимир 2001

1. Введення

2. Історія виникнення теорії графів

3. Основні визначення теорії графів

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

5. Завдання застосування теорії графів

6. Застосування теорії графів у шкільному курсіматематики

7. Додаток теорії графів у різних галузях науки та техніки

8. Останні досягненнятеорії графів

§1. ІСТОРІЯ ВИНИКНЕННЯ ТЕОРІЇ ГРАФІВ.

Родоначальником теорії графів прийнято вважати математику Леонарда Ейлера (1707-1783). Історію виникнення цієї теорії можна простежити з листування великого вченого. Ось переклад латинського тексту, який взятий з листа Ейлера до італійського математика та інженера Маріноні, відправленого з Петербурга 13 березня 1736 [див. стор 41-42]:

"Колись мені було запропоновано завдання про острів, розташований у місті Кенігсберзі і оточений річкою, через яку перекинуто сім мостів. Запитується, чи може хтось безперервно обійти їх, проходячи тільки одного разу через кожен міст. І тут же мені було повідомлено, що ніхто ще досі не міг це зробити, але ніхто й не довів, що це неможливо… Питання це, хоч і банальне, здалося мені, однак, вартим уваги тим, що для його вирішення недостатні ні геометрія, ні алгебра, ні комбінаторне мистецтво… Після довгих роздумів я знайшов легке правило, засноване на цілком переконливому доказі, за допомогою якого можна у всіх завданнях такого роду відразу визначити, чи може бути здійснений такий обхід через будь-яке число і як завгодно розташованих мостів чи не може. так, що їх можна уявити на наступному малюнку[Рис.1] , на якому A позначає острів, а B , C іD – частини континенту, відокремлені друг від друга рукавами річки. Сім мостів позначені літерами a , b , c , d , e , f , g ".

(МАЛЮНОК 1.1)

З приводу виявленого ним способу вирішувати завдання подібного роду Ейлер писав [див. стор 102-104]:

"Питання полягає в тому, щоб визначити, чи можна обійти всі ці сім мостів, проходячи через кожен лише один раз, чи не можна. Моє правило призводить до наступного вирішення цього питання. Насамперед, потрібно дивитися, скільки є ділянок, розділених водою, – таких , у яких немає іншого переходу з одного на інший, окрім як через міст. A , B , C , D . Далі потрібно розрізняти, чи є кількість мостів, які ведуть до цих окремих ділянок, парних чи непарних. Так, у нашому випадку до ділянки A ведуть п'ять мостів, а до інших – по три мости, тобто число мостів, що ведуть до окремих ділянок, непарне, а цього вже достатньо для вирішення завдання. Коли це визначено, застосовуємо таке правило: якби число мостів, що ведуть до кожної окремої ділянки, було парним, то обхід, про який йдеться, був би можливий, і водночас можна було б розпочати цей обхід з будь-якої ділянки. Якщо ж із цих чисел два були б непарні, бо тільки одне бути непарним не може, то й тоді міг би відбутися перехід, як це наказано, але тільки початок обходу неодмінно має бути взято від однієї з тих ділянок, до яких веде непарне число мостів. Якби, нарешті, було більше двох ділянок, до яких веде непарна кількість мостів, то тоді такий рух взагалі неможливий… якщо можна було привести тут інші, більш серйозні завдання, цей метод міг би принести ще більшу користь і їм не слід було б нехтувати. .

Обгрунтування вищенаведеного правила можна знайти у листі Л. Ейлера до свого друга Елер від 3 квітня того ж року. Ми перекажемо нижче уривок із цього листа.

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

Історія з мостами міста Кенігсберг має сучасне продовження. Відкриємо, наприклад, шкільний підручник з математики за редакцією Н.Я. Віленкіна для шостого класу. У ньому на сторінці 98 у рубриці розвитку уважності та кмітливості ми знайдемо завдання, що має безпосереднє відношення до тієї, яку колись вирішував Ейлер.

Завдання № 569. На озері є сім островів, які з'єднані між собою так, як показано на малюнку 1.2. На який острів повинен доставити мандрівників катер, щоб вони могли пройти по кожному мосту і лише один раз? Чому не можна доставити мандрівників на острів A ?

(МАЛУНОК 1.2)

Рішення.Оскільки це завдання подібне до завдання про Кенігсберзьких мостах, то при її вирішенні ми також скористаємося правилом Ейлера. В результаті отримаємо наступну відповідь: катер повинен доставити мандрівників на острів Eабо Fщоб вони змогли пройти по кожному мосту один раз. З того ж правила Ейлера випливає неможливість необхідного обходу, якщо він розпочнеться з острова A .

На закінчення зазначимо, що завдання про Кенігсберзькі мости і подібні до неї завдання разом із сукупністю методів їх дослідження становлять дуже важливе значення. практичному відношенніРозділ математики, званий теорією графів. Перша робота про графи належала Л. Ейлер і з'явилася в 1736 році. Надалі над графами працювали Кеніг (1774–1833), Гамільтон (1805–1865), із сучасних математиків – К. Берж, О. Оре, А. Зиков.

§2. ОСНОВНІ ТЕОРЕМИ ТЕОРІЇ ГРАФІВ

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

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

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

(МАЛУНОК 2.1)

Надалі вершини графа ми позначатимемо латинськими літерами A , B ,C ,D. Іноді граф загалом позначатимемо однією великою літерою.

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

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

Позначення: O " - Граф з вершинами, що не має ребер (рис. 2.2).

(МАЛУНОК 2.2)

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

Позначення: U " – граф, що складається з nвершин і ребер, що з'єднують різні пари цих вершин. Такий граф можна уявити як n-кутник, в якому проведено всі діагоналі (рис. 2.3).

(МАЛУНОК 2.3)

Визначення 2.05. ступенем вершининазивається число ребер, яким належить вершина.

Позначення: p (A) – ступінь вершини A . Наприклад, малюнку 2.1: p (A)=2, p (B)=2, p (C)=2, p (D)=1, p (E)=1.

Визначення 2.06.Граф, ступеня всіх kвершин якого однакові, називається однорідним графом ступеня k .

На малюнку 2.4 та 2.5 зображені однорідні графи другого та третього ступеня.

(МАЛУНОК 2.4 та 2.5)

Визначення 2.07. Доповненням даного графаназивається граф, що складається з усіх ребер та їх кінців, які необхідно додати до вихідного графа, щоб отримати повний граф.

На малюнку 2.6 зображено вихідний граф G , що складається з чотирьох вершин та трьох відрізків, а на малюнку 2.7 – доповнення даного графа – граф G " .

(МАЛУНОК 2.6 та 2.7)

Ми бачимо, що малюнку 2.5 ребра ACі BDперетинаються в точці, яка не є вершиною графа. Але трапляються випадки, коли цей граф необхідно подати на площині у такому вигляді, щоб його ребра перетиналися лише у вершинах (це питання буде розглянуто докладно далі, у параграфі 5).

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

Наприклад, малюнку 2.8 показаний плоский граф, ізоморфний (рівний) графу малюнку 2.5. Проте, зауважимо, що кожен граф є плоским, хоча зворотне твердження правильне, т. е. будь-який плоский граф можна у звичайному вигляді.

(МАЛУНОК 2.8)

Визначення 2.09.Багатокутник плоского графа, що не містить у собі ніяких вершин або ребер графа, називають його гранню .

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

Що таке граф

Часто для опису будови систем використовують графічні схеми. Елементи в них зображують кружками, крапками, квадратами тощо, а зв'язки між елементами – лініями чи стрілками. У цьому ні те, як зображуються елементи, ні довжина чи форма ліній не важливі - має значення лише, які з'єднані. Отже, граф - це пара виду (A, M), де A - кінцева множина вершин, а M - множина ребер - ліній, що зв'язують деякі вершини.

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

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

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

Якщо вершини a і b - кінці ребра (або початок і кінець дуги) графа, то кажуть, що вершини a і b інцидентні цьому ребру (дузі), також ребро (дуга) інцидентно вершинам a і b. Якщо вершини a і b - кінці ребра, всі вони (a і b) називаються суміжними.

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

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

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

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

Кожна вершина орграфа характеризується:

Напівступенем результату. Це кількість дуг, що виходять із неї.
Напівступенем заходу. Це кількість дуг, які входять у цю вершину.

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

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

Вершина зі ступенем 0 називається ізольованою.

Висячою вершиною є вершина зі ступенем 1.

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

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

Графи: ізоморфізм

Поняття ізоморфізму використовується в математиці. Зокрема, теорія графів визначає його так: два графи U і V ізоморфні, якщо в цих графах існує бієкція між множинами їх вершин: кожні 2 вершини у графі U з'єднані ребром у тому і тільки тому випадку, якщо у графі V пов'язані ребром ті ж самі вершини (які можуть інакше називатися). На малюнку нижче показані два ізоморфні графи, в яких між вершинами, забарвленими в однакові кольори і в першому, і в другому графі, існує вищеописана біекція.

Шляхи та цикли

Шляхом у неорієнтованому чи орієнтованому графі є послідовність ребер, де кожне наступне починається у вершині, у якій закінчується попереднє. Простий шлях - такий, у якому всі вершини, виключаючи, можливо, початкову і кінцеву, і ребра різні. Циклом в орграфі називається шлях, у якого збігаються початкова і кінцева вершини і включає не менше одного ребра. Циклом у неорієнтованому графіє шлях, який містить не менше трьох різних ребер. На другому малюнку циклом є, наприклад, шлях (3, 1), (6, 3), (1, 6).

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