В графе 10 вершин, нет кратных рёбер и петель. Какова наибольшая возможная степень вершины в этом графе?
от

1 Ответ

дано:  
Количество вершин в графе = 10  
Нет кратных рёбер и петель.  

найти:  
Наибольшая возможная степень вершины в графе.  

решение:  
1. В графе с n вершинами максимальное количество рёбер можно рассчитать по формуле:  
   m = n(n - 1) / 2  
   Для n = 10:  
   m = 10(10 - 1) / 2 = 10 * 9 / 2 = 45.  

2. Степень вершины – это количество рёбер, инцидентных данной вершине. Если граф простой, максимальная степень может быть в пределах от 0 до n - 1 (все другие вершины соединены с данной).  

3. Для максимальной степени одной вершины, она может быть соединена с остальными 9 вершинами. Таким образом, максимальная степень = 9.  

ответ:  
9.
от