Пусть G = G(V,E) – неориентированный граф с вершинами v0, v1, v2, v3, …, vk множества V и ребрами e1, e2, e3, …, ek множества Е.
Определение. Путем (маршрутом) длины k из v0 в vk (или между v0 и vk) называется последовательность v0e1v1e2v2e3v3…v(k-1)ekvk такая, что eі = {ѵі-1, vі}. Таким образом, путь длины k имеет k ребер.
Определение. Если нет рёбер, предшествующих e1, то вершина v0 называется начальной, если нет рёбер, следующих после ek, то вершина vk называется конечной, вершины пути, не являющиеся начальной или конечной, называются внутренними.
Замечание. Для сокращения записи путь можно обозначать через v0, v1, v2, v3, …, vk или e1, e2, e3, …, ek (можно также опустить запятые).
Определение. Простым путем из v0 в vk называется путь, в котором нет повторяющихся вершин.
Пример 1. Для неориентированного графа G, показанного на рис. ниже, определим несколько путей, в том числе простых. Например, из вершины a в вершину f: abdcabdf или acdbabdf – пути длины 7 и abdf или acdf – простые пути длины 3. Простой путь не обязательно самый короткий, например, существуют два пути из вершины f в вершину e: fdbace или fdce – оба являются простыми, хотя они разной длины (длины 5 и 3 соответственно).
Определение. Путь, в котором каждое ребро используется не более одного раза, называется цепью.
Простой цепью называется цепь, в которой нет повторяющихся вершин.
Пример 2. Для неориентированного графа G, показанного на рис. выше, определим несколько цепей, в том числе простых. Например, из вершины a в вершину f: abdf или acdf – простые цепи длины 3. Например, простые цепи из вершины f в вершину e: fdbaceили fdce( длины 5 и 3 соответственно).
Определение. Путь называется циклическим, если начальная и конечная вершины пути совпадают.
Определение. Циклический путь, в котором каждое ребро используется не более одного раза, называется циклом. Простым циклом называется цикл, в котором нет повторяющихся вершин, кроме вершины, которая является начальной и конечной вершиной.
Пример 3. Для неориентированного графа G, показанного на рис. выше, определим, если возможно, цикл (простой цикл). Например, цикл из вершины a: abdca или acdba – простые циклы длины 4.
Определение. Неориентированный граф G называется связным, если имеется путь между любыми двумя его различными вершинами.
Например, неориентированный граф G является связным.
Теорема. Если в неориентированном графе G = G(V, E) существует путь из вершины vi в вершину vj, тогда существует простой путь из вершины vi в вершину vj.
Следствие. Граф G является связным тогда и только тогда, когда между любыми двумя его вершинами существует простой путь.
Заметим, что необязательно, чтобы в неориентированном графе, который не является связным, существовала изолированная (или несколько) вершина, чаще всего такой граф состоит из нескольких связных подчастей.
Пример 4. Неориентированного графа с двумя компонентами связности (см. рис. ниже).
Пример 5. Определим число компонент связности в неориентированном графе G5, показанном на рис. ниже.
Решение примера 5.
1. Неориентированный граф G5 не является связным, т.к. не из любой вершины существует путь в любую другую вершину, например, из вершины 10 нет пути в вершину 7, таким образом, неориентированный граф G5 обладает некоторым числом компонент связности.
2. Графы со множествами вершин {1, 10}, {4, 7, 8}, {2, 3, 5, 6, 9} являются подграфами графа G5, т.к. их вершины составляют подмножества множества вершин G5.
3. Каждый подграф п. 2 графа G5 является связным, следовательно, эти подграфы являются компонентами связности графа G5.
4. Учитывая п. 3, граф G5 имеет три компоненты связности.
Определение. Разрезающим множеством рёбер неориентированного графа G называется множество его рёбер, удаление которых из графа G приводит к увеличению числа компонент связности.
Определение. Разрезом называется минимальное по включению разрезающее множество рёбер.
Пример 6. Определим все разрезы неориентированного графа G6, показанного на рис. ниже.
Решение примера 6.
1. Неориентированный граф G6 связен, т.к. из любой вершины этого графа можно попасть в любую другую вершину. Следовательно, граф G6 имеет одну единственную компоненту связности.
2. Если удалить любое единственное ребро из графа, то число компонент связности не возрастет. Если удалить пару рёбер {1, 2} и {1, 6}, то число компонент связности возрастет, следовательно, разрезы (по определению, наименьшие по включению разрезающие множества) в графе G6 состоят из двух рёбер.
3. Разрезы графа G6: {{1,2}, {1,6}}; {{3,7}, {6,7}}; {{4,5}, {8,5}}; {{7,4}, {7,8}}; {{7,4}, {8,5}}; {{4,5}, {7,8}}.
Определение. Мостом графа называется одноэлементный разрез, при удалении которого число компонент связности возрастает ровно на единицу.
Пример 7. На рисунке ниже показан пример графа, имеющего мост.
Пример 8. На рисунке ниже представлен неориентированный граф G8, определите все мосты графа G8, если таковые имеются.
Решение примера 8.
1. Неориентированный граф G8 не является связным, т.к. … (попробуйте объяснить самостоятельно).
2. Графы со множеством вершин {1, 5, 8}, {2, 3, 4, 6, 7, 9, 10, 11, 12, 13} являются подграфами графа 8, т.к. … (попробуйте объяснить самостоятельно).
3. В подграфе {1, 5, 8} имеется два моста, т.к., удалив рёбра {1, 5} или {5, 8}, число компонент связности увеличится ровно на единицу. В подграфе {2, 3, 4, 6, 7, 9, 10, 11, 12, 13} имеется пять мостов, т.к., удалив одно из рёбер {2, 6} или {3, 6}, или {4, 7}, или {9, 11}, или {10, 12}, число компонент связности увеличится ровно на единицу.
4. Таким образом, учитывая п. 3, в графе G8 ровно семь мостов:
{1, 5}, {5, 8}, {2, 6}, {3, 6}, {4, 7}, {9, 11}, {10, 12}.
Упражнение.
Для графов, приведённых ниже:
1) запишите простой путь и если возможно, путь (маршрут) заданного неориентированного графа , не являющийся простым;
2) запишите, если возможно, пример цепи и цикла заданного неориентированного графа, укажите, являются ли они простыми;
3) укажите, имеет ли заданный неориентированный граф разрезающее множество, разрез или мост.