Вопрос:

124 Нарисуйте какой-либо граф, в котором 5 вершин со степенями 1, 2, 2, 3, 3. 125 Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3. 126 Может ли количество вершин нечётной степени в каком-нибудь графе равняться...

Фотография

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

124. Степень вершины — это количество рёбер, которые из неё выходят. Нам нужно нарисовать граф с 5 вершинами: $A$ (ст. 1), $B$ (ст. 2), $C$ (ст. 2), $D$ (ст. 3), $E$ (ст. 3). :::div .chart-container @chart-124::: 125. Нужно нарисовать два разных (неизоморфных) графа с 6 вершинами и степенями 1, 1, 2, 2, 3, 3. Граф 1 (две отдельные части): первая часть — путь из 4 вершин ($1-2-2-1$), вторая часть — цикл из 2 вершин (не подходит по условию простых графов) или треугольник. Правильнее соединить их так: Первый вариант: Вершины со степенью 3 соединены между собой и каждая с двумя другими. Второй вариант: Вершины со степенью 3 не соединены друг с другом напрямую. :::div .chart-container @chart-125-1::: :::div .chart-container @chart-125-2::: 126. **Нет**, не может. Согласно «Лемме о рукопожатиях», сумма степеней всех вершин графа всегда чётна (она равна удвоенному числу рёбер). Если бы количество вершин с нечётной степенью было нечётным, то общая сумма степеней тоже была бы нечётной, что невозможно. Ответ: нет.

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

Что ещё задавали пользователи