ідні вершини з'єднані дугами (для орграфа деякі дуги мають направлення, що зазвичай відзначають стрілкою). Крім цього, в теорії графів розглядаються також мультіграф - це такі графи, в яких можуть бути петлі (тобто деяка вершина з'єднана сама з собою ребром) або деякі пари вершини можуть бути з'єднані між собою кількома ребрами. Маршрут у графі - це послідовність сусідніх (суміжних) вершин. Ясно, що можна визначити маршрут і як послідовність суміжних ребер (у цьому випадку ребра набувають напрямок). Зауважимо, що в маршруті можуть повторюватися вершини, але не ребра. Маршрут називається циклом, якщо в ньому перша вершина збігається з останньою. Шлях у графі (іноді говорять простий шлях) - це маршрут без повторення вершин (а значить, і ребер). Контур - це цикл без повторення вершин, за винятком першої вершини, що збігається з останньою. Послідовності вершин (рис. 2): 1-2-3-4-2-5 не простий шлях, а маршрут; послідовності 1-2-3-4-7-5 і 1-2-5 - прості шляхи; 1 - 2-3-4-2-5-6-1-це цикл (але не контур); 1-2-5-6-1 - це контур.
В
Рисунок 2 - В«НеправильнийВ» граф
Якщо є деякий маршрут з вершини t у вершину s, заданий у вигляді послідовності ребер, які в цьому випадку придбали напрямок, і якщо в цей маршрут входить ребро, що з'єднує вершини (i, j), те це ребро по відношенню до вершини i називають іноді прямий дугою, а по відношенню до вершини j - зворотної дугою (або зворотним ребром). Граф називається зв'язковим, якщо будь-які дві його вершини можна з'єднати маршрутом (або шляхом). На рис. 2 зображений зв'язний граф. Ребро, при видаленні якого граф перестає бути зв'язковим, іноді називають мостом або перешийком. Наступне визначення має сенс тільки для графів або мультіграф без петель (але не для орграфов). Ступінь вершини - це число ребер, що входять в цю вершину. Вершина називається висячої, якщо її ступінь дорівнює одиниці. p> Лемма 1. Якщо ступінь всіх вершин у графі більше або дорівнює двом, то граф обов'язково містить контур. p> Доказ. Дійсно, вийшовши з деякої вершини і увійшовши в іншу, завжди можна вийти з неї по іншому ребру, так як ступінь вершини більше або дорівнює двом. Вийти з вершини за новим ребру неможливо тільки в тому випадку, якщо ця вершина вже зустрічалася, а це означає, що можна виділити контур з вершин цього графа. p> Завдання розмальовки графа вважається класичною в інформатиці. Створені алгоритми застосовуються для видачі радіочастот, складання розкладів та інших завдань на розподіл ресурсів. p> На жаль не існує оптимального алгоритму. Завдання можна вирішити або повним перебором, або з наближеним значенням. p> Складність повного перебору дорівнює O (nn), де n - це кількість вершин. У реальній ситуації складність, звичайно, буде менше - O (4n) або O (5n), оскільки більшість вводяться людиною графів скоріше будуть планарнимі, або мати малу кількість перетинань. p> Однак, у кожному разі, складність повного перебору дуже висока. І, оскільки, на...
