Числа, що характеризують граф - Студопедія

Цикломатическим числом графа називається число u=N-n+p, де N- число ребер графа, n – число його вершин, P – число компонент зв'язності. Для зв'язкового графа u=N-n+1.

Теорема. Цикломатичне число графа дорівнює найбільшій кількості незалежних циклів.

Поняття незалежних циклів ось у чому. Поставимо у відповідність циклу μ графа G деякий вектор. Для цього надамо кожному ребру графа довільну орієнтацію. Якщо цикл проходить через ребро uk в напрямку його орієнтації rk раз і в протилежному напрямку Sk раз, то вважаємо c k = rk-Sk. Вектор з 1 ,c 2 ,…,c K ,…,c N ) N-вимірного простору називаютьвектором-циклом, відповідним циклу μ. Цикли μ1, μ2, називаютьнезалежними, якщо відповідні їм вектори , ,... лінійно незалежні.

Наслідком розглянутої теореми є такі твердження:

1. Зв'язковий граф G не має циклів і тоді, коли u=0. Такий граф є дерево (різні визначення графа-дерева будуть розглянуті у спеціальному розділі 3.2).

2. Зв'язковий граф G має єдиний цикл і тоді, коли u=1.

Цикломатичне число зв'язкового графа можна визначити як число ребер, яке потрібно видалити, щоб граф став деревом.

Цикломатичне число графа, зображеного на рис. 3.1.10, дорівнює 3.

Кількість внутрішньої стійкості графа. Нехай задано деякий граф G (x, г x). Розглянемо таке підмножина його вершин S Х, у якому дві будь-які точки є несумежними. Таке підмножина S називається внутрішньо стійким. Інакше кажучи, підмножина S Х є внутрішньо стійким, якщо гSÇS=ø.

Позначимо S – потужність множини S. Нехай F – множина всіх внутрішньо стійких множин.Числом внутрішньої стійкості графа G називається

a(G) = S.

Знаходження a(G) потрібно починати з максимального числа вершин і, поступово збільшуючи його, перевіряти, чи утворюють вибрані вершини внутрішньо стійке безліч.

Але якщо до будь-якої з цих множин додати якусь вершину, що не міститься в ньому, то підмножина перестане бути внутрішньо стійким, отже, a(G3)=2.

Кількість зовнішньої стійкості графа. Нехай задано деякий граф G(x,гx). Підмножина його вершин ТІХ є зовні стійкою множиною, якщо для кожної точки xiÎ(X/T) виконано умову

Позначимо T – потужність множини T. Нехай Ф – множина всіх зовні стійких множин. Числом зовнішньої стійкості графа G називається

b (G) = T.

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

Визначимо число зовнішньої стійкості графів, зображених на рис.3.1.11. Будь-яка пара вершин графа G1 утворює зовні стійку множину, але будь-яка його вершина не є зовні стійкою множиною, отже, b(G1)=2. Граф G2 містить дві зовні стійкі множини T1=1,x3>, T2=2,x4> із мінімальним числом елементів, тобто. b(G2)=2. Для графа G3 зовні стійким безліччю мінімальної потужності є T=1,x3>, тобто. b(G3)=2.

До визначення числа зовнішньої стійкості графа зводиться завдання про вартових. На посаді розставлені вартові, що охороняють n об'єктів, причому один і той же вартовий може спостерігати за кількома об'єктами. Потрібно з'ясувати, яка мінімальна кількість вартових, необхідних для спостереження за всіма об'єктами. Граф, зображений на рис.3.1.12, відповідає наступному завданню: 9 вершинграфа – об'єкти, що охороняються (n=9), ребра характеризують можливість перегляду об'єктів годинними. Так, наприклад, вартовий у об'єкта X1 може одночасно спостерігати за об'єктами X2, X3, X4, X9, вартовий у об'єкта X2 – за об'єктами X1, X3, X7, X8 і т.д. Для даного графа число зовнішньої стійкості дорівнює 2. Зовнішньо стійка множина утворюють вершини X4,X8. Достатньо двох вартових, розташованих у точках X4 і X8, для охорони всіх об'єктів.

Ядро графа. Якщо безліч вершин графа G(x,гx) містить підмножина LІХ як внутрішньо, так і зовні стійке, то таке підмножина L називаєтьсяядром графа.

Позначимо L потужність множини L. Ця величина задовольняє нерівності a(G)³L³b(G).

Хроматичне число графа.Припустимо, що кожна вершина графа G забарвлена в будь-який колір так, що жодні дві суміжні вершини не забарвлені однаково. Якщо при цьому знадобилося До фарб, то граф називається хроматичним порядком К. Мінімальне число К, при якому граф залишається хроматичним, називається хроматичним числом і позначається γ. Для графа G, зображеного на рис.3.1.13, хроматичне число γ(G)=3.

Теорема. До кожного графа G виконується нерівність n£a(G)g(G), де n=Х – потужність множини X, a(G) – число внутрішньої стійкості, g(G) – хроматичне число графа.

Доказ. Усі безліч вершин графа можна розбити на g внутрішньо стійких множин, що складаються з точок однакового кольору. Нехай внутрішньо стійкі множини містять m1, ..., mg вершин. mi£a(G), т.к. a(G) за визначенням є максимальна кількість вершин внутрішньо стійких множин. Але n=m1+m2+…+mg, отже, n£a(G)g(G).

Завдання про забарвлення геометричної карти пов'язані з визначенням хроматичного числа графа.Будь-яку географічну карту можна зобразити як графа G(x,гx), де вершинами є країни, а ребрами пов'язані країни, що межують між собою. Такий граф є пласким. Гіпотеза про чотири фарби полягає у твердженні того, що граф, відповідний будь-якій географічній карті, має хроматичне число не більше 4. Довгий час це припущення залишалося недоведеним, незважаючи на широкий інтерес математиків до цієї проблеми. Завдяки створенню сучасних ЕОМ вирішення цієї проблеми стало можливим, що було зроблено американськими математиками К. Аппелем і В. Хакеном. Завдання було вирішено шляхом зведення її до деяких приватних питань суто арифметичного характеру, що вимагають великої кількості обчислень, які були б не під силу людині, не озброєній сучасною обчислювальною технікою.

Чи не знайшли те, що шукали? Скористайтеся пошуком:

Вимкніть adBlock! і оновіть сторінку (F5)дуже потрібно