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

1 Ответ

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

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

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

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

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

ответ:  
14.
от