Задачи и упражнения

• 1. Можно ли спроектировать такой город с односторонним движением на его улицах, чтобы в каждый перекресток входило по 2 дороги, а выходило по 4 дороги?
• 2. В некоторой стране есть столица и еще 100 городов. Некоторые пары городов соединены дорогами с односторонним движением, причем, два города в одном направлении может соединять не более чем одна дорога. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя приехать ни из одного города.
• 3. Можно ли так ориентировать ребра полного графа, чтобы в нем не появилось контуров?
• 4. Для каждого из орграфов, изображенных на рис. 196, укажите количество росчерков, необходимое для согласованного с ориентацией изображения.

Рис. 196

• 5. На множестве чисел Х=[ 1, 2, 3,4, 5, 6, 7, 8, 9, 10} бинарное отношение А задано по закону: числа а и b находятся в отношении А, если они имеют равные остатки при делении на р-3. Докажите, что А — отношение эквивалентности, и постройте граф этого отношения. Сколько он имеет компонент связности? Обобщите это упражнение для случая, когда X — произвольное подмножество целых чисел, ар- некоторое натуральное число.
• 6. Пусть X — это некоторое множество людей (например, ученики некоторого класса). На множестве X рассмотрим бинарное отношение «старше». Что можно сказать о свойствах графа этого отношения?