Маршруты и связность

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

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

Указанный маршрут соединяет вершины v0 и vn, и его можно обозначитьv0,vl,v2 . . .vn (наличие ребер подразумевается). Эта последовательность иногда называется

(v0-vn)-маршрутом. Маршрутзамкнут, если v0=vn, иоткрытв противном случае. Маршрут называетсяцепью(trail), если все его ребра различны, ипростой цепью(раth) если все вершины (а следовательно, и ребра) различны. Замкнутая цепь называетсяциклом. Замкнутый маршрут называетсяпростым циклом, если все егоnвершин различны иn>= 3.

В помеченном графе G на рис v1v2v5v2v3-маршрут, который не является цепью, а v1v2v5v4v2v3 — цепь, но не простая цепь, v1v2v5v4- простая цепь и v1v2v5v4-простой цикл.

Обозначим через Сnграф, состоящий из одного простого цикла сnвершинами, и через Рnпростую цепь сnвершинами; С3 часто называюттреугольником.

Граф G называется связным, если любая пара его вершин соединена простой цепью. Максимальный связный подграф графа G называется компонентой связности, или простокомпонентойграфа G. Таким образом, несвязный граф имеет, по крайней мере, две компоненты. Граф на рисунке имеет 10 компонент.

Длина маршрутаv1v2....vn равнаn, т. е. количеству ребер в нем.Обхват графаG - обозначается g(G) -это длина простого кратчайшего цикла графа G (если он есть);окружение, графа G - обозначается с(G) -длина самого длинного простого цикла графа G. Эти понятия не определены в случае, когда в G нет циклов.

Расстояниемd(u, v) между двумя вершинамиuиvграфа G называется длина кратчайшей простой цепи, соединяющей их; еслиuи v не соединены, то полагаем d(u, v) =. В связном графе расстояние является метрикой, т. е. удовлетворяет следующим аксиомам (аксиомы метрики): для любых трех вершин и, v и w

1) d(u, w)>0 и d(u, и)=0 тогда и только тогда, когда u=v;

2) d(u, v)=d(v, и);

3) d(u, v)+d(v, w)> d(u, w).

Кратчайшая простая (u-v)-цепь часто называетсягеодезической.

Диаметрd(G) связного графа G — это длина самой длинной геодезической. Граф G на рисунке имеет обхват g=3, окружение с=4 и диаметр d=2.

Квадрат G²графа G имеет то же множество вершин, что и граф G, т.е V(G²) = V(G), и две вершиныuи v в G2 смежны тогда и только тогда, когда d(u,u)2 в G. Степени G³, G⁴, ... графа G определяются аналогично.