СВЯЗНОСТЬ

Пусть G – неориентированный граф. Маршрутом в G называется такая конечная или бесконечная последовательность ребер

, (1)

что каждые два соседних ребра и имеют общую концевую точку. Таким образом, можно записать

. (2)

Одно и то же ребро а может встретиться в маршруте несколько раз. Если в (1) нет ребер, предшествующих , то называется начальной вершиной S, а если нет ребер, следующих за , то называется конечной вершинойS. Любая вершина в (2), принадлежащая двум соседним ребрам и , называется внутренней, или промежуточной,вершиной. Маршрут называется нетривиальным, если он содержит хотя бы одно ребро.

Если маршрут S имеет как начальную вершину , так и конечную вершину , то можно записать

(3)

и называть и концевыми точками или концами маршрута S. Будем говорить, что S есть маршрут длины n, соединяющий и . Если , то маршрут будет называться циклическим.

Маршрут называется цепью, а циклический маршрут – циклом, если каждое его ребро встречается в нем не более одного раза; вершины в цепи могут повторяться и несколько раз. Нециклическая цепь называется простой цепью, если в ней никакая вершина не повторяется. Цикл с концом называется простым циклом, если не является в нем промежуточной вершиной и никакие другие вершины не повторяются.

Теорема 3. Для того чтобы граф G представлял собой простой цикл, необходимо и достаточно, чтобы каждая его вершина имела степень 2.

Для ориентированного графа можно вводить как неориентированные маршруты, цепи и простые цепи, не принимая во внимание ориентации ребер, так и ориентированные маршруты (цепи, простые цепи), в которых все ребра (2) проходятся в направлении их ориентации. Ориентированную цепь называют также путем, а ориентированный цикл – контуром.

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

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