Теорія графів
Теорія графів — розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якої зліченної множини, а E — підмножина V × V.
Визначення графу є настільки загальним, що цим терміном можна описувати безліч подій та об'єктів повсякденного життя. Високий рівень абстракції та узагальнення дозволяє використовувати типові алгоритми теорії графів для вирішення зовнішньо несхожих задач у транспортних і комп'ютерних мережах, будівельному проектуванні, молекулярному моделюванні тощо. Теорія графів знаходить застосування, наприклад, в геоінформаційних системах (ГІС). Існуючі або запроектовані будинки, споруди, квартали тощо розглядаються як вершини, а дороги, інженерні мережі, лінії електропередачі, що їй з'єднують, тощо — як ребра. Застосування різних обчислень, вироблених на такому графі, дозволяє, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут.
Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез.
Визначення графу є настільки загальним, що цим терміном можна описувати безліч подій та об'єктів повсякденного життя. Високий рівень абстракції та узагальнення дозволяє використовувати типові алгоритми теорії графів для вирішення зовнішньо несхожих задач у транспортних і комп'ютерних мережах, будівельному проектуванні, молекулярному моделюванні тощо. Теорія графів знаходить застосування, наприклад, в геоінформаційних системах (ГІС). Існуючі або запроектовані будинки, споруди, квартали тощо розглядаються як вершини, а дороги, інженерні мережі, лінії електропередачі, що їй з'єднують, тощо — як ребра. Застосування різних обчислень, вироблених на такому графі, дозволяє, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут.
Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез.
Формальні означення
Нехай X = { x1,…,xn} — деяка скінченна множина (множина вершин), M2 — множина всіх невпорядкованих пар елементів з X,
M2 = { (xi,xj): xi ∈ X, xj ∈ X, i ≠ j}
1. Граф G(X, W) — пара множин X, W ⊂ M2. Множина X — це множина вершин, множина W — це множина ребер. Якщо (xi,xj) ∈ W, то ми говоримо, що ребро (xi,xj) сполучає вершину xi з вершиною xj; інша термінологія — ребро (xi,xj) і вершини xi та xj інцидентні.
2. Граф G(X, W) називається повним, якщо W = M2.
Якщо множина X містить n вершин, то, очевидно, число ребер повного графа дорівнює Cn2. Повний граф з n вершинами позначається Kn.
3. Граф G(X, W) називається порожнім, якщо W = ∅.
4. Вершини xi та xj графа G(X, W) інцидентні, якщо (xi,xj) ∈ W.
5. Степенем d(xi) вершини xi графа G(X, W) називається число вершин xj, які інцидентні вершині xi (число відрізків, які виходять з вершини xi).
6. Якщо d(xi)=1, то вершина xi називається кінцевою вершиною графа G(X, W). Якщо d(xi)=0, то вершина xi називається ізольованою.
M2 = { (xi,xj): xi ∈ X, xj ∈ X, i ≠ j}
1. Граф G(X, W) — пара множин X, W ⊂ M2. Множина X — це множина вершин, множина W — це множина ребер. Якщо (xi,xj) ∈ W, то ми говоримо, що ребро (xi,xj) сполучає вершину xi з вершиною xj; інша термінологія — ребро (xi,xj) і вершини xi та xj інцидентні.
2. Граф G(X, W) називається повним, якщо W = M2.
Якщо множина X містить n вершин, то, очевидно, число ребер повного графа дорівнює Cn2. Повний граф з n вершинами позначається Kn.
3. Граф G(X, W) називається порожнім, якщо W = ∅.
4. Вершини xi та xj графа G(X, W) інцидентні, якщо (xi,xj) ∈ W.
5. Степенем d(xi) вершини xi графа G(X, W) називається число вершин xj, які інцидентні вершині xi (число відрізків, які виходять з вершини xi).
6. Якщо d(xi)=1, то вершина xi називається кінцевою вершиною графа G(X, W). Якщо d(xi)=0, то вершина xi називається ізольованою.
Історія виникнення теорії графів
Родоначальником теорії графів вважається Леонард Ейлер. У 1736 році в одному зі своїх листів він формулює і пропонує рішення завдання про сім Кенігсберзьких мостів, що стала згодом однією з класичних задач теорії графів.
Поштовх до розвитку теорія графів отримала на рубежі XIX і ХХ століть, коли різко зросла кількість робіт в сфері топології та комбінаторики, з якими її пов'язують тісні узи спорідненості. Графи стали використовуватися при побудові схем електричних кіл і молекулярних схем. Як окрема математична дисципліна теорія графів була вперше представлена в роботі угорського математика Кеніга в 30-ті роки XX століття.
Останнім часом графи і пов'язані з ними методи досліджень органічно пронизують на різних рівнях чи не всю сучасну математику. Теорія графів розглядається як одна з гілок топології; безпосереднє відношення вона має також до алгебри і до теорії чисел. Графи ефективно використовуються в теорії планування та управління, теорії розкладів, соціології, математичній лінгвістиці, економіці, біології, медицині, географії. Широке застосування знаходять графи в таких областях, як програмування, теорія кінцевих автоматів, електроніка, в рішенні імовірнісних і комбінаторних задач, знаходженні максимального потоку в мережі, найкоротшої відстані, максимального паросполучення, перевірки планарності графа і ін. Як особливий клас можна виділити задачі оптимізації на графах. Математичні розваги і головоломки теж є частиною теорії графів, наприклад, знаменита проблема чотирьох фарб, інтригуюча математиків і по сей день. Теорія графів швидко розвивається, знаходить все нові додатки і чекає молодих дослідників.
Поштовх до розвитку теорія графів отримала на рубежі XIX і ХХ століть, коли різко зросла кількість робіт в сфері топології та комбінаторики, з якими її пов'язують тісні узи спорідненості. Графи стали використовуватися при побудові схем електричних кіл і молекулярних схем. Як окрема математична дисципліна теорія графів була вперше представлена в роботі угорського математика Кеніга в 30-ті роки XX століття.
Останнім часом графи і пов'язані з ними методи досліджень органічно пронизують на різних рівнях чи не всю сучасну математику. Теорія графів розглядається як одна з гілок топології; безпосереднє відношення вона має також до алгебри і до теорії чисел. Графи ефективно використовуються в теорії планування та управління, теорії розкладів, соціології, математичній лінгвістиці, економіці, біології, медицині, географії. Широке застосування знаходять графи в таких областях, як програмування, теорія кінцевих автоматів, електроніка, в рішенні імовірнісних і комбінаторних задач, знаходженні максимального потоку в мережі, найкоротшої відстані, максимального паросполучення, перевірки планарності графа і ін. Як особливий клас можна виділити задачі оптимізації на графах. Математичні розваги і головоломки теж є частиною теорії графів, наприклад, знаменита проблема чотирьох фарб, інтригуюча математиків і по сей день. Теорія графів швидко розвивається, знаходить все нові додатки і чекає молодих дослідників.
Деякі задачі теорії графів
- Проблема семи мостів Кенігсберга — один з перших результатів у теорії графів, опублікований Ейлером в 1736.
- Проблема чотирьох фарб — була сформульована в 1852, але некласичне доведення отримано лише в 1976 (достатньо 4-х фарб для карти на сфері (площині).
- Завдання комівояжера — одна з найбільш відомих NP-повних задач.
- Задача про кліку — ще одна NP-повна задача.
- Знаходження мінімального стягуючого (кістякового) дерева.
- Знаходження мінімального дерева Штейнера — найкоротшої мережі, що з'єднує заданий кінцевий набір точок площини, при умові, що дозволяється додавати до мережі нові точки. NP-повна задача.
- Ізоморфізм графів — чи можна шляхом зміни нумерації вершин одного графа отримати інший.
- Планарними графа — чи можна зобразити граф на площині без перетинань ребер (або з мінімальним числом шарів, що знаходить застосування при трасуванні з'єднань елементів друкованих плат або мікросхем).
Спосіб зберігання графів в пам'яті
Найчастіше використовують два способи зберігання:
Матриця суміжності.
Являє собою двовимірний масив розміром NxN, де N - кількість вершин графа. У матриці A [i, j] = 1 (або більше, якщо граф зважений, тобто кожне ребро має свою вагу або вартість), якщо існує ребро між вершинами I і J (в орієнтованому графі - чи можна дістатися з вершини I до вершини J, тобто ребро направлено в одну сторону), або A [i, j] = 0 в іншому випадку. Очевидно, що для оріетнірованного графа a [i, j] = a [j, i] (оскільки орієнтованим графом називають окремий випадок неориентированного графа, у якого кожному ребру i-> j є противонаправленность j-> i)
Список ребер.
Являє собою двомірний масив розміром Mx2, де M - кількість ребер графа. У кожному рядку описує:
sp [i, 1] - від якої вершини відходить ребро i
sp [i, 2] - до якої вершині приходить ребро i;
Окремо можна завести масив P (M), де P [i] буде зберігати вагу ребра i;
Матриця суміжності.
Являє собою двовимірний масив розміром NxN, де N - кількість вершин графа. У матриці A [i, j] = 1 (або більше, якщо граф зважений, тобто кожне ребро має свою вагу або вартість), якщо існує ребро між вершинами I і J (в орієнтованому графі - чи можна дістатися з вершини I до вершини J, тобто ребро направлено в одну сторону), або A [i, j] = 0 в іншому випадку. Очевидно, що для оріетнірованного графа a [i, j] = a [j, i] (оскільки орієнтованим графом називають окремий випадок неориентированного графа, у якого кожному ребру i-> j є противонаправленность j-> i)
Список ребер.
Являє собою двомірний масив розміром Mx2, де M - кількість ребер графа. У кожному рядку описує:
sp [i, 1] - від якої вершини відходить ребро i
sp [i, 2] - до якої вершині приходить ребро i;
Окремо можна завести масив P (M), де P [i] буде зберігати вагу ребра i;
const MaxN = 100; //максимальна кількість вершин
INF = 1000000000; //"нескінченність ", задана наперед величина, у багато разів більша максимального вазі ребер.
type Matrix = array[1..MaxN, 1..MaxN] of longint; //тип матриці суміжності. M[i,j] > 0, якщо існує ребро, що йде від вершини i к j
Spisok = array[1..MaxN * MaxN, 2]of longint; //тип матриці, яка містить список ребер. Кожен рядок описує ребро. (ребро k з'єднує вершини з номерами s[k,1] и s[k,2])
Ves = array[1..MaxN * MaxN]of longint; //тип матриці, що містить ваги ребер для списку Залежно від умов і контексту завдань, необхідно вести якийсь певний формат зберігання. При цьому варто мати на увазі, що одні алгоритми працюють з матрицею суміжності, а інші - зі списком ребер. Але структура графа така, що не складає труднощів перетворити список в таблицю, і навпаки. Тому буває зручно вести відразу дві структури, так як найчастіше в задачах вводяться саме ребра, а матрицю суміжності побудувати, виходячи з даного списку. Як це реалізувати, буде розглянуто докладніше.
Введення і виведення
За замовчуванням в програмах буде розглядатися введення з клавіатури. Я не стану поки описувати процедури читання з файлу, так як в різних завданнях структура файлу буває різною. Але варто лише трохи змінити нижчеприкладені процедури, як буде отримана можливість читання з файлу.
procedure Input_Table(var A : Matrix; N : longint); //процедура введення матриці суміжності A(N, N)
var i, j : longint;
begin
for i := 1 to N do
begin
for j := 1 to N do read(A[i, j]);
readln;
end;
end;
procedure Input_Spisok(var P : Spisok; var V : Ves; M : longint); //процедура введення списку зважених ребер P(M,2), M - кіл-ть ребер.
var i : longint;
begin
for i := 1 to M do readln(P[i, 1], P[i, 2], V[i]);
end;Сільвейстр Богдан, Паламар Максим, Майданюк Артем
