40
чтобы ни на одном берегу не оставалось больше женщин, чем мужчин. Как им переправиться через реку?
3.Муж, жена и двое детей должны переправиться на противоположный берег реки при помощи лодки. Муж и жена весят по 100 кг, а дети - по 50. Как им быть, если лодка вмещает не более 100 кг, и каждый из них умеет грести?
4.Человеку необходимо было переправить через реку с помощью лодки волка, козу и капусту. В лодке мог поместиться только человек, а с ним или волк, или коза, или капуста. Но если оставить волка с козой без человека, то волк съест козу, если оставить козу с капустой, то она съест капусту, а в присутствии человека никто никого не ел. Человек все-таки перевез через реку и волка, и козу, и капусту. Как он это сделал?
№ 5.16. Задачи на поиск фальшивой монеты решите с помощью графов.
1.Из 9 монет одна фальшивая (более легкая). Как двумя взвешиваниями на чашечных весах (без разновесов) определить фальшивую монету?
2.Из 80 одинаковых по виду монет одна более легкая (фальшивая). Как четырьмя взвешиваниями на чашечных весах (без разновесов) определить фальшивую?
3.Из 28 монет одна более легкая. Как при помощи 4 взвешиваний (без разновесов) определить ее?
4.Из 27 монет одна более легкая. Как при помощи З взвешиваний (без разновесов) определить ее?
5.Из 81 монеты одна более легкая. Показать, что 4 взвешиваний(без разновесов) достаточно, чтобы ее определить.
6.Из 82 монет одна более легкая. Какое наименьшее число взвешиваний (без разновесов) необходимо для определения этой монеты?
7.Из т одинаковых по виду монет одна фальшивая (более легкая). Указать наименьшее число взвешиваний
(без разновесов) необходимых для определения фальшивой монеты.
Ответы, указания, решения к разделу 5
№5.1. Указание. Граф с n вершинами не будет связным, если существует подграф с n -1 вершиной, число ребер которого не меньше Сn2 . Рассмотрите полный граф с n -1 вершиной.
№5.2. Указание. Рассмотрите связные и не связные графы, с циклами и ациклические. Обсудите, к чему приведет добавление одной вершины. Начните с одновершинного графа.
№5.3. Таких графов 3.
№5.4. Изоморфны графы G1 и G3.
№5.5. Указание. Самодополнительнве графы должны иметь одинаковое количество ребер со своим дополнением, т.е. число ребер полного графа должно быть четным.
№ 5.6. Рассмотрим пример. Дана матрица смежности |
01010 |
|
|||||
Т.к. матрица не симметрична относительно главной диагонали, то она является матрицей смеж- |
|
|
|||||
ности орграфа. Соответствующий граф представлен на рис |
00111 |
|
|||||
11001 |
|
||||||
|
|
|
|
|
|||
1 |
|
|
|
|
|
|
|
|
|
|
|
01000 |
|||
|
|
|
|
||||
|
|
○2 |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
10010 |
|
|
4 ○ ○3
5○
Рис. 39. Орграф, заданный матрицей смежности
№5.7. Указание. Рассмотрите число вершин, смежных с каждой вершиной.
№5.8. Указание. Для наглядности нарисуйте граф. Заодно проверьте, не содержит ли ошибок матрица смежности данного графа, и внесите исправления при их наличии.
Составьте таблицу значений λ I для каждой i-ой вершины, положив вначале λ0 = 0, а остальные λ = ∞. Обо-
значим через ℓ ij расстояние между i-той и j –той вершинами (вес ребра). Если λ j > λ I + ℓ i j , то полагаем λ j = λ I + ℓ i j . После того, как будут просмотрены все вершины, мы получим значения λ, выражающие кратчайшее расстояния взятой вершины от начальной.
Для нахождения кратчайшего пути, надо, начиная с последней вершины, найти разности взятого λ I и смежными λ j. То значение j, для которого λ I - λ j = ℓ i j, и будет номером вершины кратчайшего пути. Заметим, что он может быть не один.
№5.9. Указание. Для наглядности нарисуйте граф и расставьте веса ребер. Создайте копию расположения вершин (будущий остов). Из всех ребер выберете наименьшее и внесите его в остов. Из оставшихся ребер выбираете наименьшее и заносите его в остов только в том случае, если оно не образует цикла с ранее введенными ребрами. И так до тех пор, пока остов не будет построен.
№5.10. Указание. Составьте список смежности.
№5.11. Указание. Составьте список смежности.
№5.13. е) Х= {(1, 3), (2, 2), (2, 3), (2, 5), (3, 5), (3, 6), (2, 7), (4, 1), (4, 6), (4, 2), (6, 4), (6, 3), (7, 2), (7, 6)).
41
|
2 |
5 |
|
• • |
• |
1• |
• |
•6 |
|
|
3 |
|
|
|
|
|
• |
|
|
|
• |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
7 |
|
|
|
|
|
|
|
|
|
Рис. 40. Орграф задачи № 5.13. е) |
|
|
|
|
|
|||||||||
|
2) таблица инцидентности графа G |
|
|
|
|
|
||||||||||
|
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
Х7 |
Х8 |
Х9 |
Х10 |
Х11 |
Х12 |
Х13 |
Х14 |
||
1 |
1 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
|
1 |
1 |
1 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
3 |
0 |
|
0 |
0 |
0 |
1 |
1 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
5 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
1 |
0 |
0 |
7 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
3) таблица смежности графа G
|
вершины |
1 |
2 |
3 |
|
4 |
5 |
6 |
7 |
|
1 |
0 |
0 |
1 |
|
0 |
0 |
0 |
0 |
|
2 |
0 |
1 |
1 |
|
0 |
1 |
|
1 |
|
3 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
4 |
1 |
1 |
0 |
|
0 |
0 |
1 |
0 |
|
5 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
|
6 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
|
7 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
4) таблица смежности неориентированного графа G1 |
|
|
|
|
|||||
|
вершины |
1 |
2 |
3 |
|
4 |
5 |
6 |
7 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
|
2 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
|
3 |
1 |
1 |
0 |
|
0 |
1 |
1 |
0 |
|
4 |
1 |
1 |
0 |
|
0 |
0 |
1 |
0 |
|
5 |
0 |
1 |
1 |
|
0 |
0 |
0 |
0 |
|
6 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
|
7 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
5) степени вершин
Вершины |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Полустепень исхода G |
1 |
6 |
2 |
3 |
0 |
2 |
2 |
Полустепень захода G |
1 |
5 |
3 |
1 |
2 |
3 |
1 |
Степень вершины G1 |
2 |
6 |
4 |
3 |
2 |
3 |
2 |
№ 5.14. е) надо изготовить табурет. Сценарий:
1.Заготовить исходный материал: 4 бруска для ножек 3 х 3 см, длиной не менее 50 см ; 4 дощечки 2 х 4 см, длиной не менее 35 см для верхней обвязки; 4 дощечки 1 х 2 см, длиной не менее 35 см для средней обвязки; материал для сидения 2 х 50 х 50 см; клей.
2.Изготовить 4 ножки.
3.Изготовить верхнюю обвязку.
4.Изготовить среднюю обвязку.
5.Соединить ножки с помощью обвязок.
6.Обработать сидение.
7.Соединить сидение с ножками
8.Табурет готов.
Граф
2
5 |
5 |
7 |
42
1 |
|
|
3 |
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис.41. Граф изготовления табурета |
|||
№ 5.15. 4) |
введем обозначения • - волк, ∆ - коза, ° -капуста, λ - человек. Нарисуем граф перевозок |
|||||||
∆ |
|
|
|
|
|
|
∆ λ |
|
|
|
|
|
|
||||
|
λ |
• |
λ |
|
° λ |
|||
|
|
|
|
λ |
|
λ |
|
|
|
|
|
|
|
|
|||
λ ∆ λ |
|
• |
∆ |
° |
|
|
|
|
Рис. 42. Граф перквозок волка, козы и капусты Будем считать, что все находятся на правом берегу. Человек перевозит козу на левый берег, оставляет её
там и возвращается. Перевозит на левый берег волка, оставляет его там, забирает козу и с ней возвращается. Оставив козу на правом берегу, человек перевозит капусту, возвращается и перевозит козу.
№ 5.16. 3) Решение. Граф будет иметь вид
28
9 |
9 |
9 |
1 |
9
3 3 3
3
1 1 1
●●
Рис. 43. Граф поиска фальшивой монеты
Разобьём 28 монет на 4 группы. Три из них содержат по 9 монет, а четвертая одну.
Сравниваем первые две группы. Если весы остались в равновесии, то надо исследовать третью группу. Если весы вышли из равновесия, то для исследования берется более легкая группа. В любом случае после первого взвешивания дело сводится к исследованию группы из 9 монет.
Разбиваем эту группу на 3 подгруппы по 3 монеты каждая. Сравниваем первые две подгруппы. Если весы остались в равновесии, то надо исследовать третью подгруппу. Если весы вышли из равновесия, то для исследования берется более легкая подгруппа. В любом случае после второго взвешивания дело сводится к исследованию группы из 3 монет.
Сравниваем первые две монеты. Если весы вышли из равновесия, то более легкая монета обнаружена. Если весы остались в равновесии, то надо сравнить третью монету и монету из четвертой группы. Четвертым взвешиванием устанавливаем более легкую монету