04. Эйлеров цикл и эйлеров граф. Условия существования эйлерова цикла. Задача о разбиении графа на минимальное число цепей
Пусть — граф. Эйлеровым циклом в графе называется такой цикл, который содержит все ребра и все вершины этого графа. Напомним, что, по определению, в циклах не повторяются ребра. Таким образом, при наличии эйлерова цикла в графе этот граф можно
Обойти по всем ребрам, пройдя каждое ребро только один раз. Граф, обладающий эйлеровым циклом, сам называется Эйлеровым.
Вот пример эйлерова графа:
А вот пример графа, не являющегося эйлеровым:
Существует теорема (Теорема Эйлера), полностью описывающая эйлеровы графы:
Граф является эйлеровым тогда и только тогда, когда он связен и все его локальные степени четны.
Таким образом, имеется конкретный способ устанавливать, является или нет данный граф эйлеровым. Однако, если граф окажется эйлеровым, то указать его эйлеров цикл можно только после дополнительных исследований.
В связи с эйлеровыми графами имеется одна классическая задача О минимальном цепном разбиении. Вот ее формулировка.
Пусть — Связный граф и — все его вершины Нечетной степени (на-помним, что в каждом графе число вершин нечетной степени четно). Тогда, если , То минимальное число цепей графа, содержащих в совокупности все его ребра, равно ; Если же , То указанное минимальное число равно 1.
В последней ситуации, указанной в этой формулировке, речь идет, очевидно, об эйлеро-вом графе. В первой же ситуации имеет смысл остановится на принципиальной схеме рассуж-дений. А именно:
построим новый граф , в котором (т. е. добавляется одна новая вершина) и (т. е. добавляется еще ребер);
заметим, что полученный граф является связным и все его локальные степе-ни уже четны; поэтому в нем существует некий эйлеров цикл ;
осуществим обход по циклу , начав и закончив этот обход в вершине ; те цепей, о которых идет речь в обсуждаемом утверждении, будут выделяться в процессе этого обхода так: обход начинается в вершине ; следовательно, следующей за будет некая вершина из G; она и будет началом первой цепи; после некоторого пути надо будет вновь вернуться в ; первая цепь закончится в той вершине из G, из которой осуществится возвращение в ; затем по той
Эйлеровы цепи и циклы
Рассматриваемая задача является одной из самых ста-рей-ших в теории графов. В городе Кенигсберге (ныне Калининград) имелось семь мостов, соединяющих два берега реки Преголь, и два основа на ней друг с другом (рис. 1а). Требуется, начав путешествие из одной точки города прой-ти по всем мостам по одному разу и вернуться в исходную точку.
Если поставить в соответствие мостам ребра, а участкам суши — вершины, то получится граф (точнее псевдограф), в котором надо найти про-стой цикл, проходящий через все ребра. В общем виде эта задача была решена Эйлером в 1736 г.
Определение 1. Эйлеровой цепью в неориентированном графе G называется простая цепь, содержащая все ребра графа G. Эйлеровым циклом назы-вается замкнутая Эйлерова цепь. Аналогично, эйлеров путь в орграфе G — это простой путь, содержащий все дуги графа G. Эйлеров контур в орграфе G — это замкнутый эйлеров путь. Граф, в котором существует эйлеров цикл, называется эйлеровым.
Простой критерий существования эйлерова цикла в связном графе дается следующей теоремой.
Теорема 1. (Эйлер) Эйлеров цикл в связном неориентированном графе G(X, E) существует только тогда, когда все его вершины имеют четную степень.
Доказательство. Необходимость. Пусть — эйлеров цикл в связном гра-фе G, x — произвольная вершина этого графа. Через вершину x эйлеров цикл проходит некоторое количество k (k1) раз, причем каждое прохождение, очевидно, включает два ребра, и степень этой вершины равна 2k, т.е. четна, так как x выбрана произвольно, то все вершины в графе G имеют четную сте-пень.
Достаточность. Воспользуемся индукцией по числу m ребер графа. Эйле-ровы циклы для обычных (не псевдо) графов можно построить начиная с m=3.Легко проверить, что единственный граф с m=3, имеющий все вершины с четными степенями, есть граф K3 (рис. 2). Существование эйлерова цикла в нем очевидно. Таким образом, для m=3 достаточность условий доказываемой теоремы имеет место. Пусть теперь граф G имеет m>3 ребер, и пусть утверждение справедливо для всех связных графов, имеющих меньше, чем m ребер. Зафиксируем произвольную вершину a графа G и будем искать простой цикл, идущий из a в a. Пусть (a, x) — простая цепь, иду-щая из a в некоторую вершину x. Если x a, то цепь можно продолжить из вершины x в некотором направлении. Через некоторое число таких про-дол—же-ний мы придем в вершину zX, из которой нельзя продлить полу-чен-ную про-стую цепь. Легко видеть, что z = a так как из всех остальных вершин цепь может выйти (четные степени!); a в a она начиналась. Таким образом, нами построен цикл , идущий из a в a. Предположим, что построенный про-стой цикл не содержит всех ребер графа G. Удалим ребра, входящие в цикл , из графа G и рассмотрим полученный граф . В графе все вершины имеют четные степени. Пусть — компо-нен-ты связ-нос-ти графа , содержащие хотя бы по одному ребру. Соглас-но пред-поло-же-нию индукции все эти компоненты обладают эйлеровыми циклами 1, 1, …, k соот-вет-ствен-но. Так как граф G связан, то цепь встре-чает каждую из компонент. Пусть первые встречи цикла с ком-понентами происходят соответственно в вершинах x1, x2, …, xk. Тогда про-стая цепь
является эйлеровым циклом в графе G. Теорема доказана.
Замечание. Очевидно, что приведенное доказательство будет верно и для псевдографов, содержащих петли и кратные ребра (см. рис. 1,а).
Таким образом, задача о кенигсбергских мостах не имеет ре-ше-ния, так как соответствующий граф (см. рис. 1,б) не имеет эйлерова цикла из-за не-четности степеней все вершин.
Отметим, что из существования эйле-ро-ва цикла в неориентированном графе G не следует связность этого графа. Напри-мер, неориентированный граф G на рис. 3 обладает эйлеровым циклом и вместе с тем несвязен.
Совершенно также, как теорема 1, могут быть доказаны следующие два утверждения.
Теорема 2. Связный неориентированный граф G обладает эйлеровой цепью тогда и только тогда, когда число вершин нечетной степени в нем равно 0 или 2, причем если это число равно нулю, то эйлерова цепь будет являться и циклом.
Теорема 3. Сильно связный орграф G(X, E) обладает эйлеровым кон-ту-ром тогда и только тогда, когда для любой вершины xX выполняется
Можно также обобщить задачу, которую решал Эйлер следующим обра-зом. Будем говорить что множество не пересекающихся по ребрам простых цепей графа G покрывает его, если все ребра графа G включены в цепи i. Нужно найти наименьшее количество таких цепей, которыми можно покрыть заданный граф G.
Если граф G — эйлеров, то очевидно, что это число равно 1. Пусть теперь G не является эйлеровым графом. Обозначим через k число его вер-шин нечетной степени. По теореме … k четно. Очевидно, что каждая верши-на нечетной степени должна быть концом хотя бы одной из покрывающих G цепей i. Следовательно, таких цепей будет не менее чем k/2. С другой сто-роны, таким количеством цепей граф G покрыть можно. Чтобы убедиться в этом, расширим G до нового графа , добавив k/2 ребер , соединяющих раз-личные пары вершин нечетной степени. Тогда оказывается эйлеровым графом и имеет эйлеров цикл . После удаления из ребер граф разло-жится на k/2 цепей, покрывающих G. Таким образом, доказана.
Теорема 4. Пусть G — связный граф с k>0 вершинами нечетной степени. Тогда минимальное число непересекающихся по ребрам простых цепей, покрывающих G, равно k/2.
Алгоритм построения эйлерова цикла
Для начала отметим, что теорема 1 также дает метод построения эйлерова цикла. Здесь мы рассмотрим несколько иной алгоритм.
Пусть G(X, E) — связный неорентированный граф, не имеющий вершин нечетной степени. Назовем мостом такое ребро, удаление которого из связного графа разбивает этот граф на две компоненты связности, имеющие хотя бы по одному ребру.
1. Пусть a — произвольная вершина графа G. Возьмем любое ребро e1=(a, x1) , инцидентное вершине a, и положим = <e1>.
2. Рассмотрим подграф G1(X, E1). Возьмем в качестве e2 ребро, инци-дентное вершине x1 и неинцидентное вершине a, которое также не является мостом в подграфе G1 (если такое ребро e2 существует!). Получим простую цепь 2 = <e1, e2>.
3. Пусть e2 = (x1, x2), x a. Рассмотрим подграф G2(X, E2) и удалим из него все изо-лированные вер-шины. В полученном подграфе выберем ребро e3E2, инцидентное вершине a, которое не является мостом в под-графе (если такое ребро e3 суще-ству-ет!). Получим простую цепь
Продолжая указанный процесс, мы через конечное число шагов получим эйлеров цикл = <e1, e2, …, en>, где n — число ребер графа G(X, E).
Предположим, что уже построена простая цепь k-1 = <e1, e2, …, ek-1> для k2 методом, указанным в алгоритме. Пусть ek-1 = (xk-2, xk-1) и xk-1 a. Рас-смо-трим подграф , который получается из подграфа Gk-1(X, Ek-1) удалением всех изолированных вершин. Вершина xk-1 в этом подграфе имеет нечет-ную степень, поэтому существует по крайней мере одно ребро ekEk-1, ин-ци-дентное xk-1. Если это ребро единственное, то оно не является мостом в графе . В противном случае вершина a будет связана с некоторой вер-ши-ной единственной цепью, содержащей ребро ek, что противоречит суще-ствованию эйлерова цикла в графе G. Поскольку ek — не мост, то процесс мож-но продолжать, взяв . Если ребро ek не единственное инци-дентное вершине xk-1, то среди этих ребер есть по крайней мере одно, не явля-ющееся мостом. В противном случае один из этих мостов можно выбро-сить так, что вершины xk-1 и a попадут в разные компоненты связности графа . Если xk-1 принадлежит компоненте M, то в этой компоненте все вер-шины имеют четную степень, поэтому существует эйлеров цикл в M, про-хо-дящий через xk-1. Этот цикл содержит все ребра, инцидентные xk-1 и при-над-лежащие , являющиеся одновременно мостами. Получено противоречие, так как ребра из эйлерова цикла мостами быть не могут. Итак, в рассмотренном случае существует ребро ek, инцидентное вершине xk-1 и не являющееся мостом. Значит, и в этом случае процесс можно продолжать, взяв
Из предыдущего следует, что процесс нельзя продолжать тогда и только тогда, когда мы попадем в вершину a, причем степень вершины a относительно непройденных ребер равна нулю. Докажем, что в этом случае построенный цикл — простой цикл. Покажем, что содержит все ребра графа G. Если не все ребра графа G принадлежат , то не принадлежащие ребра порождают компоненты связности C1, …, Cm (m1) в подграфе . Пусть компонента Ci, 1im соединяется с циклом в вершине yi. Если существует ребро e , такое, что e=(yi, a), то при построении цикла было нарушено правило выбора ребра e, что невозможно. Если часть цикла , соединяющая yi и a, состоит более чем из одного ребра, то первое ребро этой части было мостом, и поэтому было нарушено правило вы-бора , что невозможно. Итак, непройденных ребер быть не может, поэ-тому — эйлеров цикл.
Программирование на C, C# и Java
Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode
Поиск элементарных цепей в графе
В этой статье речь пойдет об алгоритме поиска всех элементарных цепей в неориентированном графе. Будет приведено описание алгоритма и его реализация на языке программирования C#.
Цепью в графе называется последовательность ребер 
, когда каждое предыдущее ребро 
соприкасается одним из своих концов со следующим ребром 
. Цепь обозначается последовательностью вершин, которые она содержит (2-5-3-6).
Цепь называется элементарной, если все вершины, входящие в нее, различны.
Приведем пример. Пусть дан граф, как на рисунке ниже:
Все элементарные цепи в нем: 1-2, 1-3-2, 1-2-3, 1-3, 1-2-3-4, 1-3-4, 2-1-3, 2-3, 2-1-3-4, 2-3-4, 3-4.
Пусть граф задан, как G = (V, E), где V — множество вершин графа, а E — множество его ребер. Вершины и ребра можно представить объектами следующих классов:
Как найти количество цепей в графе
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | B enq | 3783 |
| 2 | j iangly | 3669 |
| 3 | t ourist | 3658 |
| 4 | m aroonrk | 3650 |
| 5 | U m_nik | 3541 |
| 6 | f antasy | 3526 |
| 7 | R adewoosh | 3515 |
| 8 | k o_osaga | 3500 |
| 9 | i naFSTream | 3477 |
| 10 | c nnfls_csy | 3427 |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 181 |
| 2 | U m_nik | 180 |
| 3 | -is-this-fft- | 172 |
| 4 | nor | 171 |
| 5 | adamant | 167 |
| 6 | m aroonrk | 166 |
| 7 | antontrygubO_o | 161 |
| 8 | SecondThread | 160 |
| 9 | YouKn0wWho | 156 |
| 10 | kostka | 153 |
GlebsHP → Nebius Welcome Round Editorial
robiul_404 → Suggest a book for Competitive programming..
IanDeHaan → Teams Going to the 2023 ICPC North America Championship
GlebsHP → Nebius Welcome Round (Div. 1 + Div. 2, rated, t-shirts!)
Pakgamer2022 → Need Help!
AAK → Indian ICPC 2022-23 Regionals — Discussion
Vladosiya → Codeforces Round 855 (Div. 3) Разбор
Diegogrc → Companies interested in hiring a Competitive Programming background eng?
adamant → Unexpected application of cosines
sahal → ICPC Dhaka Regional and Preliminary Problemset and Editorials
Kolyanchick → Задача "Крош и битовые операции" — Объяснение решения
appu_nitd → Invitation to Decathlon 2023
orz → Nebius Welcome Round (Div. 1 + Div. 2) screencast and editorial
vovuh → Разбор Codeforces Round #653 (Div. 3)
cpdojo → Introducing cpdojo
OneShhhhhh → Introducing CF-Daily: An Easy Way to Discover Daily Codeforces Challenges
zibada → Google Code Jam Archive
nor → [Tutorial] Floors, ceilings and inequalities for beginners (with some programming tips)
ExplodingKonjac → A ridiculous user script for codeforces: Emojiforces
SirRembocodina → Обратный остаток / деление по модулю – Быстрый гайд
fjuengermann → Codeforces Live Bot (Telegram Bot)
M aksim1744 → Counting primes in $\tilde<<\cal O>>(n^<2/3>\,\,)$
Omkar2003 → Regarding TLE on CF
yh11 → Need help/tutor for preparing for big coding competitions
adamant → The 1st Universal Cup. Stage 7: Zaporizhzhia
Блог пользователя birne
Количество простых цепей в полном графе
Автор birne, 10 лет назад ,
Добрый день! Возникли проблемы с решением следующей задачи. Пусть задан полный граф, в котором содержится n вершин. Найти количество простых цепей длины 1, 2, . n — 1 между парой вершин в этом графе. Наверняка какое-то квадратное ДП, но пока ничего придумать не смог. Заранее спасибо!
количество, простых, цепей