Пояснительная записка
Дисциплина: Элементы высшей математики.
Курс: 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. Посетить все вершины графа и вернуться в исходную точку, минимизировав затраты. | В. Найти маршрут, позволяющий с наименьшими затратами топлива и времени доставить товар из пункта А в пункт Б. |
Тест в интерактивной форме:
Приложение 1: Викторина с выбором правильного ответа
Приложение 2: Заполнить пропуски
Приложение 3: Парочки "Виды графов"
