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

1 Что такое степень вершины графа?

Степень вершины графа — это одна из ключевых числовых характеристик вершины, которая показывает, сколько рёбер с ней связано. Определение различается для неориентированных и ориентированных графов.

Степень в неориентированном графе

В неориентированном графе степенью (или валентностью) вершины $v$ называют количество рёбер, инцидентных ей, то есть рёбер, для которых $v$ является одним из концов. Степень вершины $v$ обычно обозначают как $deg(v)$ или $d(v)$.
Важно отметить, что если в графе есть петли (рёбра, соединяющие вершину саму с собой), то каждая петля при подсчёте степени традиционно добавляет 2 к общей степени, а не 1. Это логично, так как у ребра два конца, и в случае петли оба они "прикреплены" к одной и той же вершине.
Пример: если к вершине $A$ подходит 3 обычных ребра и одна петля, её степень будет $deg(A) = 3 + 2 = 5$.

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

Степень в ориентированном графе (орграфе)

В ориентированных графах рёбра (называемые дугами) имеют направление. Поэтому для каждой вершины различают два вида степеней:
• Полустепень захода (in-degree), обозначаемая $deg^-(v)$ или $d^-(v)$, — это количество дуг, которые входят в вершину $v$.
• Полустепень исхода (out-degree), обозначаемая $deg^+(v)$ или $d^+(v)$, — это количество дуг, которые исходят из вершины $v$.
Полной степенью вершины $deg(v)$ в орграфе называют сумму её полустепени захода и полустепени исхода: $deg(v) = deg^-(v) + deg^+(v)$.

Ответ: В ориентированном графе у вершины есть две степени: полустепень захода (число входящих дуг) и полустепень исхода (число исходящих дуг).

Фундаментальное свойство (Лемма о рукопожатиях)

Существует важное свойство, связывающее степени вершин с общим числом рёбер в графе, известное как лемма о рукопожатиях.
Для неориентированного графа: сумма степеней всех вершин равна удвоенному числу рёбер. Формула: $\sum_{v \in V} deg(v) = 2|E|$, где $V$ — множество вершин, а $E$ — множество рёбер. Это следует из того, что каждое ребро вносит по единице в степени ровно двух вершин (или двойку в степень одной вершины в случае петли). Из этой леммы следует, что число вершин с нечётной степенью в любом графе всегда чётно.
Для ориентированного графа: сумма всех полустепеней захода равна сумме всех полустепеней исхода, и обе эти суммы равны общему числу дуг в графе. Формула: $\sum_{v \in V} deg^-(v) = \sum_{v \in V} deg^+(v) = |E|$. Это верно, поскольку каждая дуга имеет ровно одно начало и один конец.

Ответ: Сумма степеней всех вершин в неориентированном графе равна удвоенному числу рёбер. В ориентированном графе сумма полустепеней захода и сумма полустепеней исхода равны между собой и равны общему числу дуг.

2 Может ли степень вершины равняться $0$?

Да, степень вершины графа может равняться 0.

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

Если вершина не соединена ни с какой другой вершиной (включая саму себя), то есть не является концом ни одного ребра, то её степень по определению равна нулю. Такая вершина называется изолированной вершиной.

Например, рассмотрим граф $G = (V, E)$, где множество вершин $V = \{v_1, v_2, v_3\}$ и множество рёбер $E = \{(v_1, v_2)\}$. В этом графе степень вершины $v_1$ равна 1 ( $deg(v_1) = 1$ ), и степень вершины $v_2$ также равна 1 ( $deg(v_2) = 1$ ), так как они соединены одним ребром. Вершина $v_3$ не является концом никакого ребра, поэтому её степень равна 0 ( $deg(v_3) = 0$ ). Она является изолированной.

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

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

3 Сформулируйте теорему о сумме степеней вершин.

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

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

Математически это выражается следующей формулой для графа $G = (V, E)$, где $V$ — множество вершин, а $E$ — множество рёбер: $$ \sum_{v \in V} \deg(v) = 2|E| $$ Здесь $\deg(v)$ обозначает степень вершины $v$ (количество рёбер, инцидентных ей, при этом петля добавляет к степени 2), а $|E|$ — общее число рёбер в графе.

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

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

