Методы оптимальных решений. Теория графов и ее экономические приложения. Транспортная задача. Задача поиска потока минимальной стоимости. Разрез в сети. Величина максимального потока в сети от источника к стоку. Величина потока в сети. Дерево. Матрица смежности. Матрица инцидентности. Ориентированный граф. Эйлеров граф
Решение задач и выполнение научно-исследовательских разработок: Отправьте запрос сейчас: irina@bodrenko.info
математика, IT, информатика, программирование, статистика, биостатистика, экономика, психология
Пришлите по e-mail: irina@bodrenko.info описание вашего задания, срок выполнения, стоимость
Контрольные
вопросы
к
лекции № 6 «Теория
графов и ее экономические приложения»
по
предмету
«Методы оптимальных решений»
1.
Конечный связный граф называется эйлеровым, если:
А) все его вершины четны;
Б) в нем существует простая цепь,
содержащая все вершины графа ровно один раз;
В) и А), и Б).
2.
Деревом называется:
А) связный граф, который не имеет циклов;
Б) граф, в котором каждая его вершина
соединена ребром с любой другой его вершиной;
В) не А) и не Б).
3.
Маршрут, соединяющий вершины графа, называется цепью, если:
А) каждое ребро графа встречается в нем не более одного раза;
Б) каждая вершина графа встречается в
нем не более одного раза;
В) и А), и Б).
4.
Граф называется связным, если:
А) любая пара его
вершин связана;
Б) множество его вершин X может быть
разделено на два непересекающихся подмножества Y и Z таким образом, что каждое ребро
графа соединяет вершины из двух разных подмножеств Y и Z;
В) и А), и Б).
5.
Матрица смежности неориентированного графа с
n вершинами и m ребрами является:
А) квадратной
матрицей порядка n;
Б) квадратной матрицей порядка m;
В) матрицей размера (n
x m).
6.
Матрица инцидентности ориентированного графа с n вершинами и m дугами является:
А)
квадратной матрицей порядка n;
Б) квадратной матрицей порядка m;
В) матрицей размера (n x m).
7.
Величина потока V в сети равна:
А) сумме значений потоков, выходящих из
источника s;
Б) сумме значений потоков, заходящих в
сток t;
В) и А), и Б).
8. Величина максимального потока в сети от источника к стоку равна:
А) величине минимального разреза, отделяющего источник от
стока;
Б) величине максимального разреза,
отделяющего источник от стока;
В) не А) и не Б).
9.
Разрез в сети представляет:
А) множество дуг, при удалении которых из сети,
полностью прекращается поток от источника к стоку;
Б) множество дуг, сумма
пропускных способностей которых минимальна;
В) не А), и не Б).
10.
Транспортная задача является частным случаем:
А) задачи поиска потока минимальной
стоимости;
Б) задачи о назначениях;
В) не А) и не Б).