Графы

Задача №175 В задаче №174 (см. в тексте задачи №173) нам необходимо было «обойти» граф, изображенный на рисунке 1. Условия: проходить граф необходимо не отрывая карандаша от бумаги и не проводя по какому-либо ребру дважды. Один из возможных вариантов обхода изображен на рисунке 2: При, казалось бы, игровой направленности «обхода» графов, решение задач по «обходу» имеет и вполне прикладное значение. Например, мы ставили перед собой задачу обхода каждого ребра графа, опираясь на то, что всякий эйлеров граф (см...

Задача №173 Нам необходимо решить такую задачу (задача №173): не отрывая карандаша от бумаги и не проводя по какому-либо ребру дважды, нарисуйте граф, изображенный на рисунке (рис.1). Пронумеруйте ребра в той последовательности, в которой вы их проходили. При разборе задачи «о Кёнигсбергских мостах» (см. «Графы») Леонард Эйлер сформулировал следующие правила решения задач с «обходом графов»: В нашем графе есть вершины с четным количеством сходящихся «мостов» (ребер), а также есть вершины с нечетным количеством сходящихся «мостов» (ребер)...

Задача №172. Любители шахмат В качестве разминки после задачи №170 «Комната с коврами» была приведена задача №171 «Недружелюбные соседи». Задача очень простая. Ответом на неё может быть такой вариант: В4, А5, Б2, Г1, Д3. Может быть вариант с Б5 и А2. Для нас имеет значение не сам ответ, а способ, с помощью которого он найден – соединение отрезками различных исходных точек и конечных объектов. В задаче №171 исходные точки – дома, конечные объекты – колодцы, а тропинки – отрезки, с помощью которых соединяются наши исходные точки...

Задача №170 Решите следующую задачу: Пол помещения площадью 12 м² покрыт тремя коврами. Площадь первого ковра 5 м², второго – 4 м², третьего – 3 м².  Каждые два ковра перекрываются на площади 1,5 м², причем 0,5 м² из этих полутора квадратных метров приходится на участок пола, где перекрываются сразу все три ковра. Необходимо: Использовать для решения этой задачи мы будем способ, предложенный в XVIII веке Леонардо Эйлером[1], а впоследствии доработанный Джоном Венном[2]. Более подробно мы останавливались на этом при рассмотрении решения к задаче №166...