Введення в теорію графів
ОСНОВНІ ЧИСЛА ТЕОРІЇ ГРАФІВ
Можна розглядати не просто графи, а мультиграфом (X, U), де Х - множина вершин, U - безліч ребер (на відміну від звичайного графа кожна пара вершин може бути пов'язана більш ніж одним ребром). Наприклад, формули органічної хімії - типовий приклад мультиграфом.
Якщо взяти мультіграф G з n вершинами, m ребрами і p компонентами зв'язності, то число n (G) = m-n + p називається цикломатическая числом мультиграфом. Зокрема, це число визначає кількість незалежних циклів.- Хроматичної число графа
Граф називається р -хроматіческім, якщо його вершини можна розфарбувати р фарбами так, щоб суміжні вершини не були розфарбовані однаково. Найменше значення р називається хроматичним числом графа і позначається g (G). Доведено, що хроматичної число будь-якого плоского графа (графа, який можна зобразити на площині без перетинань ребер поза вершин) не перевищує 5 (залишається невирішеною проблема чотирьох фарб: будь-яку політичну карту світу можна розфарбувати чотирма фарбами, тобто всякий плоский граф є 4-хроматичним )
Мінімальна кількість фарб для розфарбовування ребер графа без однакового фарбування суміжних ребер називають хроматичним класом графа.
Хроматичний клас графа G збігається з хроматичним числом графа G ', який виходить з G заміною ребер вершинами зі збереженням суміжності (рис.9).
Можна довести, що за відсутності в графі елементарних циклів непарної довжини граф є біхроматичним.
Нехай графи G і H відповідно p + 1 - і q + 1 -хроматіческіе. Граф G + H є r + 1 -хроматіческім, де
(Символ Е визначає поразрядное підсумовування двійкових подань чисел з приведення по модулю 2; наприклад, 5 Е 6 = 3).
Безліч S М X називається внутрішньо стійким в графі (Х, Г), якщо ніякі дві його вершини не суміжні. Число a (G) = називається числом внутрішньої стійкості.
Наприклад, для симетричного графа на рис.10 можна побудувати кілька максимальних внутрішньо стійких множин (наприклад, 0 X5 X6 X8>) і a (G) = 4.
Прикладами його пошуку служать завдання непоражающихся розміщення 8 ферзів на шахівниці (симетричний граф з 64 вершинами; 92 рішення - 76 були знайдені Гауссом) (рис.11) завдання про 15 дівчат, яких можна водити на прогулянку трійками, в які кожна пара потрапляє не більше одного разу, - a (G) = 35 при C 3 15 = 455 трійках
Можна показати, що a (G) Ч g (G) і | Х |; a (G ґ H) i a (G) Ч a (H).
Апарат внутрішньої стійкості, зокрема, використовується при вирішенні завдання помехозащищенной передачі сигналів (завдання Шеннона про інформаційну ємності безлічі сигналів [1]).- Число зовнішньої стійкості
Безліч Т М X називається зовні стійким в графі (Х, Г), якщо для кожної вершини х П Т існує хоча б один образ в безлічі Т. Число b (G) = називається числом зовнішньої стійкості.
Приклади: скільки можна поставити ферзів (рис.12) або інших фігур, щоб все поля дошки були під ударом (5 ферзів, 8 тур або слонів, 12 коней), скільки спостерігачів поставити на перехрестях вулиць, щоб всі перехрестя були під наглядом.
Існує досить простий алгоритм пошуку мінімального зовні стійкого безлічі. Для графа G = (X, Г) (див. Ріс.13a) будуємо граф (X,, D), де визначено відображення D безлічі X в так, що, якщо у = x або y є прообразом х (у О Г - 1 х) (ріс.13b).
Подальші дії:- видаляємо з (X,, D) вершини х такі, що D х М D у для у № х (тут ми видаляємо c, d, f) і виходять з них ребра;
- якщо виявиться "висячий ребро" (х,), включаємо х в шукане безліч Т і видаляємо цю вершину і її образи (тут а Про Т і з графа виключається а й D а =<>;