В графе все вершины имеют степень 3 докажите что в нем есть цикл

Теория и подборка задач про графы.

Полезные материалы

Графы (Фоксфорд.Учебник)
Деревья (Фоксфорд.Учебник)
Эйлеровы графы (Фоксфорд.Учебник)
Гамильтоновы графы (Фоксфорд.Учебник)
Планарный граф (Фоксфорд.Учебник)
Ориентированные графы (Фоксфорд.Учебник)

Подборка задач

Доска имеет форму креста, который получается, если из квадратной доски $4 s 4$ выкинуть угловые клетки. Можно ли обойти ее ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по разу?
В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 — по 4 друга, а 10 — по 5 друзей?
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими?
У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?
Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?
Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера?
Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно.
Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?
В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с 7 другими. Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через другие города).
Докажите, что граф с $n$ вершинами, степень каждой из которых не менее $(n – 1)/2$, — связен.
В Тридевятом царстве лишь один вид транспорта — ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний — одна, а из всех остальных городов — по 20. Докажите, что из столицы можно долететь в Дальний (возможно, с пересадками).
В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого.
а) Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?
б) Какое наименьшее число раз придется ломать проволоку, чтобы все же изготовить требуемый каркас?
Докажите, что граф, в котором любые две вершины соединены ровно одним простым путем, является деревом.
Докажите, что в дереве любые две вершины соединены ровно одним простым путем.
Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).
В графе все вершины имеют степень 3. Докажите, что в нем есть цикл.
Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.
В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог?
Докажите, что связный граф, у которого число ребер на единицу меньше числа вершин, является деревом.
Волейбольная сетка имеет вид прямоугольника размером $50 s 600$ клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски?
В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?
Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими из нее ребрами так, чтобы он остался связным.
В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от любого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать в каждом городе, совершив не более
а) 198 перелетов;
б) 196 перелетов.
В стране Озерная 7 озер, соединенных между собой 10 каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов?
В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?
Граф, имеющий 5 вершин, каждая из которых соединена ребром с любой другой, не является плоским.
Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?
Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, — не плоский.
Докажите, что в плоском графе есть вершина, степень которой не превосходит 5.
Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо “красный”, либо “синий” граф не является плоским.
Семиугольник разбит на выпуклые пяти- и шестиугольники, причем так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13.

Источник

Теория и подборка задач про графы.

Полезные материалы

Графы (Фоксфорд.Учебник)
Деревья (Фоксфорд.Учебник)
Эйлеровы графы (Фоксфорд.Учебник)
Гамильтоновы графы (Фоксфорд.Учебник)
Планарный граф (Фоксфорд.Учебник)
Ориентированные графы (Фоксфорд.Учебник)

Подборка задач

Доска имеет форму креста, который получается, если из квадратной доски $4 s 4$ выкинуть угловые клетки. Можно ли обойти ее ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по разу?
В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 — по 4 друга, а 10 — по 5 друзей?
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими?
У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?
Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?
Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера?
Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно.
Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?
В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с 7 другими. Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через другие города).
Докажите, что граф с $n$ вершинами, степень каждой из которых не менее $(n – 1)/2$, — связен.
В Тридевятом царстве лишь один вид транспорта — ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний — одна, а из всех остальных городов — по 20. Докажите, что из столицы можно долететь в Дальний (возможно, с пересадками).
В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого.
а) Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?
б) Какое наименьшее число раз придется ломать проволоку, чтобы все же изготовить требуемый каркас?
Докажите, что граф, в котором любые две вершины соединены ровно одним простым путем, является деревом.
Докажите, что в дереве любые две вершины соединены ровно одним простым путем.
Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).
В графе все вершины имеют степень 3. Докажите, что в нем есть цикл.
Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.
В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог?
Докажите, что связный граф, у которого число ребер на единицу меньше числа вершин, является деревом.
Волейбольная сетка имеет вид прямоугольника размером $50 s 600$ клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски?
В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?
Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими из нее ребрами так, чтобы он остался связным.
В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от любого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать в каждом городе, совершив не более
а) 198 перелетов;
б) 196 перелетов.
В стране Озерная 7 озер, соединенных между собой 10 каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов?
В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?
Граф, имеющий 5 вершин, каждая из которых соединена ребром с любой другой, не является плоским.
Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?
Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, — не плоский.
Докажите, что в плоском графе есть вершина, степень которой не превосходит 5.
Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо “красный”, либо “синий” граф не является плоским.
Семиугольник разбит на выпуклые пяти- и шестиугольники, причем так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13.

