электронный учебник

"Экономико-математические методы"

 

На главную страницу

Графы и сети. Потоки в сетях

В конец страницы

14.2.  СВЯЗНОСТЬ

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

                                                 ,                           (14.1)

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

                        .        (14.2)

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

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

                                                                                           (14.3)

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

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

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

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

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

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

Назад     К началу страницы     Вперед