Поскольку каждое ребро вносит вклад, равный 2, в общую сумму степеней вершин, то сумма степеней всех вершин равна удвоенному числу рёбер.

Следствие из теоремы
Важным следствием этой теоремы является то, что в любом графе число вершин с нечётной степенью должно быть чётным. Это объясняется тем, что общая сумма степеней всех вершин ($2|E|$) всегда является чётным числом. Эту сумму можно разбить на две части: сумму степеней вершин с чётной степенью и сумму степеней вершин с нечётной степенью. Сумма любого количества чётных чисел всегда чётна. Чтобы общая сумма была чётной, сумма нечётных степеней также обязана быть чётной. А сумма нечётных чисел будет чётной тогда и только тогда, когда их количество (т.е. число вершин с нечётной степенью) чётно.

Ответ: Теорема о сумме степеней вершин утверждает, что сумма степеней всех вершин в любом конечном неориентированном графе равна удвоенному числу его рёбер. Математически это записывается как $\sum_{v \in V} \deg(v) = 2|E|$.

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

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

Лемма о рукопожатиях гласит, что сумма степеней всех вершин графа равна удвоенному числу его рёбер. Это можно записать в виде формулы:

$ \sum_{i=1}^{n} \text{deg}(v_i) = 2|E| $

где $ n $ — число вершин, $ \text{deg}(v_i) $ — степень $ i $-й вершины, а $ |E| $ — количество рёбер в графе.

Из этой формулы следует важное следствие: сумма степеней всех вершин любого графа всегда должна быть чётным числом, так как она равна произведению числа рёбер на 2.

Теперь проверим условие задачи. Нам дан граф с тремя вершинами, степени которых равны 1, 2 и 2. Найдём сумму степеней этих вершин:

$ S = 1 + 2 + 2 = 5 $

Полученная сумма степеней равна 5, что является нечётным числом. Это противоречит лемме о рукопожатиях. Следовательно, граф с таким набором степеней вершин не может существовать.

Ответ: Нет, такой граф не существует, так как сумма степеней его вершин ($1+2+2=5$) является нечётным числом, что противоречит лемме о рукопожатиях.

122 На рисунке 13 (с. 80) изображён граф. Найдите степень вершины:

а) А;

б) Б.

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

а) А;
Чтобы найти степень вершины А, необходимо посчитать, сколько рёбер соединено с этой вершиной на графе, изображённом на рисунке 13. Видно, что к вершине А подходят 3 ребра. Следовательно, степень вершины А равна 3. В теории графов это обозначается как $deg(А) = 3$.
Ответ: 3

б) Б.
Чтобы найти степень вершины Б, выполним аналогичные действия. Посчитаем количество рёбер, соединённых с вершиной Б на том же графе. Видно, что к вершине Б подходят 2 ребра. Следовательно, степень вершины Б равна 2. Математическая запись: $deg(Б) = 2$.
Ответ: 2

123 На рисунках 19, а и 19, б (с. 81) изображены графы. Сколько у каждого из них вершин степени $0$, степени $1$ и степени $2$?

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

рисунок 19, а

Проанализируем граф, изображённый на рисунке 19, а. Он состоит из трёх несвязанных частей (компонент связности):

• Вершины степени $0$: К этой категории относятся изолированные вершины, то есть точки, не соединённые рёбрами ни с какой другой вершиной. В данном графе есть $1$ такая вершина.

• Вершины степени $1$: Это вершины, из которых выходит ровно одно ребро. В графе есть один отдельный отрезок, который состоит из двух вершин, и степень каждой из них равна $1$. Итого $2$ вершины степени $1$.

• Вершины степени $2$: Это вершины, соединённые двумя рёбрами с другими вершинами. В графе есть пятиугольник, состоящий из $5$ вершин. Каждая вершина пятиугольника соединена с двумя соседними, следовательно, все $5$ вершин имеют степень $2$.

Ответ: у графа на рисунке 19, а есть $1$ вершина степени 0, $2$ вершины степени 1 и $5$ вершин степени 2.

