Нарисуйте в тетради какое-нибудь дерево, в котором 7 вершин, причём степень 1 имеют ровно: а) 2 вершины;

3. Нарисуйте в тетради какое-нибудь дерево, в котором 7 вершин, причём степень 1 имеют ровно: а) 2 вершины; б) 4 вершины; в) 6 вершин. Допущение: под «степенью 1» имеется в виду степень вершины графа, равная 1 (висячая вершина). Поскольку дерево — это связный граф без циклов, то сумма степеней всех вершин равна удвоенному числу рёбер. В дереве с $n$ вершинами ровно $n-1$ ребро. В нашем случае $n=7$, значит, количество рёбер $m = 7-1 = 6$. Сумма степеней всех вершин равна $2m = 2 \times 6 = 12$. а) Пусть 2 вершины имеют степень 1. Остальные $7-2=5$ вершин должны иметь степень больше или равную 2, так как в дереве нет изолированных вершин (степень 0). В таком случае, две вершины имеют степень 1 (их вклад в сумму степеней $1+1=2$). Оставшиеся 5 вершин должны иметь сумму степеней $12-2 = 10$. Если все эти 5 вершин будут иметь степень 2, то их сумма степеней будет $5 \times 2 = 10$. Это возможно. Пример дерева: ``` o / \ o o | | o---o | | o---o ``` (Это линейный граф, где две концевые вершины имеют степень 1, а остальные 5 вершин имеют степень 2). :::div .chart-container @chart-1::: б) Пусть 4 вершины имеют степень 1. Остальные $7-4=3$ вершины должны иметь степень больше или равную 2. Сумма степеней этих 4 вершин равна $4 \times 1 = 4$. Тогда сумма степеней оставшихся 3 вершин должна быть $12-4 = 8$. Средняя степень этих 3 вершин: $8/3 = 2,66...$. Это означает, что хотя бы одна из этих 3 вершин должна иметь степень больше 2. Например, можно сделать так: две вершины по степени 2, одна вершина степень 4 ($2+2+4=8$). Это возможно. Пример дерева: ``` o /|\ о о о | | | o о о ``` (Центральная вершина имеет степень 4, две соседние вершины имеют степень 2, и четыре висячие вершины имеют степень 1). :::div .chart-container @chart-2::: в) Пусть 6 вершин имеют степень 1. Остальная $7-6=1$ вершина должна иметь степень, равную $12-6 = 6$. Это возможно. Такая вершина будет соединена со всеми 6 висячими вершинами. Пример дерева: ``` o /|\\ o o o o | | | o o o ``` (Это звезда, где центральная вершина имеет степень 6, а все остальные 6 вершин имеют степень 1). :::div .chart-container @chart-3:::