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

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

Маршрутом в графе G называется чередующаяся последовательность вершин и ребер v0, x1, v1,..., vn-l xn, 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 определяются аналогично.