рисунок 19, б

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

• Вершины степени $0$: В этом графе есть $2$ изолированные вершины. Их степень равна $0$.

• Вершины степени $1$: В графе есть один отдельный отрезок. Две вершины, образующие этот отрезок, имеют степень $1$. Всего $2$ вершины степени $1$.

• Вершины степени $2$: К этой категории относятся вершины треугольника, четырёхугольника и вершина с петлёй.
- В треугольнике $3$ вершины, и степень каждой из них равна $2$.
- В четырёхугольнике $4$ вершины, и степень каждой из них равна $2$.
- Вершина с петлёй также имеет степень $2$, так как петля даёт вклад в степень, равный $2$.
Суммарное количество вершин степени $2$ составляет: $3 + 4 + 1 = 8$.

Ответ: у графа на рисунке 19, б есть $2$ вершины степени 0, $2$ вершины степени 1 и $8$ вершин степени 2.

124 Нарисуйте какой-либо граф, в котором 5 вершин со степенями $1, 2, 2, 3, 3$.

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

Лемма о рукопожатиях гласит, что сумма степеней всех вершин в любом неориентированном графе равна удвоенному числу его рёбер. Математически это записывается так: $$ \sum_{i=1}^{n} \text{deg}(v_i) = 2|E| $$ где $n$ — число вершин, $\text{deg}(v_i)$ — степень $i$-ой вершины, а $|E|$ — число рёбер.

Из этой леммы следует важное следствие: сумма степеней всех вершин любого графа всегда является чётным числом.

Теперь проверим, выполняется ли это условие для графа, заданного в задаче. Нам дан граф с 5 вершинами, степени которых должны быть 1, 2, 2, 3, 3.

Найдём сумму этих степеней: $$ 1 + 2 + 2 + 3 + 3 = 11 $$

Полученная сумма степеней равна 11. Это нечётное число.

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

Ответ: Нарисовать граф с 5 вершинами, имеющими степени 1, 2, 2, 3, 3, невозможно. Это связано с тем, что сумма степеней вершин в любом графе должна быть чётным числом, а в данном случае она нечётна ($1+2+2+3+3=11$).

125 Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями $1, 1, 2, 2, 3, 3$.

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

Согласно лемме о рукопожатиях, сумма степеней всех вершин графа равна удвоенному числу его рёбер. В нашем случае сумма степеней составляет $1 + 1 + 2 + 2 + 3 + 3 = 12$. Это чётное число, что подтверждает возможность существования таких графов. Число рёбер в каждом графе будет равно $12 / 2 = 6$.

Таким образом, мы ищем два графа с 6 вершинами и 6 рёбрами, имеющие заданный набор степеней, но разную структуру.

Построим первый граф. Обозначим вершины $v_1, v_2, ..., v_6$. Пусть вершины $v_1, v_2$ имеют степень 3, вершины $v_3, v_4$ — степень 2, а вершины $v_5, v_6$ — степень 1. Соединим две вершины с наибольшей степенью ($v_1$ и $v_2$) между собой. Затем построим треугольник, соединив их с вершиной $v_3$. Оставшиеся рёбра распределим так, чтобы получить нужные степени. Набор рёбер: $(v_1, v_2), (v_1, v_3), (v_2, v_3), (v_1, v_5), (v_2, v_4), (v_4, v_6)$. Проверка степеней:

• $\deg(v_1) = 3$ (соседи: $v_2, v_3, v_5$)
• $\deg(v_2) = 3$ (соседи: $v_1, v_3, v_4$)
• $\deg(v_3) = 2$ (соседи: $v_1, v_2$)
• $\deg(v_4) = 2$ (соседи: $v_2, v_6$)
• $\deg(v_5) = 1$ (сосед: $v_1$)
• $\deg(v_6) = 1$ (сосед: $v_4$)

В этом графе две вершины максимальной степени 3 ($v_1$ и $v_2$) смежны. Также в графе присутствует цикл длины 3 (треугольник), образованный вершинами $v_1, v_2, v_3$.

