Олимпиадные задачи из источника «глава 5. Графы» для 8 класса - сложность 2-4 с решениями
глава 5. Графы
НазадНа консультации было 20 школьников и разбиралось 20 задач. Оказалось, что каждый из школьников решил две задачи и каждую задачу решили два школьника. Докажите, что можно так организовать разбор задач, чтобы каждый школьник рассказал одну из решённых им задач и все задачи были разобраны.
У Царя Гвидона было 5 сыновей. Среди его потомков 100 имели каждый ровно по 3 сына, а остальные умерли бездетными.
Сколько потомков было у царя Гвидона?
Доказать, что в двудольном плоском графе <i>E</i> ≥ 2<i>F</i>, если <i>E</i> ≥ 2 (<i>E</i> – число рёбер, <i>F</i> – число областей).
а) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет треугольников?
б) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет полного подграфа из четырёх вершин?
Есть волейбольная сетка 5×10. Какое максимальное число веревок, её составляющих, можно разрезать так, чтобы она не распалась?
Доказать, что
а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;
б) в дереве с <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>
Можно ли начертить, не отрывая карандаша от бумаги (одним росчерком)
а) квадрат с диагоналями?
б) шестиугольник со всеми диагоналями?
В графе 20 вершин, степень каждой не меньше 10. Доказать, что в нём есть гамильтонов путь.
В стране каждые два города соединены дорогой с односторонним движением. Доказать, что можно проехать по всем городам, побывав в каждом по одному разу (то есть что в полном ориентированном графе есть <i>гамильтонов путь</i>).
В стране каждые два города соединены дорогой с односторонним движением.
Доказать, что существует город, из которого можно проехать в любой другой не более чем по двум дорогам.
Грани некоторого многогранника раскрашены в два цвета так, что соседние грани имеют разные цвета. Известно, что все грани, кроме одной, имеют число рёбер, кратное 3. Доказать, что и эта одна грань имеет кратное 3 число рёбер.
В ориентированном графе 101 вершина. У каждой вершины число входящих и число выходящих рёбер равно 40. Доказать, что из каждой вершины можно попасть в любую другую, пройдя не более чем по трём ребрам.
Доказать, что число штатов США с нечётным числом соседей чётно.
Есть 20 карточек, у каждой из которых на двух сторонах написано по числу. При этом все числа от 1 до 20 написаны по два раза.
Доказать, что карточки можно разложить так, чтобы все числа сверху были различны.
В графе 100 вершин, причём степень каждой из них не меньше 50. Доказать, что граф связен.
Из полного 100-вершинного графа выкинули 98 рёбер. Доказать, что он остался связным.
В некоторой стране из столицы выходит 89 дорог, из города Дальний – одна дорога, из остальных 1988 городов – по 20 дорог.
Доказать, что из столицы можно проехать в Дальний.
В кружке у каждого члена имеется один друг и один враг. Доказать, что
а) число членов чётно.
б) кружок можно разделить на два нейтральных кружка.
Каждое из рёбер полного графа с 18 вершинами покрашено в один из двух цветов.
Докажите, что есть четыре вершины, все рёбра между которыми – одного цвета.
Каждое из рёбер полного графа с 17 вершинами покрашено в один из трёх цветов. Докажите, что есть три вершины, все рёбра между которыми – одного цвета.
Каждое из рёбер полного графа с 6 вершинами покрашено в один из двух цветов.
Докажите, что есть три вершины, все рёбра между которыми – одного цвета.