какой маршрут называется замкнутым

Учебная тема: Путь в графе

Содержание

Маршрут, цепь, цикл [ править ]

Маршрут [ править ]

Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны (т.е. соединены).

!В случае простого графа (графа без петель и кратных ребер) маршрут однозначно определяется последовательностью вершин или последовательностью ребер.

Длиной маршрута называют число ребер в нем с учетом повторений.

Цепь [ править ]

Цепь, в которой все вершины различны, кроме, может быть, ее концов, называется простой

Путь – это ориентированная простая цепь

Эйлеров путь (эйлерова цепь) — это путь, проходящий по всем ребрам графа и притом только по одному разу.

Цикл [ править ]

Простой цикл – это замкнутая простая цепь.

Эйлеров цикл — это эйлеров путь, являющийся циклом.

Контур – это простой ориентированный цикл.

Расстояние между вершинами, диаметр, мост [ править ]

Расстояние между вершинами – это длина кратчайшей цепи, соединяющей эти вершины (сама такая цепь называется геодезической) рисунок

Например: расстояние между вершинами V1 и V5 это длина геодезической цепи V1-V2-V4-V5

Диаметр – это самая длинная геодезическая цепь.

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

Например: на рисунке это ребра (2,4), (7,10), (11,12)

Точка сочленения, блок [ править ]

Точка сочленения – это вершина графа v, удаление которой из графа увеличивает число компонентов связности.

Блок – связный граф, не имеющий точек сочленения.

После удаления точки сочленения (вершины V) граф распадается на три блока

Ссылки на буклет и презентацию по данной теме [ править ]

Ресурсы [ править ]

Учебник «Дискретная математика. Курс лекций» Палий И.А.

Материал из википедии: статья «Эйлоров цикл»

Источник

Виды вершин и рёбер графа. Маршруты, цепи, циклы в графах

Виды вершин и рёбер графа

Пример 1. Найти звенья в графе, представленном на рис А (под примером).

Ответ. Звенья данного графа изображены линиями 8 и 11 без указания направления.

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

Пример 2. Найти дуги в графе, представленном на рис А.

Пример 3. Найти петли в графе, представленном на всё том же рис А.

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

Пример 4. Найти голую вершину в графе, представленном на всё том же рис А.

Изолированной называется вершина графа, которая инцидентна одной или нескольким петлям.

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

Пример 5. В графе, представленном на рис А, найти изолированные вершины, смежные и не смежные вершины, вершины, смежные сами с собой.

Кратными называются рёбра, соединяющие одну и ту же пару вершин.

Пример 6. Найти кратные рёбра в графе, представленном на всё том же рис А.

Количество рёбер, инцидентных вершине графа, называется степенью этой вершины графа.

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

Маршрут, в котором все рёбра различны, называется цепью.

Цепь, в которой все вершины, кроме, возможно, первой и последней, различны, называется простой цепью.

Замкнутая цепь с положительной длиной называется циклом. Замкнутая простая цепь с положительной длиной называется простым циклом.

Пример 7. В графе, представленном на рисунке ниже, найти примеры маршрута (указать длину), любой цепи, простой цепи, цепи, не являющейся простой, любого цикла (указать длину), простого цикла (указать длину).

Ответ. В данном графе:

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

Источник

Лекция № 15. Маршруты, цепи и циклы.

Пусть G(V, Е) – неориентированный граф. Рассмотрим конечную последовательность рёбер такую, что любые два соседние ребра имеют одну общую инцидентную вершину . Эту последовательность называется маршрутом графа.

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

Заметим, что одно и то же ребро может встречаться не один раз. Вершина , инцидентная первому ребру маршрута и не инцидентная следующему ребру , называется началом маршрута. Причём если эти рёбра кратные, то необходимо указать, какая именно из двух инцидентных им вершин является началом маршрута. Аналогично определяется конец маршрута. Вершины, инцидентные рёбрам маршрута, за исключением первой и последней, называются промежуточными. Причём, поскольку одной вершине может быть инцидентно несколько рёбер, начало и конец маршрута могут быть в то же время промежуточными точками. Таков, например, маршрут на рисунке 1, где вершина 1 является началом маршрута и, в то же время, промежуточной точкой.

Рисунок 1.

Рассмотрим случай, когда , то есть начало и конец маршрута совпадают. Отметим, что в этом случае маршрут может быть только конечным..

Определение. Незамкнутый маршрут (путь) называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью.

