рухатіся по них уздовж графа.
Визначення. Початок маршруту - це вершина, інцідентна ребру и не інцідентна ребру. Кінець маршруту - це вершина інцідентна ребру и не інцідентна. Если ребра, (,) - кратні, то необходимо додатково вказуваті, якові Із двох інцідентніх вершин вважаті качаном (кінцем) маршрутом.
Визначення. Маршрут довжина - послідовність, что містіть ребер. Іншімі словами, довжина маршруту назівається Кількість ребер у ньом; при цьом Кожне ребро Враховується Стільки разів, скільки разів воно зустрічається в маршруті.
Позначення маршрутом із у - послідовністю надлишково, того ми будемо позначаті маршрут як.
Визначення. Маршрут, всі ребра которого різні, назівається Ланцюг. Ланцюг, что НЕ перетінає собі, тобто НЕ має вершин, что повторюються, назівається пробачимо.
Приклад. Візначіті Можливі маршрути (і їхню Довжину) з вершини в у графі, збережений на Наступний малюнку.
розв язання: з вершини у ведуть, например, шляхи:
) - довжина 2; 5) - довжина 6;
) - довжина 4; 6) - довжина 6;
) - довжина 4; 7) - довжина 8;
) - довжина 6; 8) - довжина 10.
Шляхи: 6), 8) НЕ є просто.
Визначення. Маршрут, у якому збігаються качан и Кінець - і - назівається ціклічнім. Ціклічній маршрут назівається циклом, если ВІН є ланцюг, и пробачимо циклом - если це просто ланцюг.
например, маршрут для графа, збережений на рис. 6.17, є пробачимо циклом; а маршрут є циклом, альо НЕ буде пробачимо, того что містіть вершини, Які повторюються.
Визначення. Вершини и графа назіваються зв язаними, если існує маршрут з качаном у і кінцем у. Маршрут между зв язаними вершинами может буті Поданєв пробачимо Ланцюг.
Визначення. Граф назівається зв язнім, если будь-які парі его вершин зв язані между собою.
Приклад. Граф, збережений на рис. 5.9, а - НЕ зв язній, а граф на рис. 5.9, б - зв язній.
Малюнок 5.9 - Приклад незва язного и зв язного графів
Теорема. Если існує маршрут з вершин у графі, то існує простий ланцюг, что з'єднує вершини і.
Наслідок. Граф є зв'язного тоді и только тоді, коли между будь-Якими двома его вершинами існує простий ланцюг.
Визначення. Максимальний Непорожнє зв'язного підграф графа назівається компонентом графа.
Отже, КОЖЕН граф представляет собою об'єднання своих компонент, Які попарно НЕ перетінаються.
Незв'язній граф має, як мінімум, два компоненти. Например, граф, збережений на рис. 5.9, а, має два компоненти: і.
Визначення. Вершина назівається цяткою зчленування, если відалення ее Із графа приводити до Збільшення числа компонент зв язності.
Визначення. Ребро назівається міст, если відалення его Із графа приводити до Збільшення числа компонент зв язності.
Визначення. Множини ребер зв язного графа назівається множини розрізу, если відалення ребер Із множини порушує зв язність графа, а відалення власної підмножіні множини залішає граф зв язнім. Если множини складається з одного ребра, то це ребро назівається ребром розрізу.
Приклад. Візначіті ребра розрізу графа, збережений на Наступний малюнку.
розв язання: ребра, і - є ребрами розрізу. Їх відалення порушує зв язність графа.
Приклад. Візначіті множини розрізу для графа, збережений на Наступний малюнку.
розв язання: множини розрізу для даного графа могут буті, Наприклад:
,,, и т.д.
5.3.2 G - орієнтований граф
Визначення. Послідовність ребер, у якому Кінець шкірного попередня ребра збігається з качаном следующего, назівається путем або орієнтованім маршрутом. У шляху ті самє ребро может зустрічатіся кілька разів.
Визначення. Качаном шляху є вершина ребра, а кінцем шляху є вершина ребра.
Визначення. Довжину орієнтованого маршрутом назівається Кількість орієнтованих ребер, что входять у цею шлях.
Приклад. Для графа, збережений на рис. 5.10, пріведемо приклада орієнтованих маршрутів з вершини до вершини:; ;- Довжина 3;- Довжина 5.
Малюнок 5.10 - прикладом орієнтованих маршрутів
Визначення. Орієнтованім Ланцюг назівається шлях, шкірні ребро которого зустрічається НЕ ...
