Маршруты, циклы в графах

Пусть G – конечный граф. Маршрутом S в G называется последовательность ребер, S = (U1, U2, …Un), * в которой любые соседние два ребра Ui-1, Ui, (i=2, n) имеют общую вершину.

На графах допускаются маршруты, в которых не принимаются во внимание направления ребер. Такие маршруты называются неориентированными.

Пусть на графе определен маршрут (*). Та вершина ребра U1, которая не является общей с вершиной ребра U2, называется начальной вершиной маршрута S.

Аналогично вводится понятие конечной вершины маршрута: та вершина ребра Un, которая не является общей с вершиной Un-1, называется конечной вершиной маршрута S. Остальные вершины маршрута S называются внутренними.

Нуль-маршрутом называется маршрут, не содержащий ребер.

Вершина Ui называется достижимый из вершины Ui, если существует маршрут из Ui в Uj. Для определенности считают, что любая вершина Ui достижима из себя нуль-маршрутом независимо от наличия петель.

Неориентированный граф называется связным, если все его вершины попарно достижимы.

Неориентированный граф называется соотнесенным, если он получен из ориентированного либо смешанного графа заменой всех дуг на ориентированные ребра.

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

Цепь называется циклом, если начальная и конечная вершины цепи равны. Другое определение цикла – замкнутая цепь, которое понимается в первоначальном определении. Цикл называется простым, если все его вершины различны.

Началом (концом) цикла можно считать любую из его вершин.

На ориентированном графе аналогично понятию цепи вводится понятие пути, а аналогично понятию цикла – понятие контура.

Путь – это ориентированная цепь. Контур – это замкнутый путь. Рассмотрим примеры различных маршрутов на графе G.

Маршрут (U4, U1, U2) является простой цепью.

Маршрут (U4, U1, U2, U3, U7, U1) цепью не является. поскольку ребро U1 встречается в нем дважды. Маршрут (U4, U3, U2, U1) представляет цепь, но не простую, поскольку вершина V3 встречается на ней дважды: как начало ребра U1 и как конец ребра U3. Такая цепь содержит в себе цикл. В данном случае в цепи (U4, U3, U2, U1) имеем цикл (U3, U2, U1). Этот цикл простой. Примером не простого цикла может служить маршрут (U1, U2. U3, U7, U6, U5).

Решим задачу 1.3. Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими.

Решение. Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками ребром. Изобразим графы, которые могут соответствовать такой компании.

Итак, ситуация, рассмотренная в задаче, вполне возможна. Но случай соответствует не одной, а двум компаниям, участники одной из них не знакомы с участниками другой.

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

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

Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.

Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их.

Пример. В графе Г вершины А и В – связные, а вершины А и Н – несвязные.

Граф называется связным, если каждые две вершины его связные, т.е. от любой вершины существует маршрут.

Граф называется несвязным, если хотя бы две вершины его несвязные.