Введение в теорию графов
Тест направлен на проверку планируемых результатов на уроке "Введение в теорию графов".
Задание 1
На обед в школьной столовой предлагают первое блюдо - куриный суп и борщ, второе блюдо - плов, третье блюдо - компот из сухофруктов, сок. Какой граф соответствует данному условию?
Задание 2
В некотором графевершин, степени которых равны: Сколько в этом графе рёбер?
Задание 3
Антон решил пригласить друзей - одноклассников на день рождение. Известно, что Антон дружит с Ильёй и Николаем, Дмитрий дружит с Ильёй и Алексеем, Марина дружит с Жанной и Максимом, Яна дружит с Максимом. Может ли Антон пригласить Максима на день рождения?
Задание 4
Укажите эйлеровы графы.
Задание 5
Выполните классификацию графов. Сопоставьте условие с заключением.
Задание 6
Найдите сумму степеней всех вершин графа.
Задание 7
На рисунке указана схема дорог, связывающих городаПо каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из городав город
Задание 8
Количество столбов в городе равнонекоторые из них соединены кабелями, проводящими электричество. От каждого столба должно отходить покабелей. Сколько всего нужно кабелей?
Задание 9
В одной из вершин октаэдра сидит муха. Она может проползти по всем его рёбрам ровно по одному разу и возвратиться в исходную вершину. Укажите верные путь, по которому она может совершить данный маршрут.
Задание 10
Сформулируйте утверждения, подставив в прямоугольник слова по смыслу. Путём в графе от вершины А до вершины B назовём такую рёбер графа, в которой каждые соседних ребра имеют вершину. Длина пути - это рёбер в этом . Путь в графе, у которого вершины не повторяются, называется . Цикл в графе - это путь, у которого - в одной вершине, а рёбра и промежуточные вершины . Если существует путь, ведущий из одной вершины в другую, то эти вершины называются . Если в графе любые две вершины соединены, то такой граф называется . Граф, у которого каждая соединена с любой вершиной, называется . Чтобы найти количество рёбер в полном графе, у которого n вершин, нужно воспользоваться формулой:.
Задание 11
В таблице приведены расстояния между четырьмя посёлками. Если пересечение строки и столбца пусто, то между посёлками дороги нет. Постройте данный граф и с помощью него определите кратчайший путь из посёлкав.
Задание 12
Дан граф. Сопоставьте условие с заключением.