Найдите наименьшее количество вершин в графе, сумма степеней вершин в котором равна 24.

Заметим, что в графе из n вершин не больше, чем n(n − 1)/2 ребер.
$ \sum_{i\ =\ 1}^{n}{deg(v_i)\ =\ 2E} $, тогда в графе должно быть 24 : 2 = 12 ребер
Предположим, что в графе не более 5 вершин, тогда ребер не более, чем 5 · 4 : 2 = 10
Тогда в графе должно быть хотя бы 6 вершин. Степень каждой вершины 4, всего 6 вершин, тогда сумма степеней – 24


info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp