Тест по теме "Элементы теории графов"

Пояснительная записка

Дисциплина: Элементы высшей математики.

Курс: 2.

Тема: Элементы теории графов.

Цель: контроль знаний по теме; развитие навыков самоконтроля, взаимоконтроля.

Количество заданий: на дополнение текста – 1, с выбором ответа – 10, на установление соответствия – 2.

Время выполнения: 15-20 мин.

Теория графов

«Математики изучают не предметы, а только лишь отношения между ними»

А. Пуанкаре, французский математик (1854-1912)

Часть I. Вставьте в текст пропущенные слова, изменив, если нужно, их падеж.

Основные понятия теории графов.

Теория графов, как и любая другая математическая дисциплина, включает в себя необходимые понятия. … – это совокупность конечного числа точек, называемых … графа, и попарно соединяющих некоторые из них линий, называемых … графа. ... – это число ребер, которые выходят из данной вершины. … данного графа называется граф, состоящий из всех … и их концов, которые необходимо добавить к исходному графу, чтобы получить … граф. Многоугольник плоского графа, не содержащий внутри себя никаких … или ребер, называется …. Последовательность …, соединенных без повтора – это путь. … – это …, в котором совпадают начальная и конечная точка. Граф со стрелками называется …, а без стрелок – ….

Словарик: граф, ребра, вершины, степень вершины, дополнение, грань, путь, цикл, полный, ориентированный, неориентированный.

Часть II. Выберите один правильный ответ.

Теория графов является разделом:

элементарной математики
дискретной математики
математического анализа
экономического анализа

Родоначальником теории графов считается:

Эйлер
Кениг
Гамильтон
Берж

Математическая формализация понятия графа дана:

Эйлером
Кенигом
Гамильтоном
Бержем

Какой из графов нельзя начертить одним росчерком:

граф, все вершины которого четные
граф с одной нечетной вершиной
граф с двумя нечетными вершинами
граф с более, чем двумя нечетными вершинами

Эйлер доказал, что задача о семи кенигсбергских мостах:

имеет одно решение
имеет несколько решений
имеет бесконечно много решений
не имеет решений

Хроматическим числом графа называется:

число красок, необходимых для «правильной» раскраски графа
максимальное число красок, необходимых для «правильной» раскраски графа
минимальное число красок, необходимых для «правильной» раскраски графа

Число нечетных вершин графа:

всегда четно
всегда нечетно
может быть как четно, так и нечетно
равно нулю

Если полный граф имеет n вершин, то количество ребер будет равно:

n
n/2
n(n-1)/2
(n-1)/2

Какой элемент не отображается при построении дерева решений:

альтернативные решения
состояния среды
вероятности возможных исходов
направление движения

Матрица смежности представляет собой таблицу, у которой:

число строк равно числу вершин, а число столбцов – числу ребер графа
число строк и столбцов равно числу вершин графа
число столбцов равно числу вершин, а число строк – числу шагов работы алгоритма отыскания кратчайшего пути

Часть III. Установите соответствие между элементами столбцов.

1. Виды графов.

Граф	Характеристика
1. полный граф	А. каждая пара вершин соединена ребром
2. нулевой граф	Б. каждая пара вершин соединена хотя бы одним путем
3. связный граф	В. ребра графа имеют направление, изображаемое стрелками
4. плоский граф	Г. схема, состоящая из изолированных вершин
5. дерево	Д. связный граф, не содержащий циклов
6.Эйлеров граф	Е. связный граф, содержащий путь, по которому можно пройти все ребра по одному разу, выйдя из любой вершины и вернувшись в нее же
7. ориентированный граф	Ж. можно представить на плоскости в таком виде, при котором ребра пересекаются только в вершинах

2. Задачи принятия решений, связанные с оптимизацией на графах

Задача	Содержание	Примеры
I. Задача коммивояжера.	1. Кратчайшим путем попасть из одной вершины графа в другую.	А. Составить пакет акций, максимизирующий объем прибыли.
II. Задача о кратчайшем пути.	2. Определить максимальный объем, который можно доставить из одной вершины графа в другую.	Б. Составить наиболее выгодный маршрут доставки товаров по заданным торговым точкам.
III. Задача о максимальном потоке.	3. Посетить все вершины графа и вернуться в исходную точку, минимизировав затраты.	В. Найти маршрут, позволяющий с наименьшими затратами топлива и времени доставить товар из пункта А в пункт Б.