ГДЗ: Упражнение 72 - § 3 (Граф и способы его задания) - (Вероятность и статистика 10 класс, Бунимович Евгений Абрамович, Булычев Владимир Александрович)
Глава 2. Элементы теории графовСтраницы: 47, 48, 49, 50, 51, 52, 53, 54, 55, 56
Какие из графов, изображённых на рисунке 40, содержат эйлеровы циклы? Найдите эти циклы.
Рис. 40 (вершины пронумерованы для удобства разбора).
Какие графы содержат эйлеровы циклы? Найдите их.
Ответ
По теореме Эйлера эйлеров цикл есть в связном графе тогда и только тогда, когда степени всех вершин чётные. Найдём степени.
Граф а) — полный граф на пяти вершинах: каждая вершина соединена с четырьмя другими, все степени равны 4. Эйлеров цикл существует, например: 1–2–3–4–5–1–3–5–2–4–1 (проверьте: использованы все 10 рёбер, каждое один раз).
Граф б): степени вершин 1, 2, 3, 4, 5 равны 2, 4, 4, 3, 3. Вершины 4 и 5 нечётные — эйлерова цикла нет (есть только эйлеров путь из вершины 4 в вершину 5, например 4–2–1–3–2–5–3–4–5).
Граф в): степени 2, 4, 4, 2, 2 — все чётные, эйлеров цикл существует: 1–2–4–3–5–2–3–1 (все 7 рёбер по одному разу).
Ответ: эйлеровы циклы содержат графы а) и в); например, а) 1–2–3–4–5–1–3–5–2–4–1, в) 1–2–4–3–5–2–3–1.
Что применять при решении
Граф, вершины и рёбра
Граф — представление объектов и связей между ними с помощью множества точек (вершин), некоторые пары которых соединены линиями (рёбрами). Графами описывают транспортные сети, родословные, строение молекул, электрические схемы. Граф можно задать рисунком или матрицей смежности — таблицей, в которой на пересечении строки \( x \) и столбца \( y \) стоит 1, если вершины \( x \) и \( y \) соединены ребром, и 0 в противном случае. У неориентированного графа матрица симметрична относительно диагонали.
Виды графов
Ориентированный граф — на каждом ребре указано направление (стрелка); его матрица смежности несимметрична. Взвешенный граф — каждому ребру сопоставлено число (вес: длина дороги, стоимость проезда); в матрицу записывают веса. Мультиграф допускает несколько (кратных) рёбер между одной парой вершин. Петля — ребро, соединяющее вершину с ней самой. Простой граф — неориентированный невзвешенный граф без петель и кратных рёбер; в основном рассматриваются именно такие графы.
Степень вершины
Степень вершины — количество рёбер, проведённых из этой вершины. Вершина степени 0 называется изолированной. В простом графе с \( n \) вершинами степень любой вершины не больше \( n - 1 \); в мультиграфе степень ничем не ограничена.
\( 0 \le \deg v \le n - 1 \) в простом графе
Теорема 1 о двух вершинах одинаковой степени
Если простой граф содержит больше одной вершины, то в нём найдутся хотя бы две вершины одинаковой степени. Доказательство от противного: все \( n \) степеней различны только при значениях \( 0, 1, \ldots, n - 1 \), но вершина степени \( n - 1 \) соединена со всеми, в том числе с изолированной вершиной степени 0 — противоречие.
Теорема 2 о сумме степеней и её следствие
Сумма степеней всех вершин графа (или мультиграфа) равна удвоенному числу его рёбер, потому что каждое ребро имеет два конца и добавляет по единице к степеням двух вершин. Следствие: число вершин нечётной степени в любом графе чётно (иначе сумма степеней была бы нечётной).
\( \deg v_1 + \deg v_2 + \ldots + \deg v_n = 2E \), где \( E \) — число рёбер
Путь, цепь, цикл
Путь (маршрут) — последовательность вершин, в которой каждая вершина соединена ребром со следующей; длина пути — число рёбер в нём (на 1 меньше числа вершин). В пути вершины и рёбра могут повторяться. Цепь — путь без повторяющихся рёбер. Цикл — цепь, у которой начальная и конечная вершины совпадают; если все остальные вершины цикла различны, цикл называется простым. Граф, все вершины которого соединены «по кругу», — простой цикл. Граф, состоящий из нескольких частей, называется несвязным.
Эйлеров цикл и теорема Эйлера
Эйлеров цикл — цикл, содержащий все рёбра графа (каждое ровно один раз). Теорема Эйлера: в связном графе (мультиграфе) эйлеров цикл существует тогда и только тогда, когда все вершины имеют чётные степени. Если ровно две вершины имеют нечётную степень, эйлерова цикла нет, но есть эйлеров путь — незамкнутый маршрут по каждому ребру ровно один раз, начинающийся в одной нечётной вершине и заканчивающийся в другой. Задача о семи кёнигсбергских мостах (все четыре вершины нечётные) решения не имеет.
Создать проектГотовый файл Word. Оплата после того, как увидите работу.
Уведомление об авторском праве и цитировании
ВНИМАНИЕ: Представленные фрагменты из учебных материалов
используются исключительно в научно-образовательных целях в объеме,
оправданном поставленной целью.
Данное использование осуществляется в рамках, установленных законодательством об авторском праве
(в частности, нормами о свободном использовании произведения для образовательных целей).
В соответствии с законодательством, автор и источник заимствования
указаны для каждого используемого фрагмента.
