|
Помогите, пожалуйста, решать эти задачи с объяснением и с фотом рисунка графов!!)
Задача 1. Имеется группа островов, соединённых мостами так, что от каждого острова можно добраться до любого другого. Турист обошёл все острова, пройдя по каждому мосту ровно один раз. На острове Троекратном он побывал трижды. Сколько мостов ведёт с Троекратного, если турист
а) не с него начал и не на нём закончил?
б) с него начал, но не на нём закончил?
в) с него начал и на нём закончил?
Задача 2. Докажите, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4, 2.
Задача 3. В классе больше 32, но меньше 40 человек. Каждый мальчик дружит с тремя девочками, а каждая девочка – с пятью мальчиками.
Сколько человек в классе?
Задача 4. Могут ли степени вершин в графе быть равны:
а) 8, 6, 5, 4, 4, 3, 2, 2?
б) 7, 7, 6, 5, 4, 2, 2, 1?
в) 6, 6, 6, 5, 5, 3, 2, 2?
Задача 5. На клетчатом листе закрасили 25 клеток. Может ли каждая из них иметь нечётное число закрашенных соседей?
Задача 6. Имеется 30 человек, некоторые из них знакомы. Доказать, что число человек, имеющих нечётное число знакомых, чётно.
Задача 7. В графе из каждой вершины выходит по три ребра. Может ли в нём быть 1990 рёбер?
Задача 9. Докажите, что граф с n вершинами, степень каждой из которых не менее n–1/2, связен.
Задача 10. В стране Озёрная семь озер, соединённых между собой десятью непересекающимися каналами, причём от каждого озера можно доплыть до любого другого. Сколько в этой стране островов?
Задача 11. В компании из 10 человек произошло 14 попарных ссор. Докажите, что все равно можно составить компанию из трёх друзей.
|
14.11.2019, 21:30 