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

UptoLike

ВУЗ: 

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

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

Рубрика: 

24
движение. Тем не менее, из каждой точки города можно про-
ехать в любую другую. Докажите, что можно предложить такой
маршрут патрулирования для полицейской машины, который
начинается и оканчивается в одном и том же месте и проходит
через каждый участок улиц между двумя перекрестками по
крайней мере один раз.
12. В городе после установления одностороннего движения
оказалось, что число улиц, по которым можно въехать на каж-
дый перекресток, равно числу улиц, по которым можно из него
выехать. Докажите, что можно предложить такой маршрут пат-
рулирования, который начинается и оканчивается в одном месте
и проходит через каждый участок улиц между двумя перекрест-
ками ровно один раз.
13. На плоскости отмечено конечное число точек. Некоторые
пары точек являются началами и концами векторов, причем
число векторов, входящих в любую точку, равно числу векторов,
выходящих из нее. Найдите сумму векторов.
ОТВЕТЫ
Решения и указания к решению задач
1. 1. Пусть это возможно. Рассмотрим граф, вершины кото-
рого соответствуют телефонам, а ребра – соединяющим их про-
водам. В этом графе 15 вершин, степень каждой из которых
равна 5. Для подсчета количества ребер в этом графе сначала
сложим степени всех его вершин. Ясно, что при таком подсчете
каждое ребро учтено дважды (так как соединяет две вершины).
Поэтому число ребер графа должно быть равно
2
5
15 . Но это
число не целое. Значит, такого графа не существует и соединить
телефоны невозможно. 2. Общее число дорог равно
200
2
4
100 . 3. Нет. Не существует графа с 15 нечетными (сте-
пени 7) вершинами. 4. В графе с 953 вершинами должно быть
четное число нечетных вершин, поэтому у нечетного числа из
них число знакомых – четно. 5. Нет. Рассмотрим граф, вершины

Страницы