R(b,d)

ВСТУП

Теорія графів - одна з небагатьох математичних теорій, для яких точно відомий її засновник, час і місце створення: Леонард Ейлер, 1736 р., м. Петербург. Саме цього року Л.Ейлер в "Записках Петербурзької академії наук" опублікував статтю щодо рішення зараз широко відомої задачі про Кенігсбергські мости. Та робота містила не лише негативну відповідь на питання щодо можливості обійти всі сім мостів м. Кенігсберга так, щоб по кожному з них пройти рівно один раз. У ній також сформульовано й обґрунтовано критерій, за яким на це питання можна відповісти для довільного графа.

Однак ця стаття була єдиною протягом сторіччя. Лише в середині XІX століття відродився інтерес до теорії графів. Дослідження електричних мереж, структур молекул і кристалів, рішення проблем у біології й психології слугували потужним каталізатором у становленні даного розділу математики. Графи виявилися зручним засобом для опису найрізноманітніших систем і ефективним інструментом структурного аналізу. Однією із знаменитіших задач, що спонукала загальний інтерес до теорії графів, була запропонована Де Морганом (близько 1850 р.) проблема чотирьох фарб:

чи досить чотирьох фарб для розфарбування будь-якої карти так, щоб сусідні країни були різного кольору?

Представлення графів

В математиці граф G= <V, E> – кортеж множини вершин V та множини ребер E Í V × V, кожне з яких задається парою вершин та, можливо, його вартістю .

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

Рис. 1. (а) – неорієнтований, (b) – орієнтований графи

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

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

Сформулюємо властивість будь-яких граф.

Теорема 1. Сума ступенів всіх вершин графа дорівнює подвоєному числу його ребер.

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

Наслідком Теореми 1 є "лема про рукостискання".

Теорема 2. Кількість вершин непарного ступеня будь-якого графа завжди парна.

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

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

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

Графи рис.1 можуть бути задані неявно фактами:

(а) – r(a,b).

Дата добавления: 2014-01-04