ВУЗ:
Составители:
Рубрика:
29
да и направим от городов с меньшими номерами к городам с
большими номерами. 4. Рассмотрим эйлеров цикл, проходящий
по всем ребрам графа, и ориентируем все ребра в соответствии с
порядком прохождения цикла. 5. Докажите, что существует
замкнутый путь вдоль стрелок, проходящий по каждому ребру
ровно один раз. 6. Индукция по числу городов. База очевидна.
Для доказательства индукционного перехода удалим сначала
один из городов. В силу индукционного предположения есть
город
A
с требуемым свойством. Вспомним теперь про удален-
ный город. Если в него ведет хотя бы одна дорога, то город
A
-
искомый. В противном случае сам удаленный город удовлетво-
ряет требуемому свойству. 7. База – для трех городов. Для дока-
зательства индукционного перехода удалите город, имеющий и
входящие, и выходящие дороги. 8. Зададим схему дорог в стране
ориентированным графом. Рассмотрим две произвольные такие
вершины
u
и
v
, что в орграфе нет дуги
vu, . Покажем, что
расстояние между двумя любыми вершинами орграфа не более
двух. Пусть из вершины
u
выходят дуги
1
,uu ,
2
,uu ,…,
50
,uu , а в вершину
v
входят дуги
vv ,
1
,
vv ,
2
,…,
vv ,
50
.
Среди вершин
i
u и
j
v должна существовать общая вершина
w
,
так как в противном случае в орграфе окажется не менее 102
вершин. Маршрут
vwu ,, в орграфе определяет нужный мар-
шрут проезда городов. 9. Опишем симпатии школьников ориен-
тированным графом. Если полустепень исхода
k
каждой вер-
шины равна 15, то орграф содержит
4501530
дуг. В то же
время в орграфе 435
2
29
30 пар вершин. Поэтому хотя бы
одна пара должна быть соединена двумя противоположно на-
правленными дугами. Школьники, соответствующие этим вер-
шинам, испытывают взаимные симпатии. 10. Опишем прохо-
дящее соревнование ориентированным графом. В этом графе
вершина
i
v обозначает команду
i
V и дуга
ji
vv , существует
тогда и только тогда, когда команда
i
V выиграла у команды
j
V .
