Файл: Комбинаторика это раздел дискретной математики, в котором изучаются вопросы о том, сколько различных комбинаций можно составить из заданных элементов (объектах) с учетом тех или иных условий..pdf

Определение. Пусть G – орграф. Полустепенью
исхода r
–
(v) вершины v графа G называется число дуг, выходящих из v, полустепенью захода r
+
(v) – число дуг, заходящих в v.
Предложение. Сумма полустепеней исхода всех вершин графа равна суммe полустепеней захода всех вершин.

Задача 8. Можно ли спроектировать такой город с односторонним движением на его улицах, чтобы в каждый перекресток входило по 2 дороги, а выходило по 4 дороги?
Решение. Нет. Сумма положительных полу степеней всех вершин равна сумме отрицательных полу степеней

Задача 9
В некоторой стране есть столица и еще 100 городов.
Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.
Решение
Пусть в столицу входит a дорог. Тогда общее число "входящих" дорог равно 21 · 100 + a, а общее количество "выходящих" дорог не больше 20 · 100 + (100 - a).
Поэтому, 21*100+а≤20*100+(100-а) т.е. 2*а ≤100
Таким образом, a = 0.

Спасибо за внимание