Что такое маршрут в графе

Маршруты, цепи, циклы

1.1. Маршруты, цепи, циклы 1.1.1. Определения Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер v₁, e₁, v₂, e₂, . ,v_k ,e_k,v_k+1, в которой любые два соседних элемента инцидентны. Это определение подходит также для псевдо-, мульти- и орграфов. Для «обычного» графа достаточно указать только последовательность вершин или только последовательность ребер. Если v₁=v_k+1, то маршрут замкнут, иначе открыт. Если все ребра различны, то маршрут называется цепью. Если все вершины цепи различны, то цепь называется простой. Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G) (является инвариантом). Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл — контуром.

Рекомендуемые материалы

Даны графы G1 и G2. Найти G1UG2, G1∩G2, G1+G2, G1∙G2. Для графа G1UG2 найти матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1.

Математика

В контракте предусматривается погашения обязательства в сумме S = 34 тысяч рублей через n = 320 дней. Первоначальная сумма долга составляет P = 30 тысяч рублей. Определите доходность (в процентах) ссудной операции в виде простой годовой ставки нараще

Математика
Вейль — О философии математики — 1934
Математика
Дифференциальные уравнения для электрической цепи
Математика
Марковские цепи
Математика
Исследование электрической цепи переменного тока при последовательном соединении
Математика

Пример В графе, диаграмма которого приведена на рис. 3.10:
1. v₁,v₃,v₁,v₄ — маршрут, но не цепь; 2. v₁, v₃, v₅, v₂, v₃, v₄ — цепь, но не простая цепь; 3. v₁, v₄, v₃, v₂, v₅ — простая цепь; 4. v₁, v₃, v₅, v₂, v₃, v₄, v₁— цикл, но не простой цикл; 5. v₁,v₃,v₄ — простой цикл.
Рис. 3.10. Маршруты, цепи, циклы Две вершины графа называются связанными, если существует маршрут, соединяющий эти вершины. Граф называется связным, если любая пара его вершин связанна. Граф называется деревом, если он связен и не содержит циклов. 1.1.2. Эйлеровы графы Вернемся к историческому примеру о Кенигсбергских мостах. В каком случае в графе можно найти цикл, в котором каждое ребро участвует ровно один раз? Цикл, содержащий каждое ребро ровно один раз, называется эйлеровым. Граф, содержащий эйлеровый цикл, называется эйлеровым графом. Теорема (критерий эйлеровости графа): конечный граф G(V,E) является эйлеровым, тогда и только тогда, когда он связен и степени всех его вершин – четны. Цепь, содержащая каждое ребро ровно один раз, называется эйлеровой. Граф, содержащий эйлерову цепь, называется полуэйлеровым графом. Теорема (критерий полуйлеровости графа): конечный граф G(V,E) является полуэйлеровым, тогда и только тогда, когда он связен и точно две го вершины имеют нечетную степень. 1.1.3. Гамильтоновы графы Кроме эйлеровых графов рассматриваются также гамильтоновы графы. Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие», придуманной Гамильтоном в позапрошлом веке: нужно обойти все вершины графа, диаграмма которого показана на рис. 3.11 (в исходной формулировке это были названия столиц различных стран), по одному разу и вернуться в исходную точку. Этот граф представляет собой укладку додекаэдра. Рис. 3.11. Задача «Кругосветное путешествие» Если граф имеет простой цикл, содержащий все вершины графа (по одному разу), то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом. Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф. Теорема (Дирак). Если в графе G(V, E) для любой вершины v выполняется: (v) р/2, то граф G является гамильтоновым. Рассмотрим следующую задачу, известную как задача коммивояжера. Имеется р городов, расстояния между которыми известны. Коммивояжер должен посетить все р городов по одному разу, вернувшись в тот, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным. Очевидно, что задача коммивояжера — это задача отыскания кратчайшего гамильтонова цикла в полном графе. Можно предложить следующую простую схему решения задачи коммивояжера: сгенерировать все р! возможных перестановок вершин полного графа, подсчитать для каждой перестановки длину маршрута и выбрать из них кратчайший. Очевидно, такое вычисление потребует огромного количества шагов. Как известно, р! с ростом р растет быстрее, чем любой полином от р, и даже быстрее, чем 2 Р . Таким образом, решение задачи коммивояжера описанным методом полного перебора оказывается практически неосуществимым даже для сравнительно небольших р. Более того, известно, что задача коммивояжера принадлежит к числу так называемых NP-полных задач. Вкратце суть проблемы NP-полноты сводится следующему. В различных областях дискретной математики, комбинаторики, логики и т. п. известно множество задач, принадлежащих к числу наиболее фундаментальных, для которых, несмотря на все усилия, не удалось найти алгоритмов решения, имеющих полиномиальную трудоемкость. Более того, если бы удалось отыскать эффективный алгоритм решения хотя бы одной из этих задач, то из этого немедленно следовало бы существование эффективных алгоритмов для всех остальных задач данного класса. На этом основано общепринятое мнение, что таких алгоритмов не существует. Полезно сопоставить задачи отыскания эйлеровых и гамилыоновых циклов, рассмотренные в этом и предыдущем разделах. Внешне формулировки этих задач очень похожи, однако они оказываются принципиально различными с точки зрения практического применения. Уже давно Эйлером получено просто проверяемое необходимое и достаточное условие существования в графе эйлерова цикла. Что касается гамильтоновых графов, то для них не известно необходимых и достаточных условий. На основе необходимого и досточного условия существования эйлерова цикла можно построить эффективные алгоритмы отыскания такого цикла. В то же время задача проверки существования гамильтонова цикла оказывается NP-полной (также как и задача коммивояжера). Известно, что почти нет эйлеровых графов, и эффективный алгоритм отыскания эйлеровых циклов редко оказывается применимым на практике. Теорема: Эйлеровых графов почти нет (E(p) – число эйлеровых графов с p вершинами, G(p) – число всех графов с p вершинами): . С другой стороны, можно показать, что почти все графы гамильтоновы. Теорема: (H(p) – число гамильтоновых графов с p вершинами, G(p) – число всех графов с p вершинами): . Таким образом, задача отыскания гамильтонова цикла или эквивалентная задача коммивояжера являются практически востребованными, но для них неизвестен (и, скорее всего, не существует) эффективный алгоритм решения.

