В некотором графе 6 вершин, степени которых равны: 2, 2, 3, 3, 4, 4. В этом графе

Привет! Давай разберемся с этой задачкой по теории графов.

Что нам известно?

• У нас есть граф, в котором 6 вершин.
• Степени этих вершин такие: 2, 2, 3, 3, 4, 4.

Какое правило мы будем использовать?

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

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

Где:

• $$ \text{deg}(v) $$ — степень вершины (количество ребер, выходящих из нее).
• $$ V $$ — множество всех вершин графа.
• $$ E $$ — множество всех ребер графа.
• $$ |V| $$ — количество вершин.
• $$ |E| $$ — количество ребер.

Давай посчитаем!

У нас есть степени вершин: 2, 2, 3, 3, 4, 4. Сложим их:

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

Итак, сумма степеней всех вершин равна 18.

Теперь применим лемму о рукопожатиях:

$$ 18 = 2 |E| $$

Чтобы найти количество ребер ($$ |E| $$), нужно разделить сумму степеней на 2:

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

Получается, в этом графе 9 ребер.

Какой вариант ответа нам подходит?

Смотрим на предложенные варианты:

• 1. 9 рёбер
• 2. 18 рёбер
• 3. 6 рёбер

Наш расчет показал, что ребер 9.

Ответ: 1