1. Вступ
2. Графи і способи їх подання

Анотація: Наводяться початкові відомості про графах і основні поняття і визначення такі як орграф, змішаний граф, дублікат графа дуга, петля, полустепені результату і заходу. Даються можливі способи представлення графів. Мета лекції: Дати уявлення про графах і можливі способи їх подання.

Вступ

В останні роки особливу важливість придбали ті розділи математики, які мають відношення до розвитку цифрових пристроїв, цифрового зв'язку і цифрових обчислювальних машин. Базою для викладання цих дисциплін поряд з класичними методами аналізу безперервних фізичних моделей стали алгебраїчні, логічні і комбінаторні методи дослідження різних моделей дискретної математики.

Значно зросла популярність теорії графів - гілки дискретної математики. Графи зустрічаються в багатьох областях під різними назвами: "структури" в цивільному будівництві, "мережі" - в електроніці, "соціограма" - в соціології та економіці, "молекулярні структури" - в хімії, "дорожні карти", електричні або газові розподільні мережі і т.д.

Народившись при вирішенні головоломок та ігор, таких, наприклад, як завдання про кенігсберзькими мостах і гра Гамільтона, теорія графів стала потужним засобом дослідження і вирішення багатьох завдань, що виникають при вивченні великих і складних систем. Для фахівців з обчислювальної техніки, інформаційних систем та систем цифрового зв'язку теорія графів - це зручний мову вираження понять з цієї області; багато результати теорії графів мають безпосередній зв'язок з завданнями, з якими їм доводиться стикатися. Графічна інтерпретація різних моделей графів дана на Мал. 1.1 Так у вигляді орієнтованих графів можна уявити будь-яку логічну або функціонально - логічну схему ( Мал. 1.1 , А). На таких графових моделях можна, наприклад, оцінити швидкодію схеми. Блок-схема алгоритму може бути представлена ​​імовірнісним графом ( Мал. 1.1 , Б), який дозволяє оцінити часові характеристики алгоритму, витрати процесорного часу, трудомісткість і інші. Графом типу "дерево" можна відобразити практично будь-яку структуру організації або підприємства ( Мал. 1.1 , В).

Широке застосування теорія графів одержала при дослідженні так званої проблеми оптимізації, що виникає при конструюванні великих систем як технічних, так і програмних, наприклад, таких, як компілятори.

В рамках цих досліджень були розроблені багато, невідомі раніше теоретико-графові поняття. Теорія графів має велику привабливість для фахівців в області проектування для побудови ефективних алгоритмів і аналізу їх складності. Використання апарату теорії графів справила значний вплив на розробку алгоритмів конструкторського проектування схем. Безпосереднє і детальне уявлення практичних систем, таких, як розподільні мережі, системи зв'язку, призводить до графів великого розміру, успішний аналіз яких залежить в рівній мірі, як від ефективних алгоритмів, так і від можливостей комп'ютерної техніки. Тому в даний час основна увага зосереджена на розробці і описі комп'ютерних алгоритмів аналізу графів. У зв'язку з цим основний акцент в даному навчальному посібнику робиться на машинні способи представлення графів і алгоритми вирішення задач на графах, легко реалізованих на ЕОМ.

Мал.1.1.

Графічна інтерпретація застосування графових структур: а - орграф; б - імовірнісний граф; в - граф-дерево

Графи і способи їх подання

Основні визначення

Граф задається безліччю точок або вершин х1, х2, ..., хn і безліччю ліній або ребер a1, a2, ..., am, що з'єднують між собою всі або частину точок. Формальне визначення графа може бути дано наступним чином.

Графом називається двійка виду

G = (X, A),

де X = {xi}, i = 1, 2, ..., n - безліч вершин графа, A = {ai}, i = 1, 2, ..., m - безліч ребер графа.

Графи можуть бути орієнтованими, неорієнтованими і змішаними ( Мал. 1.2 ). Якщо ребра у безлічі A орієнтовані, що зазвичай показується стрілкою, то вони називаються дугами, і граф з такими ребрами називається орієнтованим графом або Орграф ( Мал. 1.2 , А).

Якщо ребра не мають орієнтації, то граф називається неорієнтованим ( Мал. 1.2 , Б). Граф, в якому присутні і ребра, і дуги називається змішаним ( Мал. 1.2 , В). У разі, коли G = (X, A) є Орграф, і ми хочемо знехтувати спрямованістю дуг з безлічі A, то неорієнтовані граф, відповідний G, буде позначатися і називатися неорієнтованим дублікатом або неорієнтованим двійником ( Мал. 1.2 , Г).

Дуга ai може бути представлена ​​впорядкованою парою вершин (хn, хk), що складається з початкової хn і кінцевої хk вершин. Наприклад, для графа G1 ( Мал. 1.2 , А) дуга a1 задається парою вершин (x2, x1), а дуга а3 парою (x2, x3). Якщо хn, хk - кінцеві вершини дуги ai, то кажуть, що вершини хn і хk інцидентні дузі ai або дуга ai инцидентна вершин хn і хk.

Дуга, у якій початкова і кінцева вершини збігаються, називається петлею. У графі G3 ( Мал. 1.2 , В) дуга a7 є петлею.

Кожна вершина орграфа хi може характеризуватися полустепені результату d0 (хi) і полустепені заходу dt (хi).

Полустепені результату вершини хi - d0 (хi) називається кількість дуг, що виходять з цієї вершини. Наприклад, для графа G1 ( Мал. 1.2 , А) характеристики полустепені результату наступні: d0 (х1) = 1, d0 (х2) = 2, d0 (х3) = 2, d0 (х4) = 1.

Полустепені заходу вершини хi - dt (хi) називається кількість дуг, що входять в цю вершину. Наприклад, для орграфа G1: dt (х1) = 2, dt (х2) = 1, dt (х3) = 2, dt (х4) = 1.

Очевидно, що сума полустепені результату всіх вершин графа, а також сума полустепені заходу всіх вершин графа дорівнює загальному числу дуг графа, т. Е.

де n - число вершин графа, m - число дуг.

Кожна вершина неориентированного графа хi може характеризуватися ступенем вершини d (хi).

Ступенем вершини хi - d (хi) називається кількість ребер, інцидентних цій вершині. Наприклад, для орграфа G1 ( Мал. 1.2 , Б) характеристики ступенів наступні: d (х1) = 2, d (х2) = 3, d (х3) = 3, d (х4) = 2.