Источник

ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ.

Опираясь на приведенные выше определения теории графов, приведем формулировки

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

задач.

Теорема 3.1. Удвоенная сумма степеней вершин любого графа равна числу

его ребер.

Доказательство. Пусть А1, А2, А

3, …, An – вер¬шины данного графа, a p(A1

), р(А2), …, p(An) – степени этих вершин.

Подсчитаем число ребер, сходящихся в каждой вершине, и просуммируем эти числа.

Это рав¬носильно нахождению суммы степеней всех вершин. При таком подсчете

каждое ребро будет учтено дважды (оно ведь всегда соединяет две вершины).

Отсюда следует: p(A1)+р(А2)+ … +p(A

n)=0,5N, или 2(p(A1)+р(А2)+

… +p(An))=N , где N – число ребер. ‡

Теорема 3.2. Число нечетных вершин любого графа четно.

Доказательство. Пусть a1, a2, a3, .,

ak – это сте¬пени четных вершин графа, а b1, b

2, b3, ., bm – степени нечетных вершин графа.

Сумма a1+a2+a3+.+ak+b1

+b2+b3+.+bm ровно в два раза превышает

число ребер гра¬фа. Сумма a1+a2+a3+.+a

k четная (как сумма четных чисел), тогда сумма b1

+b2+b3+.+bm должна быть четной. Это

возможно лишь в том случае, если m – четное, то есть четным является и

число нечетных вершин графа. Что и требовалось доказать. ‡

Эта теорема имеет немало любопытных следствий.

Следствие 1. Нечетное число знакомых в любой компании всег¬да четно.

Следствие 2. Число вершин многогранника, в которых сходится нечетное

число ребер, четно.

Следствие 3. Число всех людей, когда-либо пожавших руку дру¬гим людям,

нечетное число раз, является четным.

Теорема 3.3. Во всяком графе с n вершинами, где n больше

или равно 2, всегда найдутся две или более вершины с оди¬наковыми степенями.

Доказательство. Если граф имеет n вершин, то каждая из них может

иметь степень 0, 1, 2, …, (n-1). Предположим, что в некотором

графе все его вершины имеют различную степень, то есть, и покажем, что

этого быть не может. Действительно, если р(А)=0, то это значит,

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

Х со степенью р(Х)=n-1. В са¬мом деле, эта вершина

должна быть соединена с (n-1) вершиной, в том числе и с А, но

ведь А оказалась изолированной. Следовательно, в графе, имеющем n

вершин, не мо¬гут быть одновременно вершины степени 0 и (n-1). Это

значит, что из n вершин найдутся две, имеющие одинаковые степени.

‡

Теорема 3.4. Если в графе с n вершинами (n больше или

равно 2) только одна пара имеет одинаковую степень, то в этом графе всегда

найдется либо единственная изолированная вершина, либо единственная вершина,

соединенная со всеми другими.

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

пояснении. Содержание этой теоремы хорошо разъясняется задачей: группа,

состоящая из n школьников, обменивается фотографиями. В некоторый

момент времени выяс¬няется, что двое совершили одинаковое число обме¬нов.

Доказать, что среди школьников есть либо один еще не начинавший обмена, либо

один уже завершив¬ший его.

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

содержит ни одного цикла четной длины.

Рисунок 3.1 поясняет условие теоремы. На изображенном графе все 5 простых

циклов четные.

(РИСУНОК 3.1)

Суть теоремы в том, что на этом графе невозможно найти цикл (как простой, так

и непростой) нечетной длины, то есть содержащий нечетное число ребер.

Теорема 3.6. Для того, чтобы граф был эйлеро¬вым, необходимо и

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