Заключение

Обратите внимание на лекцию «3.2 Отсечение выпуклым многоугольным окном». В качестве моделей графы удобно использовать в тех случаях, когда рассматриваются системы каких-либо объектов, между которыми существуют определенные связи а также в тех случаях, когда изучается структура системы, возможности ее функционирования. В информатике графы используются в следующих разделах: — операционные системы; — алгоритмизация; — структуры данных; — моделирование и др.

Поделитесь ссылкой:

Маршруты на графах

Пусть дан неориентированный граф . Маршрутом длиныназывается некоторая последовательностьрёбер, такая, что вершины двух соседних рёбер последовательности совпадают. Примерами маршрутов на графе (рис.7) могут служить следующие последовательности рёбери. Первый из этих маршрутов соединяетс. Второй образует замкнутый маршрут, проходя через, приводит в ту же вершину, из которой начался. Две вершины графа называются связанными, если существует маршрут, соединяющий эти вершины. Граф, любая пара вершин которого связана, называется связным графом. Граф (рис. 7) не является связным, отсутствуют маршруты из визви т. д. Граф(рис. 11) является связанным, а его суграф и подграф не являются связанными. Маршрут, все рёбра которого различны, называютсяцепью. Цепь, проходящая через различные вершины, называется простой (элементарной) цепью. Замкнутая цепь называется циклом, а цикл проходящий через различные вершины – простым циклом. Так в графе (рис.7) маршрут является простой цепью, маршрутциклом. На практике большое значение имеют задачи о нахождении различного рода маршрутов. Наиболее известные из них эйлеров и гамильтонов циклы. Цикл, содержащий все рёбра графа, называется эйлеровым, а граф, имеющий эйлеров цикл, называется эйлеровым графом. Если эйлеров граф плоский, то его можно изобразить одним росчерком пера (не отрывая пера от бумаги), причем начальная и конечная вершины совпадают. На рисунке 12 изображен граф обход всех рёбер которого ровно один раз возможен по маршруту: . Рисунок 12 Вопрос о существовании эйлерова графа разрешается следующей теоремой: Теорема. Конечный, неориентированный граф является эйлеровым тогда и только тогда, когда он связный и степени всех его вершин четны. Граф (рис. 12) эйлеров, т. к. он связан, степени равны двум, а степеничетырём. Простой цикл, который проходит через все вершины графа, называется гамильтоновым. Условий, гарантирующих существование в графе гамильтонова цикла, математиками пока не установлено.

Пример задачи на нахождение гамильтонова цикла. Задача коммивояжера

