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

Рисунок 32

135 Укажите, какие графы на рисунке 32 содержат цикл.

135

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

Проанализируем каждый граф:

• Граф 1: Не содержит цикла. Пересечение двух рёбер не является вершиной, поэтому замкнутого пути нет.
• Граф 2: Не содержит цикла. Это граф-путь (ломаная линия).
• Граф 3: Содержит циклы. Есть внутренний цикл (треугольник) и внешний цикл (пятиугольник).
• Граф 4: Содержит циклы. Этот граф состоит из двух несвязных четырёхугольников, каждый из которых является циклом.
• Граф 5: Не содержит цикла. Это граф-путь.
• Граф 6: Содержит циклы. Есть большой цикл (четырёхугольник по периметру) и два малых цикла (два треугольника, образованные диагональю).
• Граф 7: Содержит циклы. Два четырёхугольника, соединённые в одной вершине, образуют два цикла.
• Граф 8: Не содержит цикла. Это одно ребро, соединяющее две вершины.
• Граф 9: Содержит циклы. Есть внутренний цикл (четырёхугольник) и внешний, более сложный цикл.

Таким образом, циклы присутствуют в графах под номерами 3, 4, 6, 7 и 9.

Ответ: 3, 4, 6, 7, 9.

136 Изобразите какой-нибудь граф, у которого:

a) три цикла длин 3, 4 и 5;

б) два цикла длины 4 и один цикл длины 6.

а) три цикла длин 3, 4 и 5;

Для построения такого графа можно взять за основу цикл длины 5 и добавить одно ребро (хорду). Пусть граф $G$ имеет 5 вершин $V = \{V_1, V_2, V_3, V_4, V_5\}$.

Соединим вершины так, чтобы они образовывали цикл длины 5 (пятиугольник): ребра $(V_1, V_2), (V_2, V_3), (V_3, V_4), (V_4, V_5), (V_5, V_1)$. Этот цикл и будет нашим циклом длины 5.

Теперь добавим ребро $(V_1, V_3)$. Это ребро создает два новых цикла:

• Цикл $V_1-V_2-V_3-V_1$ имеет длину 3.
• Цикл $V_1-V_3-V_4-V_5-V_1$ имеет длину 4.

Исходный цикл длины 5 ($V_1-V_2-V_3-V_4-V_5-V_1$) также сохраняется, так как все его ребра присутствуют в графе.

Таким образом, полученный граф имеет 5 вершин, 6 ребер и содержит циклы длин 3, 4 и 5.

Циклы в данном графе:

• Длины 3: $V_1-V_2-V_3-V_1$
• Длины 4: $V_1-V_3-V_4-V_5-V_1$
• Длины 5: $V_1-V_2-V_3-V_4-V_5-V_1$

Ответ: Примером такого графа является пятиугольник с одной диагональю, соединяющей вершины через одну, как показано на рисунке выше.

б) два цикла длины 4 и один цикл длины 6.

Для построения такого графа возьмем за основу цикл длины 6. Пусть граф $G$ имеет 6 вершин $V = \{V_1, V_2, V_3, V_4, V_5, V_6\}$.

Соединим вершины так, чтобы они образовывали цикл длины 6 (шестиугольник): ребра $(V_1, V_2), (V_2, V_3), (V_3, V_4), (V_4, V_5), (V_5, V_6), (V_6, V_1)$. Этот цикл будет искомым циклом длины 6.

Теперь добавим ребро, соединяющее две противоположные вершины, например, $(V_1, V_4)$. Это ребро разделит шестиугольник на два четырехугольника.

• Первый четырехугольник образует цикл $V_1-V_2-V_3-V_4-V_1$. Его длина равна 4.
• Второй четырехугольник образует цикл $V_1-V_4-V_5-V_6-V_1$. Его длина также равна 4.

Исходный цикл длины 6 ($V_1-V_2-V_3-V_4-V_5-V_6-V_1$) также существует в графе.

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

Циклы в данном графе:

• Длины 4 (первый): $V_1-V_2-V_3-V_4-V_1$
• Длины 4 (второй): $V_1-V_4-V_5-V_6-V_1$
• Длины 6: $V_1-V_2-V_3-V_4-V_5-V_6-V_1$

Ответ: Примером такого графа является шестиугольник с одной главной диагональю, соединяющей противолежащие вершины, как показано на рисунке выше.

