Фігура утворена кінцевим набором точок площини і відрізків, з'єдную-щих деякі з цих точок, називається плоским графом. або просто графом (рис. 2.1, а). Точки називаються вершинами. а відрізки - ребрами графа.
Замість відрізків як ребер графів розглядаються також криві лінії на площині (рис. 2.1, б).
Прикладами графів можуть служити схеми метрополітену, залізничних і шосейних доріг, плани виставок і т.д. За допомогою графів вказуються різні зв'язки між об'єктами.
Історично склалося так, що теорія графів зародилась в ході рішення головоломок двісті з гаком років тому.
Однією з таких задач-головоломок була задача про кенігсберзькими мостах, яка привернула до себе увагу Леонарда Ейлера (1707-1783), який тривалий час жив і працював у Росії (з 1727 по 1741 рік і з 1766 до кінця життя).
Завдання. В м Кенігсберзі (нині Калінінград) було сім мостів через річку Прегель (рис. 2.2, де Л - лівий берег, П - правий берег, А і Б - острова). Завдання полягало в наступному: чи можна, прогулюючись по місту, пройти через кожен міст рівно один раз?
Це завдання пов'язана з іншими головоломками, суть яких укладаючи-лась в тому, щоб обвести контур деякої фігури, не відриваючи Каранда-ша від паперу і не обводячи жодної лінії контуру двічі, тобто "Намалюй-вать одним розчерком". Такі контури утворюють так звані унікур-сальні графи.
Задачі про Кенігсбергськая мостах Л. Ейлер присвятив ціле досліджень-ня, яке в 1736 році було представлено в Петербурзьку Академію наук.
На малюнку 2.3 зображений граф, відповідний завданню про Кенигс-Бергський мостах. Потрібно довести, що цей граф є унікур-сальним.
Для цього розглянемо поняття індексу вершини - число ребер графа, що сходяться в даній вершині, і доведемо, що має місце наступна теорема.
Теорема. Для унікурсального графа число вершин непарного індексу дорівнює нулю або двом.
Доведення. Дійсно, якщо граф унікурсален і його початок не збігається з кінцем, то початок і кінець є єдиними вершинами непарного індексу. Решта вершини мають парний індекс, так як в кожну точку ми входимо і виходимо з неї. Якщо початок збігається з кінцем, то вершин з непарним індексом немає.
Приступимо тепер до вирішення завдання. Визначимо парність вершин гра-фа на малюнку 2.3. Вершина А має індекс 5, Б - 3, П - 3 і Л - 3. Таким чином, ми маємо чотири вершини непарного індексу, і, таким чи-тельно, даний граф не є унікурсальним. Звідси отримуємо, що під час прогулянки по місту не можна пройти по кожному з семи мостів тільки один раз.
1. Намалюйте графи, у яких є вершини індексів 1, 2, 3 і 4.
2. Намалюйте граф, в якому кожна вершина має індекс, що дорівнює: а) двох; б) трьом; в) чотирьох.
3. Доведіть, що в будь-якому графі сума індексів усіх його вершин - число парне, рівне подвоєному числу ребер графа. Виведіть з цього, що число вершин з непарними індексами парне.
4. У графі 6 вершин, кожна з яких має індекс 3. Скільки у нього ребер? Намалюйте такий граф.
5. У графі 5 вершин, кожна з яких має індекс 4. Скільки у нього ребер? Намалюйте такий граф.
6. Чи можна поєднати сім точок відрізками так, щоб кожна точка була сполучена рівно з: а) двома; б) трьома; в) чотирма; г) п'ятьма іншими?
7. Сформулюйте і вирішите завдання, двоїсті завданням 5.
8. В офісі 15 комп'ютерів. Чи можна поєднати їх один з одним так, щоб кожен був з'єднаний рівно з трьома іншими?
9. У державі 100 міст. З кожного міста виходить чотири дороги. Скільки всього доріг в державі?
10. Визначте, які графи, зображені на малюнку 2.4, є унікурсальнимі?
11. Доведіть, що у всякому графі, ребрами якого є відрізки, знайдуться, принаймні, дві вершини однакового індексу.
12. Яке найменше число мостів в завданню про Кенігсбергськая мостах доведеться пройти двічі, щоб пройти по кожному мосту?
13. Доведіть, що якщо в задачі про Кенігсбергськая мостах додати ще один міст в будь-якому місці річки Прегель, то отриманий граф буде унікурсальним.