Построим второй граф, структура которого будет отличаться. Главным отличием сделаем то, что две вершины с максимальной степенью 3 не будут соединены ребром. Пусть $v_1$ и $v_2$ — вершины степени 3. Соединим $v_1$ с вершинами $v_3, v_4, v_5$, а вершину $v_2$ — с вершинами $v_3, v_4, v_6$. Набор рёбер: $(v_1, v_3), (v_1, v_4), (v_1, v_5), (v_2, v_3), (v_2, v_4), (v_2, v_6)$. Проверка степеней:

• $\deg(v_1) = 3$ (соседи: $v_3, v_4, v_5$)
• $\deg(v_2) = 3$ (соседи: $v_3, v_4, v_6$)
• $\deg(v_3) = 2$ (соседи: $v_1, v_2$)
• $\deg(v_4) = 2$ (соседи: $v_1, v_2$)
• $\deg(v_5) = 1$ (сосед: $v_1$)
• $\deg(v_6) = 1$ (сосед: $v_2$)

В отличие от первого графа, здесь две вершины максимальной степени 3 ($v_1$ и $v_2$) не смежны. Этот граф не содержит треугольников; минимальный цикл имеет длину 4 (например, $v_1-v_3-v_2-v_4-v_1$). Отсутствие нечётных циклов означает, что этот граф является двудольным. Различия в смежности вершин с одинаковыми степенями и в структуре циклов доказывают, что графы неизоморфны.

Ниже представлены два неодинаковых графа, удовлетворяющих условию задачи. Вершины с одинаковыми степенями окрашены в один цвет: степень 3 — синий, степень 2 — зелёный, степень 1 — красный.

Граф 1 (смежные вершины степени 3, содержит треугольник)

Граф 2 (несмежные вершины степени 3, двудольный)

126 Может ли количество вершин нечётной степени в каком-нибудь графе равняться:

a) 0;

б) 1;

в) 2;

г) 3;

д) 4?

Для решения этой задачи воспользуемся леммой о рукопожатиях, которая является следствием теоремы о сумме степеней вершин графа. Теорема гласит, что в любом графе $G=(V, E)$ сумма степеней всех его вершин равна удвоенному числу рёбер:

$\sum_{v \in V} \deg(v) = 2|E|$

Из этой формулы следует, что сумма степеней всех вершин графа всегда является чётным числом, так как она равна $2|E|$.

Разобьём множество всех вершин $V$ на две группы: вершины с чётной степенью ($V_{четн}$) и вершины с нечётной степенью ($V_{нечетн}$). Тогда общую сумму степеней можно записать в виде:

$\sum_{v \in V} \deg(v) = \sum_{v \in V_{четн}} \deg(v) + \sum_{v \in V_{нечетн}} \deg(v)$

Рассмотрим слагаемые в правой части:

1. $\sum_{v \in V_{четн}} \deg(v)$ — это сумма чётных чисел, результат всегда будет чётным.
2. $\sum_{v \in V_{нечетн}} \deg(v)$ — это сумма нечётных чисел.

Зная, что общая сумма степеней чётна, и первое слагаемое (сумма чётных степеней) тоже чётно, мы можем заключить, что второе слагаемое (сумма нечётных степеней) также обязано быть чётным. Сумма нечётных чисел является чётной только в том случае, если количество слагаемых в ней чётно.

Таким образом, мы приходим к fundamental-ному выводу теории графов: количество вершин нечётной степени в любом графе всегда чётно.

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

а) 0;
Число 0 является чётным. Следовательно, количество вершин нечётной степени может равняться нулю. Это означает, что в графе все вершины имеют чётную степень.
Пример: цикл $C_3$ (треугольник). В этом графе 3 вершины, и степень каждой из них равна 2 (чётное число). Количество вершин с нечётной степенью равно 0.
Ответ: Да, может.

б) 1;
Число 1 является нечётным. Согласно доказанному выше, количество вершин нечётной степени в любом графе должно быть чётным, поэтому оно не может равняться 1.
Ответ: Нет, не может.

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

г) 3;
Число 3 является нечётным. Количество вершин нечётной степени не может быть равно 3.
Ответ: Нет, не может.

