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

UptoLike

ВУЗ: 

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

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

Рубрика: 

25
которого – данные отрезки, а ребро соединяет 2 вершины, когда
2 отрезка пересекаются. 6. Рассмотрим два города, и пусть они
не соединены путем. Так как каждый соединен не менее чем с 7
другими, при этом города различны (если 2 совпадают, то есть
путь, соединяющий исходные города), то мы указали не менее
16 городов. 7. Аналогично задаче 1.6. 8. Рассмотреть двух не-
знакомых ученых и их знакомых. 9. Для решения задачи по-
строим граф знакомств
G
, в котором вершины будут соединены
зеленым ребром, если соответствующие им люди дружат, и
красным – если враждуют. Из каждой вершины графа выходит
ровно по одному зеленому и красному ребру, поэтому степень
каждой вершины равна двум. Следовательно, каждая компонен-
та графа
G
является циклом. Так как в этом цикле зеленые и
красные ребра чередуются, то он содержит чётное число ребер.
Из теоремы Кенига следует, что построенный граф знакомств
является двудольным. Разбиение его вершин на доли
A
и
B
определит разбиение группы людей на две компании. 10. Пусть
в командах «синих» и «красных» по
n
игроков. Поставим в со-
ответствие каждому игроку вершину графа и соединим ребрами
вершины, соответствующие проведенным играм. Так как каждая
пара игроков разных команд играла между собой, то получится
полный двудольный граф
nn
K
,
. Этот граф имеет
2
n
ребер. Если
встречу между двумя игроками выиграл «синий» игрок, то соот-
ветствующее ребро окрасим синим цветом, если «красный» - то
красным. Обозначим через
x
число красных ребер, тогда синих
будет
x4
. Всех ребер в графе
2
n
. Поэтому
2
4 nxx
,
2
5 nx
. Отсюда
5
n
. В каждой команде было по пять игро-
ков. 11. Рассмотрим двудольный граф, в котором вершины обо-
значают членов делегаций и две вершины будут соединены реб-
ром, если соответствующие им люди обменялись рукопожатием.
Пусть в делегациях
p
и
q
членов ( 22
qp ). Рассмотрим
полный двудольный граф
qp
K
,
, который имеет
q
p
ребер. По-
скольку pq
22 , то число ребер в графе
qp
K
,
является

Страницы