Пути в графе. Эйлеровы графы

Загрузка…

Пути в графе. Эйлеровы графы: правила и примеры

Граф — это вершины и рёбра, которые их соединяют. По рёбрам можно «путешествовать»: переходить из вершины в вершину. В 7 классе эта тема входит в курс «Вероятность и статистика» (учебник Высоцкого и Ященко, глава IV, пункты о путях, связных графах и задаче о кёнигсбергских мостах). Здесь собраны правила и примеры с разбором по шагам: есть ли путь между вершинами, как найти кратчайший путь, связный ли граф, что такое цикл, когда можно обойти все рёбра по одному разу и как это связано с нечётными вершинами.

Путь между вершинами

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

ABCDEFG

Пример. На рисунке изображён граф. Есть ли в нём путь из вершины D в вершину B?

из D можно дойти до: C, D, E, G
B недостижима: пути нет
Ответ: Нет.

Разобрать по шагам →
ABCDEF

Пример. На рисунке изображён граф. Какая из цепочек вершин — путь из B в E?

в пути соседние вершины соединены ребром
путь: B–D–C–A–E
Ответ: BDCAE.

Разобрать по шагам →

Кратчайший путь

Длина пути — число рёбер в нём; вершин в цепочке на одну больше. Чтобы найти кратчайший путь, смотрите, куда можно попасть за одно ребро, потом за два и так далее, пока не дойдёте до нужной вершины. Если до B можно добраться за два ребра, нет смысла искать более длинные пути.

ABCDEFG

Пример. На рисунке изображён граф. Найдите длину кратчайшего пути из вершины F в вершину G (число рёбер).

кратчайший путь: F–C–G
рёбер: 2
Ответ: 2.

Разобрать по шагам →

Связный граф и компоненты

Граф называют связным, если любые две его вершины соединены путём. Несвязный граф распадается на отдельные части, между которыми дорог нет, — компоненты связности. Изолированная вершина — тоже отдельная компонента. Чтобы проверить связность, выберите любую вершину и выпишите все вершины, до которых можно дойти от неё: если это все вершины графа, граф связный.

ABCDE

Пример. На рисунке изображён граф. Связный ли это граф?

из A можно дойти до: A, C
3 вершин недостижимы
граф несвязный
Ответ: Нет.

Разобрать по шагам →
ABCDE

Пример. На рисунке изображён граф. Из скольких связных частей (компонент) он состоит?

части: AC, BD, E
частей: 3
Ответ: 3.

Разобрать по шагам →

Цикл

Цикл — это замкнутый путь: он начинается и заканчивается в одной вершине, а рёбра и промежуточные вершины в нём не повторяются. Цикл ABCA — это путь A–B–C–A, возвращающийся в A. Цепочка, которая не возвращается в начало, циклом не считается. Если у графа есть вершина степени 1, цикл через неё пройти нельзя: вернуться оттуда можно только по тому же ребру.

ABCDE

Пример. На рисунке изображён граф. Есть ли в нём цикл?

через вершину степени 1 цикла нет
убираем висячие вершины — рёбра кончаются
цикла нет
Ответ: Нет.

Разобрать по шагам →
ABCDE

Пример. На рисунке изображён граф. Какая из цепочек вершин — цикл?

цикл — замкнутый путь: начало и конец совпадают
цикл: B–A–C–B
Ответ: BACB.

Разобрать по шагам →

Эйлеров путь: обход всех рёбер по одному разу

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

ABCDE

Пример. На рисунке изображён граф. Можно ли пройти по всем рёбрам ровно по одному разу?

степени: A — 3, B — 2, C — 3, D — 3, E — 3
нечётных вершин: 4 (A, C, D, E)
нечётных вершин больше двух — обхода нет
Ответ: Нет.

Разобрать по шагам →
ABCDE

Пример. На рисунке изображён граф. Нужно пройти по всем рёбрам ровно по одному разу. С какой из этих вершин можно начать обход?

степени: A — 3, B — 4, C — 4, D — 3, E — 2
нечётных вершин: 2 (A, D)
начинать нужно с нечётной вершины
начать можно с A
Ответ: A.

Разобрать по шагам →
ABCDE

Пример. На рисунке изображён граф. Можно ли пройти по всем рёбрам ровно по одному разу и вернуться в ту вершину, с которой начали?

степени: A — 3, B — 3, C — 4, D — 3, E — 3
нечётных вершин: 4 (A, B, D, E)
есть нечётные вершины — вернуться нельзя
Ответ: Нет.

Разобрать по шагам →

Задача о кёнигсбергских мостах и рисунок одним росчерком

В городе Кёнигсберге (теперь Калининград) через реку Преголя было семь мостов, и никому не удавалось пройти по всем мостам ровно по одному разу. Леонард Эйлер доказал, что это невозможно: если участки суши изобразить вершинами, а мосты — рёбрами, получится граф с четырьмя нечётными вершинами (степени 3, 3, 3 и 5). Таким же способом решают задачи «можно ли нарисовать фигуру одним росчерком, не отрывая карандаша и не проводя дважды по одной линии»: точки на линиях — вершины, линии — рёбра, а ответ зависит от числа нечётных вершин.

ABCD

Пример. На рисунке изображён план: буквами обозначены участки суши, линиями — мосты между ними. Можно ли пройти по всем мостам ровно по одному разу?

суша — вершины, мосты — рёбра
степени: A — 3, B — 5, C — 3, D — 3
нечётных вершин: 4
нечётных вершин больше двух — нельзя
Ответ: Нет.

Разобрать по шагам →
ABCDE

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

точки — вершины, линии — рёбра
степени: A — 3, B — 4, C — 4, D — 3, E — 2
нечётных вершин: 2
нечётных вершин не больше двух — можно
Ответ: Да.

Разобрать по шагам →

Сколько рёбер нужно добавить

Если у связного графа нечётных вершин больше двух, обход по одному разу невозможен. Новое ребро между двумя нечётными вершинами делает их чётными: нечётных становится на две меньше. Значит, при 4 нечётных вершинах нужно добавить 1 ребро, при 6 — 2 ребра. Добавляемое ребро должно соединять вершины, которые ещё не соединены.

ABCDEFG

Пример. На рисунке изображён граф. Сколько рёбер нужно добавить (каждое — между вершинами, которые ещё не соединены), чтобы по всем рёбрам можно было пройти ровно по одному разу?

нечётные вершины: C, E, F, G (4)
нужно не больше двух нечётных вершин
(4 − 2) : 2 = 1
Ответ: 1.

Разобрать по шагам →

Частые ошибки

Тренажёр, самостоятельные и зачёт