Элементы дискретной математики - 80 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

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

Рубрика: 

80
141.
Дана матрица смежности графа, определить, является ли он эйлеровым. Ответ
обоснуйте.
1 2 3 4 5 6 7
1 0 1 1 0 0 0 1
2 0 0 1 0 1 0 0
3 0 1 0 0 0 0 1
4 1 0 0 0 1 1 0
5 1 0 0 1 0 0 0
6 1 0 0 1 0 0 0
7 0 0 0 1 0 1 0
142. Решите задачу 62, считая, что заданы матрицы смежности ориентированного графа.
143. На ребрах связного графа расставлены стрелки так, что для каждой вершины числа
входящих и выходящих ребер равны. Докажите, что двигаясь по стрелкам, можно
добраться от любой вершины до любой другой.
144.
В связном неориентированном графе степени всех вершин четны. Докажите, что на
ребрах этого графа можно расставить стрелки так, чтобы выполнялись следующие
условия: а) двигаясь по стрелкам, можно добраться от любой вершины до любой другой;
б) для каждой вершины числа входящих и выходящих ребер равны.
145.
На плоскости отмечено некоторое конечное число точек. Некоторые пары точек
являются началами и концами векторов, причем число векторов, выходящих из любой
точки равно числу входящих в неё. Найдите сумму векторов.
146.
В некоторой стране каждый город соединен с каждым дорогой с односторонним
движением. Докажите, что найдется город, из которого можно добраться в любой другой.
147.
Несколько команд сыграли между собой круговой турнир по волейболу. Будем
говорить, что команда А сильнее команды В, если либо А выиграла у В, либо существует
команда С такая, что А выиграла у С, а С - у В. а) Докажите, что есть команда, которая
сильнее всех. б) Докажите, что команда, выигравшая турнир
, сильнее всех.
148. В одном государстве 100 городов, и каждый соединен с каждым дорогой с
односторонним движением. Докажите, что можно поменять направление движения на
одной дороге так, чтобы от любого города можно было доехать до любого другого.
149.
20 команд сыграли круговой турнир по волейболу. Докажите, что команды можно
занумеровать числами от 1 до 20 так, что 1-я команда выиграла у 2-й, 2-я - у 3-й, ..., 19-я у
20-й.
150.
Докажите, что если победитель турнира по волейболу, проведенного по круговой
системе, проиграл команде В, то существует команда С, выигравшая у В, у которой
выиграл победитель.

Страницы