Page 63 - 4496

для шляху: контур може бути простим або складеним ,
елементарним або неелементарним. Початкова (вона ж і
кінцева) вершина контуру вважається входить тільки один
раз, хоча в записі вона буде зустрічатися двічі. На рис 3.6
шлях U , U , U є контуром, так як він починається і
3
6
7
закінчується у вершині 1 .
Контур одиничної довжини називається петлею. У
прикладі дуга U 9 утворює петлю.
Граф називається сильнозв'язаним, якщо будь-яка пара
вершин у ньому пов'язана шляхом з початком в першій і
кінцем у другій вершині .
Наведений у прикладі граф є сильнозв'язаним. Якщо
змінити орієнтацію дуги (3,5) на протилежну , то отриманий
граф сильнозв'язаним не буде. У ньому жодна вершина не
повинна зв'язуватися шляхом з вершиною 5.
Означення 1. Нехай G- неорієнтований граф.
Маршрутом M у графі G називається така скінченна або не
скінченна послідовність вершин і ребер, які чергуються.
{... v s , e s , v s+1 , e s+1 ,…, v n-1 ,e n-1 , v n , e n ,…}.
і кожні два сусідні ребра es- 1 і e s є інцидентними до вершини
v s .
очевидно, маршрут M можна задати послідовністю
вершин (…,v s-1, v s, v s+1,…) або послідовністю ребер (…,е s-1,
е s, е s+1,…) .
Одне і те ж сааме ребро в маршруті може зустрічатись
декілька разів. Якщо розглядати тільки скінченні маршрути,
то існують перше е1 і останнє еn ребра. Вершина v0
інцидентна ребру e1 , називається початком маршруту. Якщо
e1 та e2 — крайні, то потрібна спеціальна вказівка, яку із двох
інцидент ним до них вершин вважати початком. Аналогічно
означається кінець маршруту.
Означення 2. Вершини, інцидентні ребрам маршруту,
крім початкової і кінцевої, називають внутрішніми або
проміжними.
Означення 3. Нехай маршрут М(e1, e2,..., en) має початок
v0 і кінець vn . Тоді його називають сполучним. Число ребер
такого маршруту є його довжиною. Якщо v0 =vn , то маршрут
М називають замкненим (циклічним). Відрізок (eі, eі+1,..., ej)
скінченого або нескінченого маршруту М називають його
ділянкою.
60