5.2. Связность

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

, (1)

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

. (2)

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

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

(3)

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

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

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

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

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

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

5.3. Подграфы

Граф называется подграфом графа G=[N , A], если N^’ и A^’ являются подмножествами N и А, причем ребро содержится в А' только в том случае, если его концевые вершины содержатся в N^’.

Пусть N' - некоторое подмножество множества вершин гра­фа G=[N , A] и пусть А'- множество всех ребер графа G, концевые вершины которых входят в N'. Тогда граф называется вершинно-порожденным подграфом графа G. Обозначим через А' некоторое подмно­жество множества ребер графа G и пусть N' есть множество всех вершин графа G, инцидентных ребрам из А'. Тогда граф называется реберно-порожденным подграфом.