Графы

Теория и подборка задач про графы.

Полезные материалы

• Графы (Фоксфорд.Учебник)
• Деревья (Фоксфорд.Учебник)
• Эйлеровы графы (Фоксфорд.Учебник)
• Гамильтоновы графы (Фоксфорд.Учебник)
• Планарный граф (Фоксфорд.Учебник)
• Ориентированные графы (Фоксфорд.Учебник)

Подборка задач

1. Доска имеет форму креста, который получается, если из квадратной доски $4 \times 4$ выкинуть угловые клетки. Можно ли обойти ее ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по разу?
2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?
3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
4. В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
5. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 -- по 4 друга, а 10 -- по 5 друзей?
6. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими?
7. У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?
8. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?
9. Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера?
10. Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно.
11. Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?
12. В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с 7 другими. Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через другие города).
13. Докажите, что граф с $n$ вершинами, степень каждой из которых не менее $(n - 1)/2$, -- связен.
14. В Тридевятом царстве лишь один вид транспорта -- ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний -- одна, а из всех остальных городов -- по 20. Докажите, что из столицы можно долететь в Дальний (возможно, с пересадками).
15. В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого.
16. а) Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?
    б) Какое наименьшее число раз придется ломать проволоку, чтобы все же изготовить требуемый каркас?
17. Докажите, что граф, в котором любые две вершины соединены ровно одним простым путем, является деревом.
18. Докажите, что в дереве любые две вершины соединены ровно одним простым путем.
19. Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).
20. В графе все вершины имеют степень 3. Докажите, что в нем есть цикл.
21. Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.
22. В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог?
23. Докажите, что связный граф, у которого число ребер на единицу меньше числа вершин, является деревом.
24. Волейбольная сетка имеет вид прямоугольника размером $50 \times 600$ клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски?
25. В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?
26. Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими из нее ребрами так, чтобы он остался связным.
27. В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от любого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать в каждом городе, совершив не более
    а) 198 перелетов;
    б) 196 перелетов.
28. В стране Озерная 7 озер, соединенных между собой 10 каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов?
29. В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?
30. Граф, имеющий 5 вершин, каждая из которых соединена ребром с любой другой, не является плоским.
31. Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?
32. Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, -- не плоский.
33. Докажите, что в плоском графе есть вершина, степень которой не превосходит 5.
34. Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо "красный", либо "синий" граф не является плоским.
35. Семиугольник разбит на выпуклые пяти- и шестиугольники, причем так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13.