д) 4?
Число 4 является чётным. Следовательно, в графе может быть 4 вершины нечётной степени.
Пример: полный граф на 4 вершинах ($K_4$). В этом графе каждая из 4 вершин соединена с тремя другими, поэтому степень каждой вершины равна 3 (нечётное число).
Ответ: Да, может.

127 На конференцию собрались учёные. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся?

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

Согласно условию задачи, в этом графе есть:

• 5 вершин, имеющих степень 3 (пятеро ученых знакомы ровно с тремя другими).
• Все остальные $N-5$ вершин имеют степень 4 (где $N$ — общее число ученых).

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

Следствием из этой леммы является тот факт, что количество вершин с нечетной степенью в любом графе должно быть четным (0, 2, 4, 6 и т.д.).

Проанализируем наш случай с этой точки зрения:

В описанной ситуации есть ровно 5 ученых, у которых по 3 знакомых. Число 3 — нечетное. Следовательно, в нашем графе есть 5 вершин с нечетной степенью.

У всех остальных ученых по 4 знакомых. Число 4 — четное. Так что остальные вершины имеют четную степень.

Таким образом, общее количество вершин с нечетной степенью в этом гипотетическом графе равно 5.

Число 5 — нечетное. Это напрямую противоречит следствию из леммы о рукопожатиях, которое требует, чтобы количество вершин с нечетной степенью было четным.

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

Ответ: Нет, так оказаться не могло.

128 Придумайте и нарисуйте 3 неодинаковых графа, в каждом из которых по 6 рёбер. Найдите сумму степеней всех вершин каждого из этих графов.

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

Ниже приведены три примера неодинаковых графов с 6 рёбрами и расчёт суммы степеней их вершин.

Граф 1: Циклический граф $C_6$

Этот граф можно представить в виде шестиугольника. Он состоит из 6 вершин, и каждая вершина соединена ребром с двумя соседними, образуя замкнутую цепь. Общее количество рёбер равно 6.

Пусть вершины графа $V = \{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)$.

Степень каждой из 6 вершин (количество инцидентных ей рёбер) равна 2.

Сумма степеней всех вершин вычисляется так: $2 + 2 + 2 + 2 + 2 + 2 = 12$.

Ответ: 12.

Граф 2: Полный граф $K_4$

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

Количество рёбер в полном графе с $n$ вершинами равно $\frac{n(n-1)}{2}$. Для $n=4$ получаем $\frac{4 \times (4-1)}{2} = \frac{12}{2} = 6$ рёбер.

Каждая из 4 вершин соединена с остальными 3 вершинами, поэтому степень каждой вершины равна 3.

Сумма степеней всех вершин: $3 + 3 + 3 + 3 = 12$.

Ответ: 12.

Граф 3: Граф-звезда $K_{1,6}$

Этот граф состоит из 7 вершин. Одна из них является центральной и соединена рёбрами с остальными 6 вершинами. Периферийные 6 вершин соединены только с центральной и не соединены между собой. Общее количество рёбер равно 6.

Степень центральной вершины равна 6.

Степень каждой из 6 периферийных вершин равна 1.

Сумма степеней всех вершин: $6 + (1 + 1 + 1 + 1 + 1 + 1) = 6 + 6 = 12$.

Ответ: 12.

129 Докажите, что сумма степеней всех вершин графа вдвое больше числа рёбер в этом графе.

Данное утверждение известно в теории графов как лемма о рукопожатиях или теорема о сумме степеней вершин.

Пусть дан граф $G$ с множеством вершин $V$ и множеством рёбер $E$. Обозначим количество рёбер в графе как $|E|$. Степенью вершины $v$, обозначаемой как $\deg(v)$, называется количество рёбер, для которых $v$ является концевой вершиной. По определению, петля (ребро, соединяющее вершину саму с собой) вносит вклад, равный 2, в степень своей вершины.

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

$\sum_{v \in V} \deg(v) = 2|E|$

Доказательство.

Для доказательства этого утверждения рассмотрим, как вычисляется сумма степеней всех вершин. При подсчёте этой суммы $\sum_{v \in V} \deg(v)$ мы учитываем вклад каждого ребра. Каждое ребро по определению имеет два конца.