В простой цепи любая вершина маршрута инцидентна не более чем двум его рёбрам.

Определение. Замкнутый маршрут (путь) называется циклическим маршрутом или циклом (контуром). Цикл, в котором все вершины попарно различны, называется простым циклом.

Иначе говоря, простой цикл – это циклический маршрут, в котором любые два соседние ребра имеют одну инцидентную вершину. Последовательности , и представляют один и тот же цикл (рисунок 2). Часто считается, что можно менять порядок рёбер цикла на противоположный, то есть, например, последовательность представляет тот же цикл.

Рисунок 2.

Участок цепи или цикла является цепью; соответственно, участок простой цепи или простого цикла является простой цепью.

Определение. Вершины и называются связанными, если существует маршрут с началом и концом . Наоборот, маршрут с началом и концом называется связывающим эти вершины.

Очевидно, что при существовании маршрута должен также существовать маршрут с началом и концом , в котором рёбра идут в противоположном порядке. Можно показать, что любые две связанные маршрутом вершины можно связать маршрутом , являющимся простой цепью, состоящей из участков маршрута .

Если вершина связана с какой-то вершиной маршрутом , то она, естественно связана с собой маршрутом, состоящим из маршрутов и . Более того, принято считать, что изолированная вершина также связана сама с собой, то есть отношение связности, заданное на множестве вершин данного графа рефлексивно. Оно также симметрично и транзитивно, а поэтому является отношением эквивалентности. Тогда оно порождает разбиение множества на непересекающиеся подмножества такие, что вершины одного подмножества связаны между собой и не связаны с вершинами другого подмножества . Это, в свою очередь, означает, что граф может быть разложен в прямую сумму подграфов: .

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

Поэтому все подграфы связного графа связны и называются связными компонентами графа .

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

Штрихи в обозначении используются, потому что не обязательно рёбра под одинаковыми индексами будут совпадать.

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

Определение. Минимальная длина простой цепи с началом в вершине и концом в вершине называется расстоянием между этими вершинами. Обозначается: .

Расстояние между любой вершиной и ею самой равно 0. Ему соответствует нулевой маршрут, не содержащий рёбер. Для любой пары различных вершин и выполняется , так как связывающая их цепь состоит хотя бы из одного ребра. Вообще, расстояние удовлетворяет аксиомам метрики:

1) , причём тогда и только тогда, когда ;

2) .

Также для расстояния выполняется неравенство треугольника: для любых трёх вершин выполняется неравенство: .

Это позволяет, для простоты рассуждений, измерять расстояние между вершинами по числу рёбер простой цепи, соединяющей их (тем более, что геометрические характеристики рёбер мы не учитываем)..

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

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

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

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

Замечание. Граф может иметь более одного центра. Например, в полном неориентированном графе, в котором две любые различные вершины соединены ребром, радиус равен единице, а любая вершина является центром.

Пусть — конечный, связный граф, число рёбер которого равно . Из соображений, изложенных при изучении комбинаторики, можно сделать очевидный вывод. Количество последовательностей рёбер этого графа конечно и равно . Следовательно, конечно и количество простых цепей, в которых рёбра не повторяются.

Определение. Протяжённостью называется максимальная из длин связывающих эти вершины простых цепей.

Определение. Цепь (цикл) в графе G называется Эйлеровым, если она проходит по одному разу через каждое ребро графа G.

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

Рисунок 3

Задача, которая привела к появлению понятия Эйлерова цикла, широко известна в истории математики. Это так называемая задача о кенигсбергских мостах. Расположение семи мостов в городе Кенигсберге в начале XVIII века приведено на рисунке 3а. Требуется обойти город, пройдя через каждый мост ровно один раз, и вернуться в исходную точку.

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

Именно решение данной задачи привело Л. Эйлера к доказательству приведённой выше теоремы. Кстати, согласно ей, данная задача неразрешима, поскольку степени всех вершин графа нечётны.

Теорема 15.2. Для того, чтобы связный граф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечетной степени.

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

Определение. Цикл (цепь) в графе G называется Гамильтоновым, если он проходит через каждую вершину графа G ровно один раз.

Пример 1.

— в графе есть и Эйлеров и Гамильтонов циклы

— в графе есть Эйлеров цикл, но нет Гамильтонова

— в графе есть гамильтонов, но нет Эйлерова цикла

— в графе нет ни Эйлерова, ни Гамильтонова цикла

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

Также необходимым условием существования гамильтонова цикла является связность графа.

Источник