еякі Дії одноразово з шкірними з вершин графа. Наприклад, Деяк інформацію звітність, Передат шкірному Із комп ютерів у мережі, до того ж не має змісту проходити шкірно вершину двічі.
Зробити подібний прохід дозволяють алгоритми поиска у глибінь та в ширину. Оскількі в програмній реалізації Використовують ідеї поиска в глибінь, то доцільно детально его описати. p align="justify"> При обході в глибінь ми проходимо перший вузол, а потім йдемо Вздовж ребер графу, до того годині, пока не впіраємося в глухий кут. Вузол неорієнтованого графу є глухим кутом, ЯКЩО Вже пройдено ВСІ сусідні з ним вершини. У неорієнтованому графі це такоже вузол, з Якого НЕ Прокуратура: ребра. p align="justify"> После потрапляння в глухий кут відбувається повернення назад Вздовж пройденого маршруту, доки НЕ знайдеться вершина, у Якої ще остался неперегляненій сусід, а потім рухаємося в цьом новому Напрямки. Процес віявляється завершеним, коли відбулося повернення в початкових точку, а ВСІ сусідні з нею вершини виявило пройденого. p align="justify"> Ілюструючі цею алгоритм обходу, при віборі двох чі больше вершин обірається вершина Менша в лексікографічному порядку, альо це может буті и не так, в залежності від того, оберемо матрицю суміжності чг список ребер.
В
Малюнок 1.1 - Приклад графу
Розглянемо граф з малий. 1.1. Починаючі прохід з вершини 1, мі потім пройдемо послідовно вершини 2, 3, 4, 7, 5, 6 та зайдемо в глухий кут. Тоді нам доведеться повернути у вершину 7 и Побачити, что вершина 8 залиша не проторений. Альо перейшовші в Цю вершину, ми знову опіняємося в глухому куті. Повернувшись у вершину 4, мі Бачимо, что не проторений залиша вершина 9; ее прохід вновь заводити в глухий кут. Знову повертаємося назад в початкових вершину, и оскількі ВСІ сусідні з нею вершини виявило пройдений, то обхід завершень. p align="justify"> Загальний алгоритм обходу віглядає так: (G, v) граф Данії вузол (v) (v) шкірного ребра vw графа G doвершіна w невідмічена then (G, w) iffor
1.3 Ланцюг, цикл. Зв язність. Метричні характеристики графа
Вершина v назівається такою, что досягається з вершини u, ЯКЩО існує (u, v) - маршрут. Будь-яка вершина вважається такою, что досягається Із самої себе. p> Маршрут назівається Ланцюг, ЯКЩО ВСІ йо ребра Різні, та пробачимо Ланцюг, ЯКЩО ВСІ йо вершини, крім, Можливо, крайніх, Різні. Маршрут назівають ціклічнім, ЯКЩО. Ціклічній ланцюг назівається циклом, а ціклічній Простий ланцюг - пробачимо циклом. Кількість ребер у маршруті назівають его довжина. Цикл Довжина 3 часто назівають трикутником. Довжина будь-якого циклу не менше за 3, ЯКЩО Говорити про Простий граф, оскількі в такому графі немає петель и кратних ребер. Мінімальна Із Довжина ціклів графу назівається его о...
