Дискретная математика Графы
Задача 1
В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два
города соединены авиалинией в том и только в том случае, если двузначное число, составленное из
цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?
Задача 2
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был
соединён ровно с пятью другими?
Задача 3
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было четыре
телефона, каждый из которых соединен с тремя другими, восемь телефонов, каждый из которых
соединен с шестью, и три телефона, каждый из которых соединен с пятью другими?
Задача 4
Докажите, что число людей, когда-либо живших на Земле и сделавших нечётное число рукопожатий,
чётно.
Задача 5
Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?
Задача 6
Докажите, что граф с n вершинами, степень каждой из которых не менее n–1
/2
, связен.
Задача 7
В Тридевятом царстве лишь один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из
города Дальний – одна, а из всех остальных городов – по 20. Докажите, что из столицы можно долететь в
Дальний (возможно, с пересадками).
Задача 8
В стране из каждого города выходит 100 дорог и от каждого города можно добраться до любого другого.
Одну дорогу закрыли на ремонт.
Докажите, что и теперь от каждого города можно добраться до любого другого.
Задача 9
а) Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром
10 см?
б) Какое наименьшее число раз придется ломать проволоку, чтобы всё же изготовить требуемый каркас?
Задача 10
Доска имеет форму креста, который получается, если из квадратной доски 4×4 выкинуть угловые клетки.
Можно ли обойти её ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно
по разу