Теорема 3.7. Для того чтобы на связном графе можно было бы проложить цепь

АВ, содержащую все его ребра в точности по одному разу, необходимо и

достаточно, чтобы А и В были единственными нечет¬ными вершинами

этого графа.

Доказательство этой теоремы очень интересно и ха¬рактерно для теории графов. Его

также следует счи¬тать конструктивным (обратите внимание на то, как

•использована при этом теорема 3.6). Для доказательства к исходному графу

присоеди¬няем ребро (А, В); после этого все вершины графа станут

четными. Этот новый граф удовлетворяет всем условиям теоремы 3.6, и поэтому в

нем можно про¬ложить эйлеров цикл Ψ. И если теперь в этом цикле

удалить ребро (А, В), то останется искомая цепь АВ

. ‡

На этом любопытном приеме основано доказатель¬ство следующей теоремы, которую

следует считать обоб¬щением теоремы 3.7.

Теорема 3.8. Если данный граф является связ¬ным и имеет 2k вершин

нечетной степени, то в нем можно провести k различных цепей, содержащих

все его ребра в совокупности ровно по одному разу.

Теорема 3.9. Различных деревьев с n перенумерованными вершинами

можно построить nn-2.

По поводу доказательства этой теоремы сделаем одно замечание. Эта теорема

известна, в основном, как вывод английского математика А. Кэли (1821-1895).

Графы-деревья издавна привлекали внимание ученых. Се¬годня двоичные деревья

используются не только ма¬тематиками, а и биологами, химиками, физиками и

инженерами (подробнее об этом – в параграфе 6).

Теорема 3.10. Полный граф с пятью верши¬нами не является плоским.

Доказательство. Воспользуемся формулой Эйлера: В-Р+Г=2,

где В – число вершин плоского графа, Р – число его ре¬бер, Г

– число граней. Формула Эйлера справедлива для плоских связных графов, в которых

ни один из многоугольников не лежит внутри другого. На рисунке 3.2, а изображен

граф, к которому формула не применима – заштрихованный много¬угольник находится

внутри другого. Справа приведено изображение графа, к которому формула

применима.

(РИСУНОК 3.2)

Эту формулу можно доказать методом математиче¬ской индукции. Это доказательство

мы опускаем. За¬метим только, что формула справедлива и для пространственных

многогранников. Пусть все пять вершин графа соединены друг с дру¬гом (рис.

3.2). Замечаем, что на графе нет ни одной грани, ограниченной только двумя

ребрами. Если через φ1 обозначить число таких граней,

то φ2=0. Далее рассуждаем от противного, а именно:

пред¬положим, что исследуемый граф плоский. Это значит, что для него верна

формула Эйлера. Число вершин в данном графе В=5, число ребер

Р=10, тогда число граней Г=2-В+Р=2-5+10=7.

Это число можно представить в виде суммы: Г=φ1+φ

2+φ3+., где φ3 – число

граней, ограниченных тремя ребрами, φ4 – число граней,

ограниченных че¬тырьмя ребрами и т. д.

С другой стороны, каждое ребро является границей двух граней, а поэтому число

граней равно 2Р, в то же время 2Р=20=3φ3+4

φ4+… . Умножив равенство Г=7=φ

3+ φ4 + φ5 + . на три,

получим ЗГ=21=3( φ3 + φ4 + φ

5 + .).

Ясно, что (3φ3+3φ4+3φ

5+.) < (3φ3+4φ4+ 5

φ5+.) или 3Г<2Р, но по

условию, 2Р=20, а ЗГ=21; поэтому вывод, полученный при введенном

нами предположе¬нии (граф плоский), противоречит условию. Отсюда заключаем, что

полный граф с пятью вершинами не является плоским. ‡

Теорема 3.11. (Теорема Понтрягина-Куратовского) Граф является плоским

тогда и только тогда, когда он не имеет в качестве подграфа полного графа с

пятью вершинами.

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

объяснялись только основные теоремы теории графов.

Источник

Граф с окрашенными рёбрами для иллюстрации пути H-A-B, замкнутого пути или обхода с повторением вершин B-D-E-F-D-C-B и цикла без повторения рёбер или вершин H-D-G-H

