Элементы теории графов. Сюсюкалов А.И - 28 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

Составители: 

Рубрика: 

23
4. В связном графе степени всех вершин четны. Докажите,
что на ребрах этого графа можно расставить стрелки так, чтобы
выполнялись следующие условия:
а) двигаясь по стрелкам, можно добраться от любой верши-
ны до любой другой;
б) для каждой вершины числа входящих и выходящих ребер
равны.
5. На ребрах связного графа расставлены стрелки так, что
для каждой вершины числа входящих и выходящих ребер рав-
ны. Докажите, что, двигаясь по стрелкам, можно добраться от
любой вершины до любой другой.
6. В некоторой стране каждый город соединен с каждым до-
рогой с односторонним движением. Докажите, что найдется го-
род, из которого можно добраться в любой другой.
7. В одном государстве 100 городов и каждый соединен с
каждым дорогой с односторонним движением. Докажите, что
можно поменять направление движения на одной дороге так,
чтобы от любого города можно было доехать до любого другого.
8. В стране 101 город. Города соединены дорогами с одно-
сторонним движением так, что два города соединены не более
чем одной дорогой. Из любого города выходит ровно 50 дорог, и
в любой город входит ровно 50 дорог. Докажите, что из любого
города в любой другой можно попасть, проехав не более двух
дорог.
9. В классе 30 человек. Каждому нравятся ровно
k
учени-
ков из класса. При каком минимальном
k
можно утверждать,
что обязательно найдутся два человека, которые нравятся друг
другу?
10. В волейбольном турнире проведено несколько матчей,
после чего у каждой команды оказалась хотя бы одна победа.
Докажите, что из сыгранных матчей можно выбрать несколько
так, что если учитывать только эти матчи, то у каждой команды,
принимающей участие в них, будет ровно одна победа и одно
поражение.
11. В одном приморском курортном городе улицы настолько
узкие, что в городе установлено одностороннее транспортное

Страницы