дано:
- количество вершин n = 12
найти:
- возможные значения степеней вершин в простом графе.
решение:
В простом графе между любыми двумя вершинами может быть не более одного ребра, и петли отсутствуют.
1. Максимальная степень вершины:
- Если одна вершина соединена со всеми остальными, её степень максимальна.
- Максимальная степень вершины = n - 1 = 12 - 1 = 11.
2. Минимальная степень вершины:
- Вершина может не иметь рёбер, то есть быть изолированной.
- Минимальная степень вершины = 0.
3. Дополнительное ограничение на сумму степеней:
- Сумма всех степеней всех вершин в графе равна удвоенному числу рёбер:
- S = 2 * m, где m — количество рёбер.
- Поскольку в простом графе количество рёбер не может превышать (n * (n - 1)) / 2, получаем:
- Максимальное количество рёбер = (12 * 11) / 2 = 66.
Таким образом, сумма степеней не может превышать 132 (так как 2 * 66 = 132).
Ответ:
Степени вершин могут изменяться в пределах от 0 до 11, и сумма степеней всех вершин должна быть четной и не превышать 132.