Цепи. Циклы. Связность

1. Последовательность вершин и ребер графа G

называется путем из вершины в вершину , если

для

Вершина называется началом, а - концом пути; число n называется длиной пути (путь нулевой длины состоит из одной вершины). В общем случае среди вершин и ребер этой последовательности могут быть повторения. Говорят, что путь проходит

последовательно через вершины по ребрам

Цепью называется последовательность вершин и ребер, образующая путь в соотнесенном неориентированном графе. Отсюда всякий путь является цепью, обратное верно только для неориентированных графов, в которых понятия пути и цепи совпадают.

Если в последовательности , т.е. начальная вершина совпадает с конечной, то такой путь (соответственно цепь) называется контуром (соответственно циклом) длины n. Контур (цикл) не имеет особо выделенной вершины и может быть записан в виде последовательности, начиная (и заканчивая) любой его вершиной.

Путь, цепь, контур, цикл называются простыми (соответственно элементарными), если каждое их ребро (соответственно каждая вершина и каждое ребро) входит в последовательность ровно один раз (не считая последней вершины в записи цикла).

Можно рассматривать цепь как траекторию на графе. Тогда путь - это траектория, проходящая каждое свое ребро в направлении его ориентации. Простой путь не проходит дважды ни по одному своему ребру, элементарный путь не проходит дважды ни через одну вершину.Элементарные путь, цепь, контур, цикл можно считать просто некоторыми подграфами графа G.

Если цепь , отличная от , не является элементарной, то некоторая вершина v входит в последовательность хотя бы дважды. Часть последовательности этой между этими двумя вхождениями вершины есть цикл, и после вычеркивания этой части остается цепь с теми же концами и

Повторяя эту операцию пока возможно, мы получим в результате элементарную цепь или цепь вида , которую можно заменить одной вершиной . То же можно сделать с простым циклом. Тем самым устанавливаются следующие свойства цепей:

- всякая цепь содержит элементарную подцепь с теми же концами;

- простая, но не элементарная цепь содержит элементарный цикл;

- простой цикл, проходящий через ребро е (вершину v), содержит

элементарный подцикл, проходящий через е (v).

2. Легко видеть, что для любого графа отношение между вершинами "быть связанными цепью" есть транзитивное замыкание отношения соседства; оно является рефлексивным (вершина сама представляет собой цепь нулевой длины), симметричным (направление цепи не имеет значения) и транзитивным (склейка, т.е. последовательное прохождение цепей [а, b] и [b, с] дает цепь [а, с]).

Таким образом, это отношение есть отношение эквивалентности. Вершины графа разбиваются на классы эквивалентности. Подграфы, натянутые на эти классы вершин, называются компонентами связности графа (или связными компонентами).

Любые две вершины из одной связной компоненты соединены хотя бы одной цепью, вершины же из разных компонент не связаны цепью.

Граф называется связным, если он имеет ровно одну компоненту связности, т.е. если любые две его вершины связаны цепью. Компоненты связности любого графа G являются максимальными (по включению) связными подграфами графа G, т.е. если к связной компоненте добавить некоторое множество вершин и/или ребер, ей не принадлежащих, то полученный подграф будет несвязным.

На множестве вершин V связного графа можно ввести расстояние как минимальное число ребер в цепи, связывающей

Очевидно, минимум достигается на элементарных цепях.

Свойства расстояния:

3) (неравенство треугольника).

Таким образом, V образует метрическое пространство.