Страница 6, часть 1 - гдз по алгебре 7-9 класс учебник часть 1, 2 Высоцкий, Ященко

2 Может ли в дереве быть 4 ребра; бесконечно много рёбер?

4 ребра

Да, может. Дерево в теории графов — это связный ациклический граф. Для любого конечного дерева существует строгое соотношение между количеством вершин $V$ и количеством рёбер $E$:

$V = E + 1$

Если в дереве 4 ребра ($E = 4$), то оно должно иметь $V = 4 + 1 = 5$ вершин. Построить такое дерево очень просто. Например, это может быть граф-путь (цепочка из 5 вершин) или граф-звезда (одна центральная вершина, соединённая с четырьмя другими). Оба этих графа являются связными и не содержат циклов.

Ответ: да, может.

бесконечно много рёбер

Да, может. Стандартное определение дерева как связного ациклического графа не накладывает обязательного условия конечности числа вершин или рёбер. Можно построить граф с бесконечным числом вершин и рёбер, который будет удовлетворять определению дерева.

Примером такого дерева может служить бесконечный регулярный граф, где из каждой вершины выходит одинаковое количество рёбер (например, бесконечное двоичное дерево). Можно представить себе "корень", из которого выходят два ребра. Из концов этих рёбер (новых вершин) также выходят по два ребра, и этот процесс продолжается до бесконечности. Полученная структура будет связной (из любой вершины можно добраться до любой другой) и ациклической, но будет содержать бесконечное множество рёбер и вершин. Другой простой пример — бесконечная цепь (граф-путь), вершины которого можно занумеровать всеми целыми числами.

Ответ: да, может.

3 Бывают ли в дереве петли; цепи; циклы?

Для ответа на этот вопрос необходимо обратиться к определению дерева в теории графов. Дерево — это связный неориентированный граф, не содержащий циклов (ациклический граф). Исходя из этого фундаментального определения, рассмотрим каждый пункт.

петли
Петля — это ребро, которое соединяет вершину саму с собой, например, ребро $(v, v)$ для вершины $v$. Такая структура является частным случаем цикла, а именно циклом длины 1. Поскольку по определению дерево является ациклическим графом (т.е. графом без циклов), оно не может содержать никаких циклов, включая петли.
Ответ: нет, в дереве не бывает петель.

цепи
Цепь (или путь) — это последовательность вершин, в которой каждая соседняя пара вершин соединена ребром. Например, $(v_1, v_2, \dots, v_k)$ является цепью, если для всех $i$ от 1 до $k-1$ существует ребро $(v_i, v_{i+1})$. По определению, дерево — это связный граф. Связность графа как раз и означает, что между любыми двумя его вершинами $u$ и $v$ существует по крайней мере одна цепь. Более того, в дереве между любыми двумя вершинами существует ровно одна простая цепь (цепь без повторяющихся вершин). Таким образом, цепи являются неотъемлемой частью структуры дерева.
Ответ: да, в дереве существуют цепи.

циклы
Цикл — это замкнутый путь, то есть цепь, у которой начальная и конечная вершины совпадают, например, $(v_1, v_2, \dots, v_k, v_1)$, где $k \ge 3$ для простого цикла в простом графе. Основное свойство дерева, заложенное в его определении, — это ацикличность. Это означает, что в дереве по определению не может быть циклов. Наличие хотя бы одного цикла в связном графе означало бы, что между некоторыми парами вершин на этом цикле существует как минимум два различных пути, что противоречит другому определению дерева (граф, в котором между любыми двумя вершинами существует ровно один путь).
Ответ: нет, в дереве не бывает циклов.

4 В графе рёбрами соединены вершины $A$ и $B$, $B$ и $C$, $A$ и $C$. Является ли этот граф деревом?

Усадьба

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

Рассмотрим заданный граф.
1. Вершины: А, В, С (всего 3 вершины).
2. Рёбра: (А, В), (В, С), (А, С) (всего 3 ребра).

Проверим граф на соответствие двум основным свойствам дерева:

1. Связность. Граф является связным, так как от любой вершины можно добраться до любой другой по рёбрам (например, все вершины попарно соединены).

2. Отсутствие циклов. Цикл — это путь, который начинается и заканчивается в одной и той же вершине. В данном графе можно построить такой путь: A → B → C → A. Это означает, что в графе есть цикл.

Так как граф содержит цикл, он не является деревом.

Также можно применить другое свойство дерева: для любого дерева количество рёбер ($E$) всегда на единицу меньше количества вершин ($V$). Формула для дерева: $E = V - 1$.
В нашем графе:
Количество вершин $V = 3$.
Количество рёбер $E = 3$.
Проверяем равенство: $3 = 3 - 1$, что упрощается до $3 = 2$. Это равенство неверно. Следовательно, граф не является деревом.