Рассмотрим два возможных случая для любого ребра:

1. Ребро соединяет две различные вершины, например $u$ и $v$. В этом случае при подсчёте суммы степеней оно будет учтено один раз при вычислении степени вершины $u$ (добавит 1 к $\deg(u)$) и второй раз при вычислении степени вершины $v$ (добавит 1 к $\deg(v)$). Таким образом, его общий вклад в сумму степеней равен $1 + 1 = 2$.

2. Ребро является петлёй и соединяет вершину $w$ саму с собой. По определению, петля вносит вклад 2 в степень своей вершины. Таким образом, её вклад в общую сумму степеней также равен 2.

Поскольку каждое из $|E|$ рёбер графа, независимо от его типа, вносит в общую сумму степеней всех вершин вклад, равный ровно 2, то итоговая сумма равна числу рёбер, умноженному на 2. Следовательно, утверждение $\sum_{v \in V} \deg(v) = 2|E|$ является верным, что и требовалось доказать.

Ответ: Утверждение доказано. Сумма степеней всех вершин графа равна удвоенному числу его рёбер, так как при суммировании степеней вклад каждого ребра учитывается ровно дважды: по одному разу для каждого из двух его концов (в случае обычного ребра) или дважды для одной вершины (в случае петли).

130 В некотором графе 6 вершин, степени которых равны:

а) $2, 2, 3, 3, 4, 4$;

б) $0, 1, 2, 2, 3, 4$.

Сколько всего рёбер в этом графе?

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

Если обозначить степени вершин как $d_1, d_2, ..., d_n$, а число рёбер как $E$, то формула будет выглядеть следующим образом:

$\sum_{i=1}^{n} d_i = 2 \cdot E$

Чтобы найти число рёбер $E$, необходимо сумму степеней всех вершин разделить на 2:

$E = \frac{\sum d_i}{2}$

Применим эту формулу для каждого случая.

а)

Даны степени вершин: 2, 2, 3, 3, 4, 4.

1. Вычислим сумму степеней всех вершин:

$2 + 2 + 3 + 3 + 4 + 4 = 18$

2. Найдём количество рёбер, разделив сумму на 2:

$E = \frac{18}{2} = 9$

Ответ: 9.

б)

Даны степени вершин: 0, 1, 2, 2, 3, 4.

1. Вычислим сумму степеней всех вершин:

$0 + 1 + 2 + 2 + 3 + 4 = 12$

2. Найдём количество рёбер, разделив сумму на 2:

$E = \frac{12}{2} = 6$

Ответ: 6.

253 В таблицах 9 и 10 дано распределение вероятностей некоторой случайной величины. Одна из вероятностей неизвестна. Найдите её.

a) Таблица 9

Значение: 1, 2, 3, 4, 5, 6

Вероятность: $ \frac{1}{9} $, $ \frac{1}{3} $, $ \frac{1}{6} $, , $ \frac{1}{4} $, $ \frac{1}{8} $

б) Таблица 10

Значение: -4, -3, -2, -1, 0, 1, 2, 3, 4

Вероятность: 0,05, 0,1, 0,15, 0,18, , 0,18, 0,15, 0,1, 0,05

а)

Для любого распределения вероятностей дискретной случайной величины сумма всех вероятностей должна быть равна 1. В таблице 9 не указана вероятность для значения 4. Обозначим эту вероятность как $p_4$.

Согласно свойству распределения вероятностей, мы можем записать следующее уравнение:

$\frac{1}{9} + \frac{1}{3} + \frac{1}{6} + p_4 + \frac{1}{4} + \frac{1}{8} = 1$

Чтобы найти $p_4$, сначала вычислим сумму известных вероятностей. Для этого приведем все дроби к общему знаменателю. Наименьшее общее кратное для знаменателей 9, 3, 6, 4 и 8 равно 72.

$\frac{1}{9} + \frac{1}{3} + \frac{1}{6} + \frac{1}{4} + \frac{1}{8} = \frac{1 \cdot 8}{72} + \frac{1 \cdot 24}{72} + \frac{1 \cdot 12}{72} + \frac{1 \cdot 18}{72} + \frac{1 \cdot 9}{72}$

