ГДЗ: Упражнение 67 - § 3 (Граф и способы его задания) - (Вероятность и статистика 10 класс, Бунимович Евгений Абрамович, Булычев Владимир Александрович)
Глава 2. Элементы теории графовСтраницы: 47, 48, 49, 50, 51, 52, 53, 54, 55, 56
Определите, существует ли описанный ниже граф. Если да, то постройте его: а) граф из семи вершин, в котором все вершины имеют степень 2; б) граф из восьми вершин, в котором все вершины имеют степень 2; в) граф из восьми вершин, в котором все вершины имеют степень 1; г) граф из семи вершин, в котором все вершины имеют степень 1; д) граф из семи вершин, в котором все вершины имеют степень 3; е) граф из восьми вершин, в котором все вершины имеют степень 3.
а)
Граф из семи вершин, в котором все вершины имеют степень 2.
Ответ
Существует. Пронумеруем вершины 1, 2, …, 7 и соединим их «по кругу»: 1–2, 2–3, 3–4, 4–5, 5–6, 6–7, 7–1. Из каждой вершины выходят ровно два ребра. Это простой цикл из семи вершин (рис. 36 учебника).
Ответ: да, например цикл 1–2–3–4–5–6–7–1.
б)
Граф из восьми вершин, в котором все вершины имеют степень 2.
Ответ
Существует: цикл из восьми вершин 1–2–3–4–5–6–7–8–1. Подойдёт и несвязный граф из двух циклов по четыре вершины: 1–2–3–4–1 и 5–6–7–8–5.
Ответ: да, например цикл 1–2–…–8–1.
в)
Граф из восьми вершин, в котором все вершины имеют степень 1.
Ответ
Существует. Разобьём восемь вершин на четыре пары и соединим вершины каждой пары ребром: 1–2, 3–4, 5–6, 7–8. Из каждой вершины выходит ровно одно ребро (граф несвязный — четыре отдельных «отрезка»).
Ответ: да: рёбра 1–2, 3–4, 5–6, 7–8.
г)
Граф из семи вершин, в котором все вершины имеют степень 1.
Ответ
Не существует. Сумма степеней была бы равна \( 7 \cdot 1 = 7 \) — нечётное число, а по теореме 2 сумма степеней вершин равна удвоенному числу рёбер и всегда чётна. Иначе: вершин нечётной степени было бы 7, а их число всегда чётно.
Ответ: нет.
д)
Граф из семи вершин, в котором все вершины имеют степень 3.
Ответ
Не существует: сумма степеней \( 7 \cdot 3 = 21 \) нечётна, что противоречит теореме 2 (семь вершин нечётной степени — нечётное количество).
Ответ: нет.
е)
Граф из восьми вершин, в котором все вершины имеют степень 3.
Ответ
Существует: сумма степеней \( 8 \cdot 3 = 24 \), рёбер 12. Пример — граф куба: вершины 1, 2, 3, 4 (нижнее основание) и 5, 6, 7, 8 (верхнее), рёбра 1–2, 2–3, 3–4, 4–1, 5–6, 6–7, 7–8, 8–5 и боковые 1–5, 2–6, 3–7, 4–8. Другой пример — два отдельных полных графа по четыре вершины (в каждом все вершины попарно соединены).
Ответ: да, например граф куба.
Что применять при решении
Граф, вершины и рёбра
Граф — представление объектов и связей между ними с помощью множества точек (вершин), некоторые пары которых соединены линиями (рёбрами). Графами описывают транспортные сети, родословные, строение молекул, электрические схемы. Граф можно задать рисунком или матрицей смежности — таблицей, в которой на пересечении строки \( 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. Оплата после того, как увидите работу.
Уведомление об авторском праве и цитировании
ВНИМАНИЕ: Представленные фрагменты из учебных материалов
используются исключительно в научно-образовательных целях в объеме,
оправданном поставленной целью.
Данное использование осуществляется в рамках, установленных законодательством об авторском праве
(в частности, нормами о свободном использовании произведения для образовательных целей).
В соответствии с законодательством, автор и источник заимствования
указаны для каждого используемого фрагмента.
