и на два непересічних підмножини V_1 і V_2 так, що всяке ребро з'єднує вершину з V_1 з вершиною з V_2.
· k-долинним, якщо його вершини можна розбити на k непересічних підмножини V_1, V_2, ..., V_k так, що не буде ребер, що з'єднують вершини одного і того ж підмножини.
· повним дводольним, якщо кожна вершина одного підмножини з'єднана ребром з кожною вершиною іншого підмножини.
· планарним, якщо граф можна зобразити діаграмою на площині без перетинів ребер.
· виваженим, якщо кожному ребру графа поставлено у відповідність деяке число, зване вагою ребра.
· Хордальная, якщо граф не містить індукованих циклів з довжиною більше трьох.
Також буває:
· k-розфарбовуваним
· k-хроматичним
. 6 Узагальнення поняття графа
Простий граф є одновимірним симпліціального комплексом.
Більш абстрактно, граф можна задати як трійку (V, E,?), де V і E - деякі множини (вершин і ребер, соотв.), а?- Функція інцидентності (або інцідентор), що зіставляє кожному ребру e? E (впорядковану або невпорядковану) пару вершин u і v з V (його кінців). Окремими випадками цього поняття є:
· орієнтовані графи (орграф) - коли? (e) завжди є впорядкованою парою вершин; неорієнтовані графи - коли? (e) завжди є невпорядкованою парою вершин;
· змішані графи - в якому зустрічаються як орієнтовані, так і неорієнтовані ребра і петлі;
· Ейлерови графи - граф в якому існує циклічний Ейлером шлях (Ейлеров цикл).
· мультиграфом - графи з кратними ребрами, що мають своїми кінцями одну і ту ж пару вершин;
· псевдографів - це мультиграфом, що допускають наявність петель;
· прості графи - не мають петель і кратних ребер.
Під дане вище визначення не підходять деякі інші узагальнення:
· гіперграф - якщо ребро може з'єднувати більше двох вершин.
· ультраграф - якщо між елементами x_i і u_j існують бінарні відношення інцидентності.
. 7 Способи представлення графа в інформатиці
Матриця суміжності
Таблиця, де як стовпці, так і рядки відповідають вершинам графа. У кожній клітинці цієї матриці записується число, що визначає наявність зв'язку від вершини-рядка до вершині-стовпцю (або навпаки). Недоліком є ??вимоги до пам'яті, прямо пропорційні квадрату кількості вершин.
· Двовимірний масив;
· Матриця з пропусками;
· Неявне завдання (за допомогою функції).
Матриця інцидентності
Кожен рядок відповідає певній вершині графа, а стовпці відповідають зв'язкам графа. У осередок на перетині i-го рядка з j-м стовпцем матриці записується:
· 1, у випадку, якщо зв'язок j «виходить» з вершини i,
·? 1, якщо зв'язок «входить» в вершину,
· 0, у всіх інших випадках (тобто якщо зв'язок є петлею або зв'язок не инцидентна вершині)
Даний спосіб є найбільш ємним (розмір пропорційний | E | | V |) для зберігання, але полегшує знаходження циклів в графі.
Список ребер
Список ребер - це тип представлення графа, що припускає, що кожне ребро представляється двома числами - номерами вершин цього ребра.
2. Технічна реалізація
. 1 Алгоритм пошуку шляху
Для реалізації алгоритму пошуку найбільш віддалених вершин у графі було розглянуто два способи вирішення даної задачі, і вибраний більш оптимальних з представлених нижче.
) Підвісимо дерево за яку-небудь вершину неодиничної ступеня. Тоді розглянемо, як буде влаштований найдовший шлях - він буде від деякого листа підніматися до деякої вершини, після чого опускатися до іншого листа. У ньому є деяка найвища вершина (будемо називати її «переломною»), і він розпадається на два подпуть, кожен з яких йде знизу вгору, і ці шляхи у своїх під-деревах є найдовшими.
З вершини, за яку ми доважили дерево, запустимо процедуру обходу в глибину. Нехай ця процедура для кожної вершини повертає довжину найдовшого шляху від цієї вершини до деякого аркуша (на малюнку близько кожної вершини написано значення, яке обчислити ця процедура). Зрозуміло, що процедура обходу в глибину це значення може легко обчислювати (як максимум з аналогічних значень для піддерев плюс 1). Крім цього, об...
