1 Что такое степень вершины графа? 2 Может ли степень вершины равняться 0? 3 Сформулируйте теорему о сумме степеней вершин. 4 Существует ли граф, в котором только 3 вершины со степенями 1, 2 и 2?

Question

Вопрос:

1 Что такое степень вершины графа? 2 Может ли степень вершины равняться 0? 3 Сформулируйте теорему о сумме степеней вершин. 4 Существует ли граф, в котором только 3 вершины со степенями 1, 2 и 2?

Фотография

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

Accepted Answer

1 **Степень вершины графа** — это количество рёбер графа, которые к ней присоединены (инцидентны ей). 2 **Да, может.** Вершина со степенью 0 называется изолированной вершиной. 3 **Теорема о сумме степеней вершин (Лемма о рукопожатиях):** Сумма степеней всех вершин любого графа — число чётное, и она равна удвоенному количеству его рёбер. $ \sum_{i=1}^{n} deg(v_i) = 2|E| $ 4 **Ответ: Такого графа не существует.** Согласно теореме о сумме степеней, сумма степеней должна быть чётной. Посчитаем сумму степеней для этого случая: $1 + 2 + 2 = 5$. Так как 5 — число нечётное, такой граф построить невозможно. Кроме того, в любом графе количество вершин с нечётной степенью всегда должно быть чётным, а здесь такая вершина только одна (со степенью 1).

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

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