Пусть имеется несколько связанных между собой пунктов (городов). Выходя из фиксированного пункта, коммивояжер должен вернуться в него, посетив все пункты ровно один раз. Обычно задача усложняется введением дополнительного ограничения: например, пройти маршрут за самое короткое время или с минимальными затратами на транспорт. Отсутствие условий существования гамильтонова цикла приводит к тому, что, приступая к решению задачи неизвестно, имеет ли она вообще решение или нет. На рисунках 13 и 14 представлены соответственно граф, имеющий гамильтонов цикл, и не имеющий такового. Рис. 13 Рис. 14 В ориентированном графе маршруты называются ориентированными: начальная вершина каждой последующей дуги маршрута должна совпадать с конечной вершиной предыдущей дуги. Если рассматривать изображение ориентированного графа, то движение по маршрутам на нём должно осуществляться только в направленияx, указанных стрелками. Маршрут, не содержащий повторяющихся дуг, называется путем. Путь, не содержащий повторяющихся вершин, называется простым путем. Замкнутый путь называется контуром. Простой контур – контур, не имеющий повторяющихся вершин. Если в графе содержится хотя бы один контур, то это контурный граф.

30.03.2015 485.38 Кб 98 Аналитическая геометрия.doc

30.03.2015 454.66 Кб 89 Введение в теорию графов.doc

30.03.2015 438.27 Кб 103 Векторная алгебра.doc

30.03.2015 297.98 Кб 83 Вычисление производной.doc

30.03.2015 437.25 Кб 135 Графики функций.doc

30.03.2015 143.36 Кб 96 Дискретная математика Теория графов Веснин.doc

30.03.2015 2.42 Mб 258 Дифференциальные уравнения.doc

Ограничение

Для продолжения скачивания необходимо пройти капчу:

Путь в графе

Путь в графе G = (V,E) — последовательность вершин $v_i \in V$ при $i = 1, \dots , k$ , таких, что две любые последовательные вершины соединены хотя бы одной дугой из E .

Число k вершин в пути называется его длиной. Каждая из пар двух последовательных вершин называется его звеном.

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

Wikimedia Foundation . 2010 .

Битва на небесах (фильм)
Печора (река)

Смотреть что такое «Путь в графе» в других словарях:

Путь (в графе) — Путь в графе G = (V,E) последовательность вершин при , таких, что две любые последовательные вершины соединены хотя бы одной дугой из E. Число k вершин в пути называется его длиной. Каждая из пар двух последовательных вершин называется его звеном … Википедия
Путь в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
путь — маршрут — [http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=4126] путь Термин теории графов, последовательность дуг (к концу одной примыкает начало другой) в ориентированном (направленном) графе. В сетевом графике принято для краткости … Справочник технического переводчика
Путь — [path] термин теории графов, последовательность дуг (к концу одной примыкает начало другой) в ориентированном (направленном) графе. В сетевом графике принято для краткости обозначать П. только указанием событий, через которые он проходит (как… … Экономико-математический словарь
Путь (теория графов) — У этого термина существуют и другие значения, см. Путь. Путь (Цепь) в графе последовательность вершин при , таких, что две любые последовательные вершины соединены хотя бы одной дугой из . Число рёбер в пути называется его длиной. Каждая из пар… … Википедия
Простой путь в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Эйлеров путь — Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. Эйлеров путь (эйлерова… … Википедия
Остаточный путь в транспортном графе — Остаточный путь в транспортной сети путь в транспортной сети при данном потоке от истока до стока, для каждой соседней по пути пары вершин (u,v) которого c(u,v) f(u,v) больше нуля. Используется в простом доказательстве Теоремы Форда Фалкерсона.… … Википедия
Определение Святейшего Синода о графе Льве Толстом — Эта статья входит в тематический блок Толстовство Российские сподвижники П. Бирюков · Бодянский · В. Булгаков · Горбунов Посадов · Гусев · Наживин · П. Николаев · … Википедия
Критический путь графа — путь максимальной длины в ориентированном ациклическом графе. Его длина является минимальной из всех возможных высот у ярусно параллельной формы данного ациклического графа. При аналитическом задании графа нахождение длины его критического пути… … Википедия

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

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

Определение 4-14- Пусть G= (V, Е) — граф. Маршрутом длины, к из вершины v в вершину w (или (щ гф-маршрутом) в графе G называется последовательность вершин До, V. щ) (необязательно различных) е V таких, что Vq = v, Vk = w, и (щ_i, v_t) е Е для всех г — 1,2. к. Вершины v и w называются концевым,и (v — начальной, w — конечной) вершинами маршрута, а остальные вершины — внутренними.

Ясно, что маршрут можно задать и последовательностью ребер: (ei = (гд, г’1), во = (v, гь). ед. = (vk-i, Vk)) • Любой участок маршрута сам я в л яется м ар ш рутом.

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

Определение 4-16. Если в маршруте До,щ,щ) начальная и конечная вершины совпадают До = г;Д, то он называется замкнутым маршрутом. При этом обычно считают, что последовательности (vo,vi. v_k), (vi. Vk,v₀), — различные записи од-

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

Пр и м е р 4.7. Привести пример маршрута, цепи, цикла, простой цепи и простого цикла в графе, заданном на рис. 22.

Маршрутом в данном графе, например, является следующая последовательность вершин (гд, г д, г у, гд, гц, го, гд). Однако данный маршрут не является цепью, так как содержит одинаковые ребра. Цепью, например, является следующий маршрут (гд, 1’2, г’б, г/Д, v4, гд, v$). Примером простой цепи может служить маршрут (гд, гд, гдц гд, гд). Циклом является замкнутая цепь, например, (гд, го/ее, г?з, гд, го, гд, гд). Простая цепь (го,гд,г/’з, гд, гд) является простым циклом.

Любая цепь является подграфом. Любой участок цепи или цикла — это цепь, а участок простой цепи или простого цикла — простая цепь.

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

Справедливы следующие утверждения:

1) для различных вершин v^w любой (го г/фмаршрут содержит простую (гд гг;)-цепь;
2) всякий цикл содержит простой цикл;
3) объединение двух несовпадающих простых (уду)-цепей содержит простой цикл.

