Пути. Циклы. Цепи в графах
Пусть G = (V, E) некоторый граф. Путем (маршрутом) в графе G, соединяющим вершины v1 и vn, называется любая чередующаяся последовательность вершин и ребер вида v0,e 0,v1,e1,v2,e 2…vn-1,e n-1,vn, в которой каждое ребро ei инцидентно вершинам vi и vi+1.
Путь называется замкнутым, если его начальная и конечная вершины совпадают.
Путь называется цепью, если все его ребра различны.
Цепь называется простой, если все ее вершины различны.
Замкнутая цепь называется циклом.
Цикл называется простым, если его вершины не повторяются.
Вот схематическое изображение простого цикла:
А вот схематическое изображение цикла, не являющегося простым:
Для пути v0, e 0 ,v1, e1 , ….vn число ребер n называется длиной пути.
Две вершины графа могут быть связаны некоторым путем: их называют связанными. Например, в графе
a
1
a2 a3 . a4
вершины a3 и a5 связаны (путем 
), а вершины a4 и a1 нет.
Простой граф – это граф, не содержащий петель и кратных ребер.
Граф называется связным, если для любой пары его вершин существует соединяющая их простая цепь. Т.о. граф связен, если из любой его вершины можно прийти к любой другой. Таким образом, выше приведен пример графа несвязного. Связной компонентой графа называется такой его подграф, который является сам по себе графом связным и при этом совпадающим с любым другим содержащим его связным подграфом. Таким образом, связный граф обладает единственной связной компонентой — это он сам. А вот пример графа с тремя связными компонентами (имена вершин не имеют значения):
Компонентой связности графа называется максимальный (по числу вершин и ребер) связный подграф этого граф.
Каждый граф или сам является компонентой связности или распадается на компоненты. Граф, содержащий хотя бы две компоненты связности, называется несвязным. Связный граф состоит из одной компоненты связности.
Граф называется эйлеровым, если он содержит цикл, проходящий через все ребра этого графа по одному разу. Такой цикл называется эйлеровым циклом.
Вот пример эйлерова графа:
А вот пример графа, не являющегося эйлеровым:
Обходы графа
Во многих задачах, решаемых с использованием графов, требуется проложить маршрут от одной вершины графа к другой или обойти все его вершины, учитывая те или иные ограничения.
Смысл такой задачи на интуитивном уровне ясен, но требуется уточнить понятия, используемы при решении подобного рода задач.
Прежде всего, уточним термины «маршрут», «цепь», «цикл» и «путь». Эти четыре понятия находятся в следующем соотношении: пути и циклы – это особые виды цепей, цепь – особый вид маршрута.
Маршрут – это последовательность вершин и ребер графа, следуя по которым, можно попасть из одной его вершины в другую.
Цепь – это маршрут без повторяющихся ребер.
Путь – это цепь, все вершины которой (за исключением, быть может, начальной и конечной) различны.
Цикл – это цепь, у которой совпадают начальная и конечная вершины, а все остальные различны.
Можно составить следующие маршруты из А в С в графе G:
М1: А – е1 – В – е3 – С (путь);
М2: А – е2 – Е – е6 – Д – е7 – Д – е6 – Е – е5 – С (не цепь);
М3: А – е1 – B – е3 – C – е5 – Е – е4 – С (цепь, но не путь).
Циклы:
А – е1 – В – е3 – С – е4 – Е – е2 – А;
Е – е4 – С – е5 – Е;
Граф называют связным, если из каждой его вершины существует путь в любую другую его вершину. Граф, рассмотренный в примере, является, связным. Если удалить из него ребро , то он потеряет связность и распадется на компоненты: одна из компонент будет содержать вершину Д и петлю , вторая компонента – вершины А,В,С,Е, связанные между собой всеми оставшимися ребрами.
Для представления данных в алгоритмах на дискретных структурах часто используются графы, которые называются деревьями.
Деревом называют связный неорграф, не содержащий циклов.
На рис. 6.8 показано, так называемое, корневое дерево. Одна из вершин корневого дерева (вершина 1) выделена, ее называют корнем дерева. Оставшиеся вершины разбиты на поддеревья (поддерево с вершинами 2,5,6 и поддерево 4,7,8,9). Вершины 5,6,3,7,8,9 называют листьями дерева. Несвязный неорграф, компонентами которого являются деревья, называют лесом.
Если граф связный, но не является деревом, в нем всегда можно выделить часть, включающую все вершины и образующую дерево. Такую часть графа называют остовом графа. Если граф несвязен, то можно превратить в дерево каждую его компоненту. Полученная совокупность деревьев носит название остовного леса.
Вообще говоря, в графе можно выделить несколько различных остовов. Каждый из них будет являться деревом, включающим все вершины графа, а следовательно, число ребер любом из остовов будет на единицу меньше числа вершин графа. Если выделен какой-либо остов, то все ребра графа, не вошедшие в этот остов, образуют коостов, соответствующий данному остову.
Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Пусть G связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G) – 1 ребер. Таким образом, любое остовное дерево графа G есть результат удаления из G ровно m(G)-(n(G)-1)=m(G)-n(G)+1 ребер.
На рис. 6.9 показан пример выделения деревьев, остовов и коостовов из графа .
Теория графов. Термины и определения в картинках
В этой статье мы познакомимся с основными терминами и определениями Теории графов. Каждый термин схематично показан на картинках.
Самый объёмный модуль на курсе «Алгоритмы и структуры данных» посвящён теории графов.
Граф — это топологичекая модель, которая состоит из множества вершин и множества соединяющих их рёбер. При этом значение имеет только сам факт, какая вершина с какой соединена.
Например, граф на рисунке состоит из 8 вершин и 8 рёбер.
Очень многие задачи могут быть решены используя богатую библиотеку алгоритмов теории графов. Для этого достаточно лишь принять объекты за вершины, а связь между ними — за рёбра, после чего весь арсенал алгоритмов теории графов к вашим услугам: нахождение маршрута от одного объекта к другому, поиск связанных компонент, вычисление кратчайших путей, поиск сети максимального потока и многое другое.
В этой статье мы познакомимся с основными терминами и определениями теории графов. На курсе “Алгоритмы и Структуры данных” в компании Отус “Теория графов” изучается в самом объёмном модуле из 6 вебинаров, где мы изучаем десяток самых популярных алгоритмов.
Вершина — точка в графе, отдельный объект, для топологической модели графа не имеет значения координата вершины, её расположение, цвет, вкус, размер; однако при решении некоторых задачах вершины могут раскрашиваться в разные цвета или сохранять числовые значения.
Ребро — неупорядоченная пара двух вершин, которые связаны друг с другом. Эти вершины называются концевыми точками или концами ребра. При этом важен сам факт наличия связи, каким именно образом осуществляется эта связь и по какой дороге — не имеет значения; однако рёбра может быть присвоен “вес”, что позволит говорить о “нагруженном графе” и решать задачи оптимизации.
Инцидентность — вершина и ребро называются инцидентными, если вершина является для этого ребра концевой. Обратите внимание, что термин “инцидентность” применим только к вершине и ребру.
Смежность вершин — две вершины называются смежными, если они инцидентны одному ребру.
Смежность рёбер — два ребра называются смежными, если они инцедентны одной вершине.
Говоря проще — две вершины смежные, если они соединены ребром, два ребра смежные — если они соединены вершиной.
Петля — ребро, инцидентное одной вершине. Ребро, которое замыкается на одной вершине.
Псевдограф — граф с петлями. С такими графами не очень удобно работать, потому что переходя по петле мы остаёмся в той же самой вершине, поэтому у него есть своё название.
Кратные рёбра — рёбра, имеющие одинаковые концевые вершины, по другому их называют ещё параллельными.
Мультиграф — граф с кратными рёбрами.
Псевдомультиграф — граф с петлями и кратными рёбрами.
Степень вершины — это количество рёбер, инцидентных указанной вершине. По-другому — количество рёбер, исходящих из вершины. Петля увеливает степень вершины на 2.
Изолированная вершина — вершина с нулевой степенью.
Висячая вершина — вершина со степенью 1.
Подграф. Если в исходном графе выделить несколько вершин и несколько рёбер (между выбранными вершинами), то мы получим подграф исходного графа.
Идея подграфов используется во многих алгоритмах, например, сначала создаётся подграф их всех вершин без рёбер, а потом дополняется выбранными рёбрами.
Полный граф — это граф, в котором каждые две вершины соединены одним ребром.
Сколько рёбер в полном графе? Это известная задача о рукопожатиях: собралось N человек (вершин) и каждый с каждым обменялся рукопожатием (ребро), сколько всего было рукопожатий? Вычисляется как сумма чисел от 1 до N — каждый новый участник должен пожать руку всем присутствующим, вычисляется по формуле: N * (N — 1) / 2.
Регулярный граф — граф, в котором степени всех вершин одинаковые.
Двудольный граф — если все вершины графа можно разделить на два множества таким образом, что каждое ребро соединяет вершины из разных множеств, то такой граф называется двудольным. Например, клиент-серверное приложение содержит множество запросов (рёбер) между клиентом и сервером, но нет запросов внутри клиента или внутри сервера.
Планарный граф. Если граф можно разместить на плоскости таким образом, чтобы рёбра не пересекались, то он называется “планарным графом” или “плоским графом”.
Если это невозможно сделать, то граф называется “непланарным”.
Минимальные непланарные графы — это полный граф К5 из 5 вершин и полный двудольный граф К3,3 из 3+3 вершин (известная задача о 3 соседях и 3 колодцах). Если какой-либо граф в качестве подграфа содержит К5 или К3,3, то он является непланарным.
Путь или Маршрут — это последовательность смежных рёбер. Обычно путь задаётся перечислением вершин, по которым он пролегает.
Длина пути — количество рёбер в пути.
Цепь — маршрут без повторяющихся рёбер.
Простая цепь — цепь без повторяющихся вершин.
Цикл или Контур — цепь, в котором последняя вершина совпадает с первой.
Длина цикла — количество рёбер в цикле.
Самый короткий цикл — это петля.
Цикл Эйлера — цикл, проходящий по каждому ребру ровно один раз. Эйлер доказал, что такой цикл существует тогда, и только тогда, когда все вершины в связанном графе имеют чётную степень.
Цикл Гамильтона — цикл, проходящий через все вершины графа по одному разу. Другими словами — это простой цикл, в который входят все вершины графа.
Взвешенный граф — граф, в котором у каждого ребра и/или каждой вершины есть “вес” — некоторое число, которое может обозначать длину пути, его стоимость и т. п. Для взвешенного графа составляются различные алгоритмы оптимизации, например поиск кратчайшего пути.
Пока ещё не придуман алгоритм, который за полиномиальное время нашёл бы кратчайший цикл Гамильтона в полном нагруженном графе, однако есть несколько приближённых алгоритмов, которые за приемлимое время находят если не кратчайший, то очень короткий цикл, эти алгоритмы мы также рассматриваем на курсе Отуса — “Алгоритмы и структуры данных”.
Связный граф — граф, в котором существует путь между любыми двумия вершинами.
Дерево — связный граф без циклов.
Между любыми двумя вершинами дерева существует единственный путь.
Деревья часто используются для организации иерархической структуры данных, например, при создании двоичных деревьев поиска или кучи, в этом случае одну вершину дерева называют корнем.
Лес — граф, в котором несколько деревьев.
Ориентированный граф или Орграф — граф, в котором рёбра имеют направления.
Дуга — направленные рёбра в ориентированном графе.
Полустепень захода вершины — количество дуг, заходящих в эту вершину.
Исток — вершина с нулевой полустепенью захода.
Полустепень исхода вершины — количество дуг, исходящих из этой вершины
Сток — вершина с нулевой полустепенью исхода.
Компонента связности — множество таких вершин графа, что между любыми двумя вершинами существует маршрут.
Компонента сильной связности — максимальное множество вершин орграфа, между любыми двумя вершинами которого существует путь по дугам.
Компонента слабой связности — максимальное множество вершин орграфа, между любыми двумя вершинами которого существует путь по дугам без учёта направления (по дугам можно двигаться в любом направлении).
Мост — ребро, при удалении которого, количество связанных компонент графа увеличивается.
Это только основные термины и определения теории графов, которые мы рассматриваем на первом вебинаре модуля “Теория графов”. Цель статьи — дать наглядное и понятное представление об этих терминах, для чего и были нарисованы эти картинки.
29. Маршруты, цепи, пути и циклы
Маршрут в графе G = (V, Е) представляет собой конечную чередующуюся последовательность вершин и ребер v0, е1, v2, е2, … , vk-1, ek, vk, начинающуюся и кончающуюся на вершинах, причем Vi-t и Vi являются концевыми вершинами ребра e1, 1 ≤ i ≤ k. С другой стороны, маршрут можно рассматривать как конечную последовательность таких вершин v0, v1, v2, … , vk, что (vi-1, vi), 1≤ i ≤ k — ребро графа G. Такой маршрут обычно называется v0 – vk — маршрутом, a v0 и vk — концевыми или терминальными вершинами маршрута. Все другие вершины маршрута называются внутренними. Заметим, что ребра и вершины в маршруте могут появляться более одного раза.
Маршрут называется Открытым, если его концевые вершины различны, в противном случае он называется замкнутым. В графе на рис. 12 последовательность v1, e1, v2, е2, v3, е8, v6, e9, v5, e7, v3, e11, v6 является Открытым маршрутом, а последовательность v1, е1, v2, е2, v3, е7, v5, e3, v2, е4, v4, e5, v1—Замкнутым.
Рисунок 12
Маршрут называется Цепью, если все его ребра различны. Цепь называется открытой, если ее концевые вершины различны, в противном случае она называется замкнутой. На рис. 12 цепь v1, e1, v2, e2, v3, e8, v6, e11, v3 — Открытая, а v1, e1, v2, e2, v3, e7, v5, e3, v2, e4, v4, e5, v1 — Замкнутая.
Открытая цепь называется Путем, если все ее вершины различны. Замкнутая цепь называется Циклом, если различны все ее вершины, за исключением концевых. Например, на рис. 12 последовательность v1, e1, v2, e2, v3 является путем, а последовательность v1, e1, v2, e3, v5, e6, v4, e5, v1 — циклом.
Ребро графа G называется циклическим, если в графе G существует цикл, содержащий ребро. В противном случае ребро называется нециклическим. На рис. 12 все ребра, за исключением е12, циклические.
Число ребер в пути называется Длиной пути. Аналогично определяется Длина цикла.
Необходимо указать следующие свойства путей и циклов.
1. Степень каждой не концевой вершины пути равна 2, концевые вершины имеют степень, равную 1.
2. Каждая вершина цикла имеет степень 2 или другую четную степень. Обращение этого утверждения, а именно то, что ребра подграфа, в котором каждая вершина имеет четную степень, образуют цикл,— неверно.
3. Число вершин в пути на единицу больше числа ребер, тогда как в цикле число ребер равно числу вершин.
Маршруты, цепи, циклы в графах
Значительная часть теории графов и ее приложений занимается вопросами существования так называемых маршрутов, т. е. последовательностей ребер, обладающих определенными свойствами.
Определение 4-14- Пусть G= (V, Е) — граф. Маршрутом длины, к из вершины v в вершину w (или (щ гф-маршрутом) в графе G называется последовательность вершин До, V. щ) (необязательно различных) е V таких, что Vq = v, Vk = w, и (щ_i, vt) е Е для всех г — 1,2. к. Вершины v и w называются концевым,и (v — начальной, w — конечной) вершинами маршрута, а остальные вершины — внутренними.
Ясно, что маршрут можно задать и последовательностью ребер: (ei = (гд, г’1), во = (v, гь). ед. = (vk-i, Vk)) • Любой участок маршрута сам я в л яется м ар ш рутом.
Определение 4-15. Маршрут называется цепью, если все его ребра различны и простой цепью, если все его вершины (возможно, кроме концевых вершин) различны.
Определение 4-16. Если в маршруте До,щ,щ) начальная и конечная вершины совпадают До = г;Д, то он называется замкнутым маршрутом. При этом обычно считают, что последовательности (vo,vi. vk), (vi. Vk,v0), — различные записи од-
ново и того же маршрута. Замкнутая цепь называется циклом, а замкнутая простая цепь простым циклом,.
Пр и м е р 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
Следствие 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 ребер, поэтому делаем вывод, что простых циклов нечетной длины в нем нет. Значит, он двудольный.