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

UptoLike

ВУЗ: 

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

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

Рубрика: 

15
ни одного цикла?
Решение. Пусть мы удалим ребро графа
G
n
-го порядка
10
,vve , принадлежащее циклу. Граф останется связным, так
как от
0
v к
1
v можно пройти по оставшейся части цикла. Уда-
лим рёбра у оставшихся циклов. Получим в результате дерево
1
G . Дерево содержит
n
вершин и
1n ребро. Пусть
N
–
число рёбер графа
G
, тогда придётся удалить 1
nN
рё-
бер. Это число называется циклическим порядком графа
G
.
3.2. Задачи
1. В графе все вершины имеют степень 3. Докажите, что в
нём есть цикл.
2. а) В стране
n
городов и некоторые из них соединены до-
рогами. При этом любые два города соединяет ровно один путь.
Сколько в этой стране дорог?
б)
n
точек соединены отрезками так, что любые две точки
связывает ровно одна цепочка отрезков. Докажите, что общее
число отрезков равно
1
n
.
3. Волейбольная сетка – прямоугольник
60050
клеток.
Какое наибольшее число верёвочек можно перерезать, чтобы
сетка не распалась?
4. В некоторой стране 30 городов, причём каждый соединён
с каждым дорогой. Какое наибольшее число дорог можно за-
крыть на ремонт так, чтобы из каждого города можно было про-
ехать в каждый другой?
5. В стране 100 городов, некоторые из которых соединены
авиалиниями. Известно, что из любого города можно долететь
до любого другого (возможно, с пересадками). Докажите, что
можно побывать в каждом городе, совершив не более а) 198 пе-
релётов; б) 196 перелётов.
6. Квадрат
88
выложили из спичек. Какое наименьшее
число спичек надо убрать, чтобы с любого поля можно было
пройти на любое другое, не перепрыгивая через спички?

Страницы