Багато найрізноманітніших задач природньо формулюються у термінах точок та зв'язків між ними, тобто в термінах теорії графів. Так, наприклад, можуть бути сформульовані задачі про складання розкладу, аналізу схем у електротехніці, встановлення структури молекул у органічній хімії тощо. Також теорія графів може бути використана для розв'язання деяких головоломок. До однієї з них відноситься відома задача про кенігсберзькі мости. Її можна сформулювати наступним чином:[2]
На річці Преголя у Кенігсберзі (тепер місто Калінінград) було два острови. Вони з'єднувалися між собою та з берегами річки сімома мостами, як показано на малюнку 1.
мал. 1
Задача полягає у тому, щоб, почавши рух з одного з чотирьох ділянок суходолу (помічених на малюнку літерами А, В, С, D), тільки один раз пройти по кожному мосту і знову повернутися у вихідну точку, тобто визначити замкнений маршрут через всі сім мостів, двічі не перетинаючи жоден з них.
Багато людей було переконані, що ця задача немає розв'язку. Однак лише у 1736 році великий швейцарський математикЕйлер виклав свої думки з приводу розв'язання цієї задачі і тим самим заклав основу теорії графів. Ейлер був першим, хто показав, що ця задача еквівалентна створенню замкненого ланцюга вздовж ребер графа,
мал. 2
в якому вершини А, В, С, D являють собою ділянки суші, а ребра - мости, що з'єднують ці ділянки. Такі графи почали називати ейлеровими. Більш детально ми розглянемо ейлерові графи пізніше. Розв'язання задачі буде подано пізніше, а поки що можете самостійно спробувати її розв'язати.
У 1859 році інший відомий математик - сер Уільям Гамільтон - придумав гру, у якій треба було обійти замкнений контур всіх ребер додекаедра, проходячи через кожну вершину лише один раз.[2]
мал. 3
Можно перевірити послідовність вершин 1, 2, ..., 20, 1 утворюють такий цикл у графі. Гамільтонові графи будемо розглядати пізніше.
мал. 4
Отже, що ж таке граф?
Граф являє собою непорожню множину точок та множину дуг, обидва кінці яких належать заданій множині точок.
Прикладами графів можуть бути схема метрополітена, схеми залізничних та шосейних доріг, структурні формули молекул, плани виставок та інше, тобто, схеми і плани (чи карти) без масштабу, які показують лише зв'язки між об'єктами.
При зображенні графів на малюнках чи схемах відрізки дуги можуть бути прямолінійними чи криволінійними; довжини дуг та розташування точок є довільним.
Точки інакше називають вершинами; дуги - ребрами (дугами) графа. Вершини графа на малюнку виділяються зазвичай кругами хоча б тому, що не всі точки перетину ребер є вершинами графа. Наприклад, за умовою на малюнку 3 точка перетину діагоналей чотирикутника не є вершиною.
мал. 5
Граф називається повним, якщо кожні дві різні вершини з'єднані одним і тільки одним ребром.
Наприклад, граф на малюнку 5 є повним.
Завдання:
1. Чи є графи, зображені на малюнках 1 і 2, повними? Чому?
2.Намалюйте повний граф з n вершинами, якщо: а) n=2, б) n=3, в) n=5.
У повному графі кожна його вершина належить одному і тому же числу ребер. Подумайте, чому.
Отже, для задання повного графа достатньо знати число його вершин.
Завдання:
3. Скільком ребрам належить вершина у повному графі з n вершинами: а) n=3, б) n=5, в) n=k ?
4. Чи існує повний граф з сімома ребрами? Чому?
У довільному графі вершини у графі можут відрізнятися одна від одної тим, скільком ребрам вони належать.
Степенем вершини називається число ребер графа, яким ця вершина належить.
Для останнього графа степінь кожної вершини дорівнює «3».
Завдання:
5. Визначте степені кожної вершин графів, зображених на малюнках 1 та 2.
6. Чи знайдеться граф з п’ятьома вершинами, у якого одна вершина ізольована, а інша – має степень 4?
7. Чи знайдеться граф з п’ятьома вершинам, степені яких всі різні між собою, тобто рівні 0, 1. 2, 3, 4?
8. Якщо у графі з п’ятьома вершинами рівно дві вершини мають однакову степінь, то чи можуть вони бути обидві ізольовані чи обидві мати степінь 4.
Розглянемо наступну задачу.
У місті Маленьке 15 телефонів. Чи можна їх з'єднати дротами так, щоб кожний телефон був з'єднаний рівно з п'ятьома іншими?
Розв'яжемо її.
Припустимо, що можливо таке з'єднання. Розглянемо тоді граф, вершини якого відповідають телефонам, а ребра - з'єднувальним дротам. У цьому графі 15 вершин, степінь кожної дорівнює п'яти. Підрахуємо кількість ребер у цьому графі. Для цього спочатку просумуємо степені усіх його вершин. Зрозуміло, що при такому підрахунку кожне ребро враховано двічі ( воно ж з'єднує дві вершини!). Тому число ребер графа повинно дорівнювати 15*5/2. Але це число неціле! Отже, такого графа не існує, а отже, і з'єднати телефони таким чином не можливо.
При розв'язуванні задачі ми виявили, як підрахувати кількість ребер графа, знаючи степені усіх його вершин. Для цьоготреба просумувати степені вершин та отриманий результат поділити на 2.
Завдання:
9. У державі 100 міст, та з кожного з них виходить 4 дороги. Скільки всього доріг у державі?
Відмітимо тепер отримане твердження: сума степенів усіх вершин графа повинна бути парною (інакше її не можна було б розділити на два націло) і дорівнювати подвійній кількості ребер.
Дамо наступні означення:
Вершина графа, що має непарну степінь, називається непарною, а та, що має парну степінь - парною.
Наслідок. Кількість непарних вершин будь-якого графа - парна.
Для доведення цього наслідку залишилось відмітити, що сума деяких цілих чисел парна тоді і тільки тоді, коли кількість непарних доданків у цій сумі парна.
Немає коментарів:
Дописати коментар