Моделирование с помощью графов

Тест направлен на проверку планируемых результатов на уроке "Моделирование с помощью графов".

Задание 1

На рисунке указана схема дорог, связывающих городаПо каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из городав город

Задание 2

В таблице приведены расстояния между четырьмя посёлками. Если пересечение строки и столбца пусто, то между посёлками дороги нет. Постройте данный граф и с помощью него определите кратчайший путь из посёлкав.

Задание 3

На обед в школьной столовой предлагают первое блюдо - куриный суп и борщ, второе блюдо - плов, третье блюдо - компот из сухофруктов, сок. Какой граф соответствует данному условию?

Задание 4

Антон решил пригласить друзей - одноклассников на день рождение. Известно, что Антон дружит с Ильёй и Николаем, Дмитрий дружит с Ильёй и Алексеем, Марина дружит с Жанной и Максимом, Яна дружит с Максимом. Может ли Антон пригласить Максима на день рождения?

Задание 5

У Юры с Антоном вышел спор. Юра утверждает, что из проволоки длиной м нельзя сложить каркас куба при условии, что нельзя резать проволоку и делать рёбра разной толщины, а Антон говорит, что можно. Кто из ребят прав? Решите данную задачу, вставив в прямоугольники слова по смыслу. Каркас куба можно представить в виде графа. Данное условие говорит о том, что нельзя проволоку и делать рёбра разной . Данный граф нужно , не отрывая карандаша от бумаги, значит этот граф является . Эйлеров может иметь либо нечётные вершины, либо не иметь их . Но у графа на рисунке все вершин нечётные, значит, этот граф эйлеровым. А значит, куб из проволоки длиной м сложить не получится. Выходит, что прав .