В теории графов два типа объектов обычно называются циклами.

Один тип циклов, чаще называющиеся замкнутым обходом, состоит из последовательности вершин, начинающейся и заканчивающейся в той же самой вершине, и каждые две последовательные вершины в последовательности смежны. Другой тип циклов, иногда называемых простыми циклами, – это замкнутые обходы без повторного прохода по ребру или посещения вершины дважды, за исключением начальной и конечной вершин. Простые циклы можно описать набором рёбер, в отличие от замкнутых обходов, в которых наборы рёбер (с возможным повторением) не определяют однозначно порядок вершин. Ориентированный цикл в орграфе – это последовательность вершин, начинающаяся и завершающаяся в той же самой вершине, и в этой последовательности для любых двух последовательных вершин существует дуга из более ранней в более позднюю. Такое же различие между простыми циклами и обходами, как выше, можно определить и для ориентированных графов[1].

Циклы без хорд[править | править код]

Цикл без хорд в графе, также называемый дырой или порождённым циклом, – это цикл, в котором никакие две вершины цикла не соединены ребром, разве что это ребро само принадлежит циклу. Антидыра – это дополнение дыры. Графы без хорд можно использовать для описания совершенных графов – согласно строгой теореме о совершенных графах граф является совершенным в том и только в том случае, когда он не содержит дыр и антидыр с нечётным числом вершин больше трёх. Хордальный граф – это специальный тип совершенных графов, в котором нет дыр размером больше трёх.

Обхват графа – это длина наименьшего цикла. Этот цикл обязательно не будет иметь хорд. Клетки – это наименьшие регулярные графы с заданной степенью вершин и обхватом.

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

Пространство циклов[править | править код]

Понятие цикл может также относиться к элементам пространства циклов графа. Оно состоит из множеств рёбер, которые имеют чётную степень для каждой вершины. Множества образуют векторное пространство над конечным полем из двух элементов. Используя методы алгебраической топологии его можно обобщить до векторных пространств или модулей над другими кольцами, такими как целые числа, вещественные числа и т. д. По теореме Веблена любой элемент пространства циклов можно получить путём комбинирования простых циклов. База циклов графа – это множество простых циклов, которые образуют базис пространства циклов[2][3].

Поиск цикла[править | править код]

Неориентированный граф имеет цикл в том и только в том случае, когда поиск в глубину (DFS) находит ребро, которое приводит к уже посещённой вершине (обратная дуга)[4]. Таким же образом, все обратные рёбра, которые алгоритм DFS обнаруживает, являются частями циклов[5]. Для неориентированных графов требуется только время O(n) для нахождения цикла в графе с n вершинами, поскольку максимум n − 1 рёбер могут быть рёбрами дерева.

Ориентированный граф имеет цикл в том и только в том случае, когда DFS находит обратную дугу. Дуги вперёд и поперечные дуги не обязательно говорят о цикле. Многие алгоритмы топологических сортировок также обнаруживают циклы, поскольку они мешают существованию топологического порядка. Если ориентированный граф разделён на компоненты сильной связности, циклы существуют только в компонентах, но не между ними, поскольку циклы сильно связаны[5].

Приложения алгоритмов нахождения циклов включают графы ожидания для нахождения взаимных блокировок в системах с параллельными потоками[6].

Покрытие графов циклами[править | править код]

В работе 1736 года о проблеме семи мостов Кёнигсберга, общепринято считающейся днём рождения теории графов, Леонард Эйлер доказал, что для того, чтобы конечный неориентированный граф имел замкнутый обход всех рёбер ровно по одному разу, необходимо и достаточно, чтобы он был связан и имел чётную степень всех вершин. Соответствующее описание существования замкнутого обхода каждого ребра ровно один раз в ориентированном графе состоит в требовании, чтобы граф был сильно связан и каждая вершина имела одинаковое число входящих и исходящих дуг. В обоих случаях полученный путь известен как эйлеров цикл. Если конечный неориентированный граф имеет чётную степень каждой вершины, независимо от того, связан он или нет, можно найти множество простых циклов, которые покрывают каждое ребро ровно раз – это теорема Веблена[7]. Если связный граф не удовлетворяет условиям теоремы Эйлера, замкнутый обход минимальной длины, покрывающий все рёбра по меньшей мере один раз может быть найден, тем не менее, за полиномиальное время путём решения задачи об инспекции дорог (англ.)русск..

