На Горох
Разбор упражнения

ГДЗ: Упражнение 73 - § 3 (Граф и способы его задания) - (Вероятность и статистика 10 класс, Бунимович Евгений Абрамович, Булычев Владимир Александрович)

Глава 2. Элементы теории графов Страницы: 47, 48, 49, 50, 51, 52, 53, 54, 55, 56
А вы знали? Проект, реферат или доклад можно создать с помощью ИИ за 5 минут — и сразу скачать готовый файл Word. Попробовать

73 упражнение:

Какие из фигур, изображённых на рисунке 41, можно нарисовать, не отрывая карандаш от бумаги и не проводя никакую линию дважды? Если возможно, покажите, как это сделать.

ABCDOа)ABCDEOб)ABCDEFв)

Рис. 41 (точки обозначены буквами для удобства разбора).

Какие фигуры можно нарисовать одним росчерком? Покажите как.
Ответ

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

а) Вершины: углы \( A, B, C, D \) и точка пересечения диагоналей \( O \). Степень каждого угла 3 (две стороны и половина диагонали), степень \( O \) — 4. Четыре нечётные вершины — нарисовать нельзя.

б) Вершины \( A, B, C, D, E, O \). Степени: \( A \) — 4 (\( AB, AD, AE, AO \)), \( B \) — 4, \( E \) — 2, \( O \) — 4, \( C \) — 3 (\( BC, CD, CO \)), \( D \) — 3. Ровно две нечётные вершины \( C \) и \( D \) — фигуру можно нарисовать, начав в одной из них и закончив в другой. Например: \( D \to A \to E \to B \to A \to O \to D \to C \to B \to O \to C \) (10 отрезков, каждый по одному разу).

в) Вершины \( A, B, C, D, E, F \). Степени: \( A \) — 4 (\( AB, AD, AE, AF \)), \( B \) — 4, \( C \) — 2, \( D \) — 2, \( E \) — 3 (\( AE, BE, EF \)), \( F \) — 3. Нечётные вершины — \( E \) и \( F \), фигуру можно нарисовать, начав в \( E \) и закончив в \( F \): \( E \to A \to B \to E \to F \to A \to D \to C \to B \to F \) (9 отрезков).

Ответ: фигуры б) и в); фигуру а) нарисовать одним росчерком нельзя.

Что применять при решении

Граф, вершины и рёбра

Граф — представление объектов и связей между ними с помощью множества точек (вершин), некоторые пары которых соединены линиями (рёбрами). Графами описывают транспортные сети, родословные, строение молекул, электрические схемы. Граф можно задать рисунком или матрицей смежности — таблицей, в которой на пересечении строки \( 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 меньше числа вершин). В пути вершины и рёбра могут повторяться. Цепь — путь без повторяющихся рёбер. Цикл — цепь, у которой начальная и конечная вершины совпадают; если все остальные вершины цикла различны, цикл называется простым. Граф, все вершины которого соединены «по кругу», — простой цикл. Граф, состоящий из нескольких частей, называется несвязным.

Эйлеров цикл и теорема Эйлера

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

Не сходится своя задача? Разберём по шагам

  • Формула, подстановка и расчёт
  • Числа считает калькулятор, а не нейросеть
  • Бесплатно и без регистрации
Решить задачу Разбор задачи бесплатный

Другие упражнения из параграфа § 3

Данные параграфа

К параграфу →
Глава
Глава 2. Элементы теории графов
Параграф
§ 3 — Граф и способы его задания
Учебник
Вероятность и статистика 10 класс — Математика. Базовый уровень
Автор
Бунимович Евгений Абрамович, Булычев Владимир Александрович
Год
2023

Задали работу по этой теме?

Реферат, доклад или проект по параграфу: план, текст, таблицы и оформление по требованиям.

Создать проект Готовый файл Word. Оплата после того, как увидите работу.