ГАМІЛЬТОНОВІ ШЛЯХИ І КОНТУРИ
Визначення графа
У математичній теорії графів та інформатики граф - це сукупність непорожньої множини вершин і безлічі пар вершин (зв'язків між вершинами).
Об'єкти видаються як вершини, чи вузли графа, а зв'язку — як дуги, чи ребра.
ПЛОСЬКІ ГРАФИ
Граф, який можна зобразити на площині без перетину ребер поза вершинами, називається плоским топологічним графом.
Область площини, обмежена ребрами і містить вершин чи ребер, називається гранню графа.
Формула Ейлера. Якщо зв'язковий плоский топологічний граф має n вершин, m ребер і f граней, то n-m+f=2.
На географічній карті (беремо за ребра ділянки кордонів держав, а вершини - їх стики).
Ейлерові графи
Ейлеровим шляхом у графі називається шлях, що містить усі ребра графа. Граф називається ейлеровим, якщо існує замкнутий ланцюг, що проходить через кожне його ребро. Такий ланцюг називається ейлеровим ланцюгом. Зазначимо, що у цьому визначенні потрібно, щоб кожне ребро відбувалося лише один раз. Якщо зняти обмеження на замкнутість ланцюга, то граф називається напівейлеровим, причому кожен ейлерів граф буде напівейлеровим.
Приклади.
Завдання з ейлеровими графами часто зустрічаються в книгах з цікавої математики - наприклад, чи можна намалювати якусь діаграму, не відриваючи олівця від паперу і не проходячи жодну лінію двічі. Назва "ейлерів" виникла у зв'язку з тим, що Ейлер першим вирішив знамените завдання про Кенігсберзькі мости, в якій потрібно було дізнатися, чи має граф, зображений на малюнку, ейлерову ланцюг (не має!).
У 1736 р. великий Леонард Ейлер (1707-1783), понад 30 років працював у Петербурзькій Академії наук(1727-1741, 1766-1783) знайшов рішення головоломки про кенігсберзьких мостах. Справа в тому, що в Кенігсберзі було два острови, з'єднані сімома мостами з берегами річки Прегель і між собою (рис.15). Мешканці міста мріяли знайти замкнутий маршрут прогулянки всіма мостами, але їхні спроби були безуспішними.
Рис.15
Для того, щоб відволіктися від краси природи та архітектури, Ейлер малює мультиграф (рис.16) і, поряд з поставленим завданням, ставить питання про можливість намалювати цю фігуру, не відриваючи пера від паперу і не проводячи ліній двічі.
Рис.16
Ланцюг, що проходить через усі вершини графа тільки по одному разу, називають ейлеровим (відповідний замкнутий ланцюг називається ейлеровим циклом).
Результат Ейлера практично став наріжним каменем топології та теорії графів. Область його застосування - від пошуку маршруту виставковими залами Ермітажу до психологічних тестів та конструювання комп'ютерів.
ГАМІЛЬТОНОВІ ШЛЯХИ ТА КОНТУРИ
У 1857 р. ірландський математик Вілльям Гамільтон (1805-1865) запропонував гру "подорож додекаедром" (рис.14а), де потрібно було прогулятися по ребрах через всі вершини, не потрапляючи в жодну з них двічі (додекаедр - багатогранник, гран якого служать п'ятикутники - 20 вершин та 30 ребер). За бажання додекаедр можна (вирізавши грань АBCDE) розгорнути на площині (рис.14b) і виявити досить простий порядок переходу (рис.14с).
Рис.14
Шлях, що проходить через усі вершини графа лише по одному разу, називається гамільтоновим. Якщо він замкнутий (кінець шляху збігається з його початком, говорять про гамільтоновий контур.
У повному графі (будь-яка пара вершин з'єднана шляхом хоча б в одному напрямку) завжди є гамільтонів шлях
Ейлерові тагамільтонові шляхи подібні за способом завдання. Перші містять усі ребра, по одному разу кожну, другі – всі вершини, по одному разу кожну. Але, незважаючи на зовнішню подібність, завдання їх пошуку різко відрізняються за ступенем складності. Для вирішення питання про наявність ейлерового циклу у графі достатньо з'ясувати, чи всі його вершини парні. Критерій існування гамільтонова циклу в довільному графі ще знайдено.
Орграф
Орієнтований граф (короткоорграф ) — (мульти) граф, ребрам якого присвоєно напрямок. Спрямовані ребра іменуються такождугами, а деяких джерелах (Оре) і просто ребрами.
Існує велика кількість завдань, які вирішуються на орграфах. Найчастіше розглядаються завдання про досяжність (тобто про існування шляху, що пов'язує дві задані вершини), про знаходження шляхів, що мають будь-яку екстремальну характеристику (наприклад, найкоротший, або найбільш надійний шлях), про випадкові блукання, потокове завдання. Всі вони добре вивчені та розроблені ефективні алгоритми їх вирішення. У цьому передбачається, що це шляхи на графі є допустимими, тобто. не накладається жодних обмежень на досяжність.
Найбільш відомі роботи в цій галузі належать Крістофідес Н., Басакер Р.Д., Харарі Ф., Бержу К., Дейкстре Е., Флойд Р., Замбіцький Д.К., Оре О., Сааті Т., Фалкерсон Д. Р., Форду Л.Р.
На відміну класичного підходу, Басанговой Е.О. та Єрусалимським Я.М. було запроваджено поняття орієнтованих графів з нестандартною досяжністю, тобто. орграфів, у яких на допустимі шляхи накладаються будь-які обмеження. У звичайному орієнтованому графі, щоб одна вершина була досяжна з іншого, необхідне існування шляху, який зв'язує ці дві вершини. У разі ж орграфів знестандартною досяжністю потрібно, крім того, щоб цей шлях задовольняв певну умову (обмеження). Зрозуміло, що в цьому випадку класичні алгоритми розв'язання задач на графах безпосередньо не застосовуються.
Орієнтований граф (скорочено орграф) G — це впорядкована пара G: = (V,A), для якої виконані такі умови:
V це безліч вершин або вузлів,
A це безліч (упорядкованих) пар різних вершин, званих дугами або орієнтованими ребрами.
Дуга - це впорядкована пара вершин (v, w), де вершину v називають початком, а w - кінцем дуги. Можна сміливо сказати, що дуга v w веде від вершини v до вершини w.
Формально, орграф D = (V, E) є безліч E упорядкованих пар вершин.
Дуга інцидентна вершин u та v. У цьому кажуть, що u — початкова вершина дуги, а v — кінцева вершина.
Орграф, отриманий з простого графа (Простий граф - граф, в якому немає кратних ребер і петель) орієнтацією ребер називається спрямованим. На відміну від останнього, у довільному простому орграфі дві вершини можуть з'єднуватися двома різноспрямованими дугами.
Спрямований повний граф називається турніром. Повний граф - простий граф, у якому кожна пара різних вершин суміжна. Повний граф із n вершинами має n(n − 1) / 2 ребер і позначається Kn. p align="justify"> Є регулярним графом ступеня n - 1.
Зв'язкість
Маршрутом в орграфі називають послідовність вершин і дуг, що чергується, виду v0v1v2 ... vn (вершини можуть повторюватися). Довжина маршруту – кількість дуг у ньому.
Шлях є маршрут в орграфі без дуг, що повторюються, простий шлях - без повторюваних вершин. Якщо існує шлях з однієї вершини до іншої, то друга вершина досяжна з першої.
Контур є замкнутий шлях.
Длянапівмаршрута знімається обмеження на напрямок дуг, аналогічно визначаються напівшлях та напівконтур.
Орграф сильно зв'язний, або просто сильний, якщо всі його вершини взаємно досяжні; односторонньо зв'язковий, або просто односторонній якщо для будь-яких двох вершин, принаймні одна досяжна з іншої; слабко зв'язковий, або просто слабкий, якщо при ігноруванні напряму дуг виходить зв'язковий (мульти)граф;
Максимальний сильний підграф (Підграф вихідного графа - граф, що містить деяке підмножина вершин даного графа і всі ребра, інцидентні даному підмножині. ; (Орграф називається сильно зв'язним (strongly connected), якщо будь-які дві його вершини сильно пов'язані. Дві вершини s і t будь-якого графа сильно пов'язані, якщо існує орієнтований шлях з s в t і орієнтований шлях з t в s. Сильно зв'язковими компонентами орграфа називаються його максимально зв'язні подграфы). Одностороння компонента та слабка компонента визначаються аналогічно.
Конденсацією орграфа D називають орграф D*, вершинами якого є сильні компоненти D, а дуга в D* показує наявність хоча б однієї дуги між вершинами, які входять у відповідні компоненти.