Сложим числители:

$\frac{8 + 24 + 12 + 18 + 9}{72} = \frac{71}{72}$

Теперь найдем неизвестную вероятность $p_4$:

$p_4 = 1 - \frac{71}{72} = \frac{72}{72} - \frac{71}{72} = \frac{1}{72}$

Ответ: $\frac{1}{72}$

б)

Аналогично, для таблицы 10 сумма всех вероятностей должна быть равна 1. В данном случае неизвестна вероятность для значения 0. Обозначим ее как $p_0$.

Составим уравнение:

$0.05 + 0.1 + 0.15 + 0.18 + p_0 + 0.18 + 0.15 + 0.1 + 0.05 = 1$

Найдем сумму известных вероятностей:

$S = 0.05 + 0.1 + 0.15 + 0.18 + 0.18 + 0.15 + 0.1 + 0.05$

Суммируем значения:

$S = (0.05 + 0.05) + (0.1 + 0.1) + (0.15 + 0.15) + (0.18 + 0.18) = 0.1 + 0.2 + 0.3 + 0.36 = 0.96$

Теперь найдем неизвестную вероятность $p_0$:

$p_0 = 1 - S = 1 - 0.96 = 0.04$

Ответ: $0.04$

254 Распределение вероятностей случайной величины X задано таблицей 11.

Таблица 11

Найдите вероятность события:

а) $1 < X < 2.5$;

б) $X = 0.5 \text{ или } X > 2$;

в) $X > 0.4 \text{ или } X = 2.5$;

г) $X \text{ -- целое число}$.

а) (1 < X < 2,5)

Для нахождения вероятности события $1 < X < 2,5$ необходимо определить, какие из возможных значений случайной величины $X$ удовлетворяют этому неравенству. Согласно таблице, это значения $X=1,5$ и $X=2$. Поскольку события $X=1,5$ и $X=2$ являются несовместными, вероятность их объединения равна сумме их вероятностей.

$P(1 < X < 2,5) = P(X = 1,5) + P(X = 2)$

Подставляя значения вероятностей из таблицы, получаем:

$P(1 < X < 2,5) = 0,18 + 0,05 = 0,23$

Ответ: 0,23

б) (X = 0,5 или X > 2)

Данное событие является объединением двух несовместных событий: "X = 0,5" и "X > 2". Вероятность этого события равна сумме вероятностей составляющих его событий.

$P(X = 0,5 \text{ или } X > 2) = P(X = 0,5) + P(X > 2)$

Вероятность $P(X = 0,5)$ дана в таблице и равна 0,04.

Событию $X > 2$ соответствуют значения $X=2,5$, $X=3$, $X=3,5$ и $X=4$. Найдем вероятность этого события как сумму вероятностей:

$P(X > 2) = P(X=2,5) + P(X=3) + P(X=3,5) + P(X=4) = 0,15 + 0,11 + 0,1 + 0,07 = 0,43$

Теперь найдем искомую вероятность:

$P(X = 0,5 \text{ или } X > 2) = 0,04 + 0,43 = 0,47$

Ответ: 0,47

в) (X > 0,4 или X = 2,5)

Событие "X > 0,4 или X = 2,5" является объединением событий $A = \{X > 0,4\}$ и $B = \{X = 2,5\}$. Поскольку значение $X=2,5$ удовлетворяет условию $X > 0,4$, то событие B является частью события A. Это означает, что их объединение совпадает с событием A. Таким образом, задача сводится к нахождению вероятности $P(X > 0,4)$.

Условию $X > 0,4$ удовлетворяют все возможные значения случайной величины, кроме $X=0$. Удобнее вычислить эту вероятность через вероятность противоположного события $X \le 0,4$, которому соответствует только одно значение $X=0$.

$P(X > 0,4) = 1 - P(X \le 0,4) = 1 - P(X=0) = 1 - 0,1 = 0,9$

Ответ: 0,9

г) (X — целое число)

Событие "X — целое число" означает, что случайная величина X принимает одно из целочисленных значений, указанных в таблице. Это значения 0, 1, 2, 3, 4. Вероятность этого события равна сумме вероятностей соответствующих несовместных событий.

