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

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

Маршрутом в графе 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 определяются аналогично.

Степени

Степеньювершины vi в графе G - обозначается di или deg vi- называется число ребер, инцидентных vi. Поскольку каждое ребро инцидентно двум вершинам, в сумму степеней вершин графа каждое ребро вносит двойку. Таким образом, мы приходим к утверждению, которое установлено Эйлером [2] и является исторически первой теоремой теории графов.

Теорема..2,1,Сумма степеней вершин графа G равна удвоенному числу его ребер:

Следствие2.1 (а).В любом графе число вершин с нечетными степенями четно

В (р, q)-графе 0<deg< p-1 для любой вершины v. Минимальная степень вершин графа G обозначается через min deg G или(G), максимальная — через max deg G=(G). Если(G) =(G)=r, то все вершины имеют одинаковую степень и такой граф G называетсярегулярным(илиоднородным)степениr. В этом случае говорят о степени графа и пишут degG = r.

Регулярный граф степени 0 совсем не имеет ребер. Если G — регулярный граф степени 1, то каждая его компонента содержит точно одно ребро; в регулярном графе степени 2 каждая компонента — цикл, и, конечно, обратно. Первые интересные регулярные графы имеют степень 3; такие графы называются кубическими. На рисунке показаны два регулярных графа с 6 вершинами.

Следствие 2.1 (б).Каждый кубический граф имеет четное число вершин.

Полезно дать названия вершинам с малыми степенями. Вершина v называется изолированной, если deg u=0, иконцевой(иливисячей), если deg u=1.