Ответ: Нет, этот граф не является деревом, так как он содержит цикл.

5 План тропинок в парке представляет собой дерево (рис. 6). Ворота в парке обозначены вершиной $S$. Сколько цепей ведёт из вершины $S$:

а) к кафе;

б) к пруду;

в) к саду камней?

Усадьба

Детская площадка

Кафе

Пруд

Фонтан

Памятник

$S$

Сад камней

Рисунок 6

Данная схема представляет собой граф-дерево, где S — это корень (ворота в парк), а остальные объекты — вершины. "Цепь" в данном контексте — это уникальный путь от начальной вершины S до конечной вершины (листа дерева). Поскольку в дереве между любыми двумя вершинами существует только один простой путь, задача сводится к подсчету количества конечных вершин (тропинок), соответствующих каждому объекту.

а) к кафе;

Чтобы добраться до кафе, нужно от ворот S пойти по средней из трёх основных тропинок до промежуточной развилки. От этой развилки отходят три тропинки к группе объектов. Судя по расположению подписей, надпись «Кафе» соответствует одной, самой верхней, конечной точке в этой группе. Таким образом, к кафе ведёт ровно один маршрут (цепь).

Ответ: 1.

б) к пруду;

Маршрут к пруду начинается так же, как и к кафе: от ворот S по средней тропинке до той же развилки. Надпись «Пруд» на схеме соответствует средней из трёх конечных точек в этой группе. Следовательно, к пруду также ведёт один-единственный маршрут (цепь).

Ответ: 1.

в) к саду камней?

Чтобы попасть в сад камней, от ворот S необходимо выбрать нижнюю тропинку. Она приводит к развилке, от которой один из путей ведёт напрямую к конечной точке с надписью «Сад камней». Это единственный путь к данному объекту. Значит, к саду камней ведёт одна цепь.

Ответ: 1.

6 Придумайте какой-нибудь случайный опыт, моделью которого служит дерево, показанное на рисунке 7.

Рисунок 7

Данное дерево вариантов иллюстрирует двухэтапный случайный опыт. На первом этапе есть 2 возможных исхода. После наступления любого из исходов первого этапа, на втором этапе возможно 6 исходов. Таким образом, общее число элементарных исходов в данном опыте равно произведению числа исходов на каждом этапе: $2 \times 6 = 12$.

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

Пример 1: Бросок монеты и игрального кубика

Сначала подбрасывается симметричная монета. Это первый этап опыта, у которого есть два возможных исхода: «орёл» или «решка». Затем, независимо от результата броска монеты, бросается стандартный шестигранный игральный кубик (кость). Это второй этап опыта с шестью возможными исходами: выпадение 1, 2, 3, 4, 5 или 6 очков. Первая развилка на дереве (2 ветви) соответствует результату броска монеты, а последующие развилки (по 6 ветвей от каждой) — результату броска кубика.

Пример 2: Выбор урны и шара

Имеются две урны. В каждой урне находится по 6 шаров, занумерованных от 1 до 6. Случайный опыт состоит в том, что сначала наугад выбирается одна из двух урн (первый этап, 2 исхода), а затем из выбранной урны наугад вынимается один шар (второй этап, 6 исходов). Дерево показывает все возможные комбинации выбора урны и номера шара.

Пример 3: Выбор блюда и напитка в столовой

В столовой на обед предлагают два варианта первого блюда: борщ или суп-лапша. К любому первому блюду можно выбрать один из шести напитков: чай, кофе, компот, сок, вода или кисель. Опыт заключается в выборе одного первого блюда и одного напитка. Первый этап — выбор первого блюда (2 исхода), второй этап — выбор напитка (6 исходов).

Ответ: Примером случайного опыта может служить эксперимент, состоящий из двух этапов: сначала подбрасывается монета (2 исхода: орёл или решка), а затем бросается игральный кубик (6 исходов: от 1 до 6 очков).

7 Приведите пример случайного опыта, для изображения которого требуется дерево с бесконечным числом вершин.

Рассмотрим следующий случайный опыт: монету подбрасывают до тех пор, пока не выпадет «орёл». Результат «орёл» будем обозначать буквой О, а результат «решка» — буквой Р.

Этот опыт может, теоретически, продолжаться бесконечно, если орёл никогда не выпадет. Построим дерево для визуализации этого процесса:

1. Начало. Корневая вершина дерева представляет собой начальное состояние перед первым броском.
2. Первый бросок. Из корня выходят две ветви. Одна ветвь соответствует выпадению орла (О). Эта ветвь заканчивается в конечной вершине (листе), так как опыт на этом завершается. Вторая ветвь соответствует выпадению решки (Р) и ведет к новой промежуточной вершине, так как опыт продолжается.
3. Второй бросок. Если на первом шаге выпала решка (Р), мы переходим к следующей вершине. Из неё снова выходят две ветви: ветвь О (опыт завершается, итоговый исход — РО) и ветвь Р (опыт продолжается, промежуточный исход — РР).
4. Последующие броски. Процесс повторяется. После каждой последовательности из $k$ решек мы достигаем вершины, из которой выходят две ветви: О (завершение) и Р (продолжение).

Таким образом, в дереве исходов существует бесконечный путь, который соответствует бесконечной последовательности выпадения решек: корень → Р → РР → РРР → ... . Каждая вершина на этом пути, включая корень, является точкой, из которой также исходит ветвь «О», ведущая в лист (конечную вершину).

Множество всех элементарных исходов этого опыта бесконечно: {О, РО, РРО, РРРО, ...}. Каждому исходу соответствует свой лист в дереве. Кроме того, существует бесконечное число промежуточных вершин, соответствующих последовательностям из одних решек. Следовательно, общее число вершин в дереве, представляющем этот опыт, является бесконечным.

Ответ: Примером случайного опыта, для изображения которого требуется дерево с бесконечным числом вершин, является подбрасывание монеты до тех пор, пока не выпадет «орёл». В дереве, представляющем этот опыт, есть бесконечная последовательность вершин, соответствующая непрерывному выпадению «решки», что делает общее число вершин бесконечным.

8 Придумайте и нарисуйте в тетради:

a) два неодинаковых дерева с четырьмя вершинами;

б) три неодинаковых дерева с пятью вершинами.

а) два неодинаковых дерева с четырьмя вершинами;

Дерево в теории графов — это связный граф (из любой вершины можно попасть в любую другую), не содержащий циклов. Важное свойство дерева: если в нем $n$ вершин, то количество рёбер всегда равно $n-1$.

Для дерева с четырьмя вершинами ($n=4$) нам потребуется $n-1 = 4-1=3$ ребра. Существует ровно два структурно различных (неизоморфных) дерева с четырьмя вершинами. Их можно построить, по-разному соединив вершины.

1. Дерево-путь ($P_4$). Вершины соединены последовательно в одну линию. Если пронумеровать вершины {1, 2, 3, 4}, то рёбра будут соединять пары (1,2), (2,3) и (3,4). В этом дереве две крайние вершины имеют степень 1 (из них выходит одно ребро), а две внутренние — степень 2.

2. Дерево-звезда ($K_{1,3}$). Одна вершина является центральной и соединена со всеми остальными. Если вершина 1 — центральная, то рёбра будут (1,2), (1,3) и (1,4). В этом дереве центральная вершина имеет степень 3, а остальные три вершины — степень 1.

Эти два дерева неодинаковы, так как у них разный набор степеней вершин (у первого {1, 2, 2, 1}, а у второго {3, 1, 1, 1}), что является фундаментальным структурным отличием.

Ответ: Первое дерево — это "цепь" из четырех вершин, соединенных последовательно (1-2-3-4). Второе дерево — это "звезда", где одна центральная вершина соединена с тремя остальными.

б) три неодинаковых дерева с пятью вершинами.

Для дерева с пятью вершинами ($n=5$) количество рёбер должно быть $n-1 = 5-1=4$. Существует три неизоморфных дерева с пятью вершинами. Их можно различить по максимальной степени вершин или по длине самого длинного пути внутри дерева.

1. Дерево-путь ($P_5$). Все пять вершин соединены в одну длинную цепь. Если пронумеровать вершины {1, 2, 3, 4, 5}, рёбра будут: (1,2), (2,3), (3,4), (4,5). Максимальная степень вершины в этом дереве равна 2.

2. Дерево-звезда ($K_{1,4}$). Одна центральная вершина соединена с остальными четырьмя. Рёбра: (1,2), (1,3), (1,4), (1,5). Максимальная степень вершины равна 4.

3. Разветвлённое дерево. Это дерево можно получить, взяв путь из четырёх вершин (например, 1-2-3-4) и присоединив пятую вершину к одной из внутренних вершин пути (например, к вершине 2). Рёбра такого дерева: (1,2), (2,3), (3,4) и (2,5). Максимальная степень вершины в этом случае равна 3.

Все три дерева структурно различны, так как у них разные максимальные степени вершин (2, 4 и 3 соответственно), что доказывает их неизоморфность.

Ответ: Три неодинаковых дерева с пятью вершинами: 1) "цепь", где все 5 вершин соединены последовательно; 2) "звезда", где одна центральная вершина соединена с остальными четырьмя; 3) разветвлённое дерево, которое можно представить как путь из 4 вершин, к одной из внутренних вершин которого присоединена пятая вершина.