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

UptoLike

ВУЗ: 

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

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

Рубрика: 

26
функцией от
p
и равно
pppppf 2222
2
. Функ-
ция
pf имеет максимум при 11
p , и этот максимум как раз
равен 121. Поэтому в делегациях по 11 человек, и все члены
разных делегаций обменялись рукопожатиями. 12. Пусть 9 «а»
классу соответствует доля
A
графа
G
, в которой будет
m
вер-
шин, а 9 «б» - доля
B
, в которой будет
n
вершин. Число ребер,
выходящих из вершин доли
A
, равно
m3
, а из вершин доли
B
–
n3
. Из теоремы 1.8 следует, что
nm 33
, отсюда
m
n
и
число учеников в классах одинаково. 13. Построим граф, в ко-
тором вершины обозначают отрезки и две вершины соединены
ребром тогда и только тогда, когда соответствующие им отрезки
пересекаются. Поскольку горизонтальные отрезки пересекаются
только с вертикальными, а вертикальные – только с горизон-
тальными, то построенный граф будет двудольным. Сумма сте-
пеней вершин, соответствующих горизонтальным отрезкам, ра-
вна 15, а сумма степеней вершин, соответствующих вертикаль-
ным отрезкам, равна 16. Однако по теореме 1.8 эти суммы
должны быть равны. Следовательно, заданный рисунок невоз-
можен.
2. 1. Нельзя. У соответствующего графа есть четыре нечет-
ных вершины. 2. а) Можно; б) нельзя. Рисуя граф, в каждую
вершину, за исключением начальной и конечной, мы войдем
столько же раз, сколько выйдем из нее. Поэтому степени всех
вершин должны быть четными. 3. Нет, нельзя. 4. а) Если это
возможно, то ясно, что проволока идет по ребрам куба без нало-
жения, то есть мы как бы нарисовали каркас куба, не отрывая
карандаша от бумаги. Но это невозможно, так как у куба восемь
нечетных вершин. б) Поскольку нечетных вершин восемь, то
таких кусков нужно не менее четырех. 5. Доказательство можно
провести индукцией по
n
. Для доказательства индукционного
перехода выберем две нечетные вершины, соединим их путем и
временно удалим все его ребра. Граф распадётся на компоненты
связности. Присоединим теперь к удаленному пути компоненты
связности, которые, очевидно, не содержат нечетных вершин.
6. а) Нельзя; б) можно. 7. а) Да. Например, все улицы прямые и

Страницы