Следующая теорема позволяет по матрице смежности графа исследовать его маршруты ([14] §4.3).

Теорема 4.3. Если C(G) — матрица смежности графа (С, то (гщ)-й элемент матрицы C k (G) = C(G). G(G) равен числу (гд, гд)-

маршрутов длины к.

Следствие 1. В графе G тогда и только тогда существует (гд,гд)- маршрут (/’ДД, когда (г,j)-й элемент матрицы C(G) + C 2 (G) + . + +C n ~ l не равен нулю (п — число вершин графа).

Следствие 2. В графе G тогда pi только тогда существует цикл, содержащий вершину щ, когда (г, г)-й элемент матрицы («(G) + C 2 (G) + + . + C n ~ l (G) не равен нулю.

П р и м е р 4.8. Определить, существуют ли (^2, щ)-маршруты в

графе G, который задан матрицей смежности («(G) = J .

Элемент С24 = 0, значит (^2,^4)-маршрута длины 1 пет.

В матрице C 2 (G) соответствующий элемент равен 0, значит маршрута длины 2 нет.

В графе G существует один (уд, гц)-маршрута длины 3, так как соответствующий элемент в С 3 (С) равен 1. Это маршрут (гд,гц, гд,гц).

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

Определение 4-17. Двудольным называется граф G=(VE), множество вершин которого можно разбить на два подмножества V и Ух (V П Vj = 0) таким образом, что каждое ребро графа G соединяет вершины из разных множеств. Если при этом каждая вершина из одного подмножества смежна с любой вершиной другого подмножества, то граф называется полным двудольным.

На рис. 23 и 24 изображены двудольные графы, причем граф на рис. 24 — полный двудольный.

Справедлива следующая теорема.

Теорема 4.4. Граф является двудольным тогда и только тогда, когда все его простые циклы четной длины.

П р и м е р 4.9. Доказать, что граф, заданный матрицей смеж-

/О 1 0 1 0

hocthC(G) = О 1 О 1 0 двудольный.

Используем теорему 4.3 для вычисления количества циклов данного графа. Чтобы найти количество циклов длины 3, вычислим матрицу С 3 (С7).

Все диагональные элементы матрицы C 3 (G) равны 0, следовательно, циклов длины 3 у данного графа нет. Чтобы найти количество циклов длины 5, вычислим матрицу C 5 (G).

Циклов длины 5 у данного графа тоже нет, так как все диагональные элементы матрицы C 5 (G) равны 0. У графа всего 5 ребер, поэтому делаем вывод, что простых циклов нечетной длины в нем нет. Значит, он двудольный.

Похожие публикации:

Как обучается нейросеть

Как определить теоретическую сложность алгоритма

Как установить тензор флоу

Как устроиться программистом без опыта работы и высшего образования