137 Изобразите два графа с шестью вершинами степени $2$: один связный, а другой — нет.

один связный

Связный граф, у которого все шесть вершин имеют степень 2, представляет собой простой цикл, проходящий через все эти вершины. Такой граф называется циклическим графом $C_6$.

Обозначим вершины графа как $v_1, v_2, v_3, v_4, v_5, v_6$. Рёбра будут соединять их последовательно, образуя замкнутую цепь: $(v_1, v_2), (v_2, v_3), (v_3, v_4), (v_4, v_5), (v_5, v_6), (v_6, v_1)$.

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

Визуально такой граф можно представить в виде шестиугольника, где углы — это вершины, а стороны — рёбра.

Ответ: Связный граф с шестью вершинами степени 2 — это циклический граф $C_6$ (шестиугольник).

а другой — нет

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

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

Таким образом, несвязный граф будет состоять из двух непересекающихся циклов $C_3$. Например, первая компонента — это вершины $v_1, v_2, v_3$ с рёбрами $(v_1, v_2), (v_2, v_3), (v_3, v_1)$, а вторая компонента — это вершины $v_4, v_5, v_6$ с рёбрами $(v_4, v_5), (v_5, v_6), (v_6, v_4)$.

В этом графе степень каждой из шести вершин равна 2, но сам граф является несвязным, так как отсутствуют рёбра между первой и второй компонентами (например, нет пути из $v_1$ в $v_4$).

Визуально такой граф можно представить в виде двух отдельных треугольников.

Ответ: Несвязный граф с шестью вершинами степени 2 — это объединение двух непересекающихся циклов $C_3$ (два треугольника).

138 В деревне 9 домов. Соседними будем считать участки, у которых есть общий забор. Известно, что у Петра соседи Иван и Антон, Максим сосед Ивану и Сергею, Виктор — Дмитрию и Никите, а также по соседству живут Евгений с Никитой, Иван с Сергеем, Евгений с Дмитрием и Сергей с Антоном и больше соседей в деревне нет. Может ли Пётр, перелезая через заборы соседних участков, пробраться на участок к Никите?

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

Для начала систематизируем все соседские связи, описанные в условии. В деревне 9 жителей: Пётр, Иван, Антон, Максим, Сергей, Виктор, Дмитрий, Никита, Евгений.

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

Начнем с Петра. Его соседи — Иван и Антон. Значит, к ним можно попасть.
Далее смотрим на соседей Ивана: это Пётр (уже рассмотрен), Максим и Сергей. К ним тоже есть путь.
Теперь соседи Антона: это Пётр (рассмотрен) и Сергей (уже в группе).
Соседи Максима: Иван и Сергей (оба уже в группе).
Соседи Сергея: Максим, Иван и Антон (все уже в группе).
Таким образом, первая группа связанных участков включает: Петра, Ивана, Антона, Максима и Сергея. Ни у кого из них нет соседей за пределами этой группы.

Теперь рассмотрим оставшихся жителей: Никиту, Виктора, Дмитрия и Евгения.
Соседи Никиты — это Виктор и Евгений.
Соседи Виктора — это Дмитрий и Никита.
Соседи Дмитрия — это Виктор и Евгений.
Соседи Евгения — это Дмитрий и Никита.
Эта четверка образует вторую, отдельную группу связанных участков. Ни один из них не является соседом для кого-либо из первой группы.

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

Ответ: Нет, Пётр не может пробраться на участок к Никите, так как их участки находятся в разных, не связанных между собой группах домов.

139 В Солнечной системе введено космическое сообщение. Корабли осуществляют рейсы в обе стороны по следующим маршрутам:

Земля – Меркурий, Марс – Венера, Уран – Нептун, Марс – Меркурий, Юпитер – Плутон, Меркурий – Венера, Нептун – Сатурн, Сатурн – Юпитер, Плутон – Уран.

Можно ли добраться с Земли до Плутона?

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

Сначала выделим все прямые сообщения между планетами из условия:

1. Земля — Меркурий
2. Марс — Венера
3. Уран — Нептун
4. Марс — Меркурий
5. Юпитер — Плутон
6. Меркурий — Венера
7. Нептун — Сатурн
8. Сатурн — Юпитер
9. Плутон — Уран

Теперь определим группы связанных между собой планет. Начнем с Земли:

С Земли можно попасть на Меркурий. С Меркурия есть рейсы до Марса и Венеры. Между Марсом и Венерой также есть прямое сообщение, и они обе связаны с Меркурием. Таким образом, планеты Земля, Меркурий, Марс и Венера образуют одну связанную группу. Из этой группы нет маршрутов к другим планетам.

Рассмотрим оставшиеся планеты, начав с Плутона:

С Плутона можно добраться до Юпитера и Урана. С Юпитера можно попасть на Сатурн. С Сатурна — на Нептун. А Нептун связан с Ураном. Таким образом, планеты Плутон, Юпитер, Уран, Сатурн и Нептун образуют вторую связанную группу.

В результате мы имеем две отдельные, не связанные между собой транспортные сети:

Сеть 1: {Земля, Меркурий, Марс, Венера}
Сеть 2: {Плутон, Юпитер, Уран, Сатурн, Нептун}

Поскольку Земля находится в первой сети, а Плутон — во второй, и между этими сетями нет никаких рейсов, совершить путешествие с Земли на Плутон невозможно.

Ответ: Нет, добраться с Земли до Плутона невозможно.

140 Архипелаг Числовой состоит из 9 островов, у которых вместо названий номера от 1 до 9. Между двумя островами есть паромная переправа тогда и только тогда, когда сумма номеров этих островов делится на 3. Можно ли перебраться на паромах с острова 3 на остров 4?

Указание. Постройте граф. Вершины-острова соедините рёбрами-переправами.

Решение:
Для решения этой задачи воспользуемся теорией графов, как предложено в указании. Острова будут вершинами графа, а паромные переправы — его рёбрами. Всего у нас 9 вершин, пронумерованных от 1 до 9.

Условие существования ребра (переправы) между двумя вершинами (островами) с номерами $a$ и $b$ заключается в том, что их сумма $a+b$ должна делиться на 3. Это можно записать с помощью сравнений по модулю 3: $a + b \equiv 0 \pmod{3}$.

Разобьём все острова на три группы в зависимости от остатка от деления их номера на 3:
1. Острова, номера которых делятся на 3 (остаток 0): {3, 6, 9}. Обозначим эту группу $R_0$.
2. Острова, номера которых при делении на 3 дают в остатке 1: {1, 4, 7}. Обозначим эту группу $R_1$.
3. Острова, номера которых при делении на 3 дают в остатке 2: {2, 5, 8}. Обозначим эту группу $R_2$.

Теперь проанализируем, между какими группами островов могут существовать переправы.

• Пусть остров $a$ принадлежит группе $R_0$, то есть $a \equiv 0 \pmod{3}$. Чтобы сумма $a+b$ делилась на 3, необходимо, чтобы номер острова $b$ также делился на 3, то есть $b \equiv 0 \pmod{3}$. Это означает, что острова из группы $R_0$ могут быть связаны переправами только с другими островами из группы $R_0$.
• Пусть остров $a$ принадлежит группе $R_1$, то есть $a \equiv 1 \pmod{3}$. Чтобы сумма $a+b$ делилась на 3, необходимо, чтобы номер острова $b$ при делении на 3 давал в остатке 2, так как $1 + 2 = 3 \equiv 0 \pmod{3}$. Это означает, что острова из группы $R_1$ могут быть связаны переправами только с островами из группы $R_2$.
• Аналогично, если остров $a$ принадлежит группе $R_2$ ($a \equiv 2 \pmod{3}$), то для существования переправы остров $b$ должен принадлежать группе $R_1$ ($b \equiv 1 \pmod{3}$).

Из этого анализа следует, что наш граф распадается на две несвязанные между собой части (компоненты связности):
1. Первая компонента состоит из островов группы $R_0$: {3, 6, 9}.
2. Вторая компонента состоит из островов групп $R_1$ и $R_2$: {1, 4, 7} и {2, 5, 8}.

Нас интересует, можно ли перебраться с острова 3 на остров 4.
Остров 3 принадлежит первой компоненте связности ($R_0$).
Остров 4 принадлежит второй компоненте связности ($R_1$).
Поскольку между этими двумя компонентами нет ни одной переправы, добраться с острова 3 на остров 4 невозможно.

Ответ: Нет, перебраться на паромах с острова 3 на остров 4 нельзя.