$P(X \text{ — целое}) = P(X=0) + P(X=1) + P(X=2) + P(X=3) + P(X=4)$

Подставляя значения из таблицы, получаем:

$P(X \text{ — целое}) = 0,1 + 0,2 + 0,05 + 0,11 + 0,07 = 0,53$

Ответ: 0,53

255 По таблице распределения (табл. 12) постройте диаграмму распределения случайной величины $Z$.

Таблица 12

Значение $Z$: -5, -3, -1, 1, 3, 5

Вероятность: 0,1; 0,15; 0,25; 0,25; 0,15; 0,1

Построение диаграммы распределения случайной величины Z

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

Сначала проверим корректность данных, убедившись, что сумма всех вероятностей равна единице, что является обязательным свойством для любого закона распределения вероятностей:
$P_{сумма} = 0,1 + 0,15 + 0,25 + 0,25 + 0,15 + 0,1 = 1,0$.
Поскольку сумма вероятностей равна 1, таблица задает корректный закон распределения.

Теперь построим диаграмму в прямоугольной системе координат:

1. На горизонтальной оси (оси абсцисс) откладываются возможные значения случайной величины Z. В нашем случае это точки: $-5, -3, -1, 1, 3, 5$.
2. На вертикальной оси (оси ординат) откладываются соответствующие им вероятности P. Максимальная вероятность в таблице равна 0,25, поэтому шкалу на этой оси удобно разметить с шагом 0,05 (например, 0; 0,05; 0,10; 0,15; 0,20; 0,25).
3. Для каждого значения $z_i$ из набора значений Z строится вертикальный столбец (или отрезок), высота которого равна соответствующей вероятности $p_i$.

Таким образом, мы получим следующие столбцы:
- из точки $Z = -5$ на оси абсцисс проводим вертикальный столбец высотой $P = 0,1$;
- из точки $Z = -3$ — столбец высотой $P = 0,15$;
- из точки $Z = -1$ — столбец высотой $P = 0,25$;
- из точки $Z = 1$ — столбец высотой $P = 0,25$;
- из точки $Z = 3$ — столбец высотой $P = 0,15$;
- из точки $Z = 5$ — столбец высотой $P = 0,1$.

Полученная столбчатая диаграмма будет состоять из шести столбцов. Заметим, что диаграмма симметрична относительно оси ординат, так как для противоположных по знаку значений Z ($z$ и $-z$) вероятности совпадают ($P(Z=-5)=P(Z=5)$, $P(Z=-3)=P(Z=3)$, $P(Z=-1)=P(Z=1)$).

Ответ: Диаграмма распределения для случайной величины Z представляет собой столбчатую диаграмму, построенную в системе координат $(Z, P)$. На горизонтальной оси Z отмечены точки $-5, -3, -1, 1, 3, 5$. Из каждой из этих точек вверх построены вертикальные столбцы, высоты которых равны соответствующим вероятностям: $0,1; 0,15; 0,25; 0,25; 0,15; 0,1$.

256 По диаграмме 2 постройте таблицу распределения случайной величины $T$.

Диаграмма 2

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

Из диаграммы 2 находим значения случайной величины T и их вероятности P:

• Для значения T = 1, высота столбца соответствует 0,1 на вертикальной оси. Следовательно, вероятность $P(T=1) = 0,1$.
• Для значения T = 2, высота столбца соответствует 0,2. Следовательно, вероятность $P(T=2) = 0,2$.
• Для значения T = 3, высота столбца соответствует 0,3. Следовательно, вероятность $P(T=3) = 0,3$.
• Для значения T = 4, высота столбца соответствует 0,4. Следовательно, вероятность $P(T=4) = 0,4$.

Для проверки убедимся, что сумма всех вероятностей равна 1, так как это является обязательным условием для любого закона распределения вероятностей:

$0,1 + 0,2 + 0,3 + 0,4 = 1,0$

Условие выполняется. Теперь можно составить таблицу распределения. В первой строке таблицы укажем возможные значения случайной величины T, а во второй — соответствующие им вероятности.

Ответ: