Придумайте и нарисуйте два графа, в котором 5 вершин со степенями 2; 6 вершин со степенями 1, 1, 2...

Question

Вопрос:

Придумайте и нарисуйте два графа, в котором 5 вершин со степенями 2; 6 вершин со степенями 1, 1, 2...

Фотография

Ответ ассистента

Accepted Answer

Ответ: в графе с 5 вершинами, степени которых равны 2, будет 5 рёбер. Решение: 1. Степень вершины — это количество рёбер, выходящих из неё. 2. Согласно лемме о рукопожатиях, сумма степеней всех вершин графа равна удвоенному количеству его рёбер: $\sum deg(v) = 2E$. 3. В первом случае имеем 5 вершин со степенью 2. Сумма степеней: $5 \cdot 2 = 10$. 4. Количество рёбер: $E = 10 / 2 = 5$. Таким графом является простой цикл (пятиугольник). Для второго случая (6 вершин со степенями 1, 1, 2, ...): так как список степеней на фото обрезан, точно определить граф нельзя. Однако принцип тот же: сумма степеней должна быть чётной.

Придумайте и нарисуйте два графа, в котором 5 вершин со степенями 2; 6 вершин со степенями 1, 1, 2...

Ответ ассистента

Другие решения