Задача поиска простого цикла, проходящего через каждую вершину ровно один раз, в отличие от покрытия рёбер, намного сложнее. Такие циклы известны как гамильтоновы циклы, и задача определения существуют ли такие циклы NP-полна[8]. Опубликовано множество исследований относительно классов графов, заведомо содержащих гамильтоновы циклы. Примером может служить теорема Оре о том, что гамильтонов цикл может быть найден в графе всегда, если при сложении степеней любой пары несмежных вершин получим по меньшей мере общее число вершин графа[9].

Гипотеза о двойном покрытии циклами утверждает, что для любого графа без мостов существует мультимножество простых циклов, покрывающих каждое ребро графа в точности два раза. Доказательство гипотезы, либо контрпример пока не найдены[10].

Классы графов, определяемые циклами[править | править код]

Некоторые важные классы графов можно определить или описать их циклами. Это:

Двудольный граф – граф без нечётных циклов.
Кактус – граф, в котором любая нетривиальная двусвязная компонента является циклом.
Граф-цикл – граф, состоящий из единственного цикла.
Хордальный граф – граф, в котором нет порождённых циклов длиной больше трёх.
Ориентированный ациклический граф – ориентированный граф без циклов.
Совершенный граф – граф без порождённых циклов нечётной длины более трёх, либо их дополнений.
Псевдолес – граф, в котором каждая связная компонента имеет максимум один цикл.
Сильно связный граф – ориентированный граф, в котором любая дуга входит в какой-либо цикл.
Граф без треугольников – граф, в котором нет циклов длины три.

Примечания[править | править код]

↑ V. K. Balakrishnan. Schaum’s outline of theory and problems of graph theory. – McGraw-Hill, 2005. – ISBN 978-0070054899.
↑ Jonathan L. Gross, Jay Yellen. 4.6 Graphs and Vector Spaces // Graph Theory and Its Applications. – 2nd. – CRC Press, 2005. – С. 197-207. – ISBN 9781584885054.
↑ Reinhard Diestel. 1.9 Some linear algebra // Graph Theory. – Springer, 2012. – Т. 173. – С. 23-28. – (Graduate Texts in Mathematics).. Перевод: Рейнгард Дистель. 1.9 Немного линейной алгебры // Теория графов. – Новосибирск: Издательство Института математики, 2002. – С. 35-40. – ISBN 5-86134-101-X..
↑ Alan Tucker. Chapter 2: Covering Circuits and Graph Colorings // Applied Combinatorics. – 5th. – Hoboken: John Wiley & sons, 2006. – С. 49. – ISBN 978-0-471-73507-6.
↑ 1 2 Robert Sedgewick. Graph algorithms. – Addison-Wesley, 1983. – ISBN 0-201-06672-6.
↑ Abraham Silberschatz, Peter Galvin, Greg Gagne. Operating System Concepts. – John Wiley & Sons, INC., 2003. – С. 260. – ISBN 0-471-25060-0.
↑ Oswald Veblen. An Application of Modular Equations in Analysis Situs // Annals of Mathematics. – 1912. – Т. 14, вып. 1. – С. 86-94.
↑ Richard M. Karp. Complexity of Computer Computations / R. E. Miller and J. W. Thatcher. – New York: Plenum, 1972. – С. 85-103.
↑ Ø. Ore. Note on Hamilton circuits // American Mathematical Monthly. – 1960. – Т. 67, вып. 1. – С. 55.
↑ F. Jaeger. Annals of Discrete Mathematics 27 – Cycles in Graphs. – 1985. – Т. 27. – С. 1-12. – (North-Holland Mathematics Studies). – doi:10.1016/S0304-0208(08)72993-1.

Источник

Читайте также: Bash for вложенные циклы