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

UptoLike

ВУЗ: 

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

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

Рубрика: 

8
1.2. Задачи
1. В городе 15 телефонов. Можно ли их соединить провода-
ми так, чтобы каждый телефон был соединён ровно с пятью
другими?
2. В государстве 100 городов, и из каждого из них выходит
4 дороги. Сколько всего дорог в государстве?
3. В турнире принимает участие 15 шахматистов. Может ли
быть, чтобы в некоторый момент каждый из них сыграл ровно 7
партий?
4. В школе 953 ученика. Одни из них знакомы, другие не
знакомы друг с другом. Доказать, что хотя бы у одного из них
число знакомых среди учеников этой школы чётно.
5. Можно ли нарисовать на плоскости 9 отрезков так, чтобы
каждый пересекался ровно с тремя другими?
6. В стране 15 городов, каждый из которых соединён доро-
гами не менее чем с семью другими. Докажите, что из любого
города можно добраться до любого другого (возможно, проезжая
через другие города), т.е. граф дорог связен.
7. Докажите, что граф с
n
вершинами, степень каждой из
которых не менее
2
1
n
, связен.
8. На конференции присутствует 50 учёных, каждый из ко-
торых знаком по крайней мере с 25 участниками конференции.
Докажите, что найдутся четверо из них, которых можно усадить
за круглый стол так, чтобы каждый сидел рядом со знакомыми
ему людьми.
9. В некоторой группе людей у каждого есть один враг и
один друг. [Если
A
– друг (враг)
B
, то
B
– друг (враг)
A
]. До-
кажите, что этих людей можно разбить на две компании так, что
в каждой компании не будет ни врагов, ни друзей.
10. В теннисном турнире каждый игрок команды «синих»
встречается с каждым игроком команды «красных». Число иг-
роков в командах одинаково и не больше восьми. «Синие» вы-

Страницы