Олимпиадные задачи из источника «глава 5. Графы» - сложность 1-2 с решениями
глава 5. Графы
НазадНа консультации было 20 школьников и разбиралось 20 задач. Оказалось, что каждый из школьников решил две задачи и каждую задачу решили два школьника. Докажите, что можно так организовать разбор задач, чтобы каждый школьник рассказал одну из решённых им задач и все задачи были разобраны.
У Царя Гвидона было 5 сыновей. Среди его потомков 100 имели каждый ровно по 3 сына, а остальные умерли бездетными.
Сколько потомков было у царя Гвидона?
В стране <i>n</i> городов. Между каждыми двумя городами установлено воздушное сообщение одной из двух авиакомпаний. Докажите, из этих двух авиакомпаний хотя бы одна такова, что что из любого города можно попасть в любой другой рейсами только этой авиакомпании.
Доказать, что в двудольном плоском графе <i>E</i> ≥ 2<i>F</i>, если <i>E</i> ≥ 2 (<i>E</i> – число рёбер, <i>F</i> – число областей).
Доказать, что
а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;
б) в дереве с <i>n</i> вершинами ровно <i>n</i> – 1 ребро;
в) в дереве не меньше двух висячих вершин;
г) в связном графа из <i>n</i> вершин не меньше <i>n</i> – 1 ребра;
д) если в связном графе <i>n</i> вершин и <i>n</i> – 1 ребро, то он – дерево.
а) Из какого минимального числа кусков проволоки можно спаять каркас куба?
б) Какой максимальной длины кусок проволоки можно вырезать из этого каркаса? (Длина ребра куба равна 1 см.)
Доказать, что связный граф можно обойти, проходя по каждому ребру дважды.
Существует ли ломаная, пересекающая все рёбра картинки по одному разу? <div align="center"><img width="68" height="26" align="BOTTOM" border="0" src="/storage/problem-media/31093/problem_31093_img_2.gif"></div>
Можно ли начертить, не отрывая карандаша от бумаги (одним росчерком)
а) квадрат с диагоналями?
б) шестиугольник со всеми диагоналями?
В стране каждые два города соединены дорогой с односторонним движением.
Доказать, что существует город, из которого можно проехать в любой другой не более чем по двум дорогам.
Грани некоторого многогранника раскрашены в два цвета так, что соседние грани имеют разные цвета. Известно, что все грани, кроме одной, имеют число рёбер, кратное 3. Доказать, что и эта одна грань имеет кратное 3 число рёбер.
В классе больше 32, но меньше 40 человек. Каждый мальчик дружит с тремя девочками, а каждая девочка – с пятью мальчиками.
Сколько человек в классе?
Доказать, что число штатов США с нечётным числом соседей чётно.
В графе из каждой вершины выходит по три ребра. Может ли в нём быть 1990 рёбер?
Есть 20 карточек, у каждой из которых на двух сторонах написано по числу. При этом все числа от 1 до 20 написаны по два раза.
Доказать, что карточки можно разложить так, чтобы все числа сверху были различны.
В графе 100 вершин, причём степень каждой из них не меньше 50. Доказать, что граф связен.
В графе каждая вершина – синяя или зелёная. При этом каждая синяя вершина связана с пятью синими и десятью зелёными, а каждая зелёная – с девятью синими и шестью зелёными. Каких вершин больше – синих или зелёных?
Могут ли степени вершин в графе быть равны:
а) 8, 6, 5, 4, 4, 3, 2, 2?
б) 7, 7, 6, 5, 4, 2, 2, 1?
в) 6, 6, 6, 5, 5, 3, 2, 2?
На клетчатом листе закрасили 25 клеток. Может ли каждая из них иметь нечётное число закрашенных соседей?
Из полного 100-вершинного графа выкинули 98 рёбер. Доказать, что он остался связным.
В некоторой стране из столицы выходит 89 дорог, из города Дальний – одна дорога, из остальных 1988 городов – по 20 дорог.
Доказать, что из столицы можно проехать в Дальний.
В кружке у каждого члена имеется один друг и один враг. Доказать, что
а) число членов чётно.
б) кружок можно разделить на два нейтральных кружка.
Имеется 30 человек, некоторые из них знакомы. Доказать, что число человек, имеющих нечётное число знакомых, чётно.
Каждое из рёбер полного графа с 6 вершинами покрашено в один из двух цветов.
Докажите, что есть три вершины, все рёбра между которыми – одного цвета.
На плоскости дано 100 окружностей, составляющих связную (то есть не распадающуюся на части) фигуру.
Докажите, что эту фигуру можно нарисовать, не отрывая карандаша от бумаги и не проводя дважды одну и ту же линию.