Итоговая домашняя работа по теме «Графы»

1) Для построения графа с вершинами степеней 1, 1, 2, 3, 3 соединим вершины так, чтобы общее количество связей соответствовало условию. Обозначим вершины $A, B, C, D, E$: $A(1)-B(3), B(3)-C(3), C(3)-D(2), D(2)-E(1), B(3)-C(3)$ (второе ребро между ними или путь через другую вершину). Проще всего представить это как путь $E-D-C-B-A$, где у $B$ и $C$ есть ещё по одной связи между собой. 2) По лемме о рукопожатиях: сумма степеней вершин равна двойному количеству рёбер. Сумма степеней: $0 + 1 + 2 + 3 = 6$. Количество рёбер: $6 / 2 = 3$. **Ответ: 3**. 3) Используем ту же лемму: сумма степеней вершин в 2 раза больше количества рёбер. $̑ = 12 \times 2 = 24$. **Ответ: 24**. 4) Посчитаем сумму степеней: $4 \times 2 + 2 \times 3 = 8 + 6 = 14$. Так как сумма степеней четная (14), такой граф существует. Пример: 6 городов (вершин) можно расположить по кругу, соединив каждый с двумя соседями (степень 2), и добавить 3 перемычки между оставшимися парами городов для получения степени 3. **Ответ: Можно**. 5) Анализ рисунка 3: - Число вершин: 6 (А, Б, В, Г, Д и отдельная точка С). - Число рёбер: 6 (АБ, БВ, ВД, АД, ДГ, ГВ). - Степень каждой вершины: $A=2, Б=2, В=3, Г=2, Д=3, С=0$. - Сумма степеней: $2 + 2 + 3 + 2 + 3 + 0 = 12$. 6) Чтобы определить наименьшее число кусков проволоки, нужно найти количество вершин с нечётной степенью. По теории графов, минимальное количество путей, покрывающих все рёбра, равно половине количества нечётных вершин (если их 0 или 2, то нужен 1 кусок). В данной решётке: - Вершины по углам (4 шт.): степень 3 (нечётные). - Вершины на границах (6 шт.): степень 3 (нечётные). - Внутренние вершины (4 шт.): степень 4 (чётные). Итого: 10 нечётных вершин. Количество кусков: $10 / 2 = 5$. **Ответ: 5**.