КИМ для проведения тестирования базового уровня

Разрабатывается
2.2. Комплект контрольно-измерительных материалов к зачету по БДЗ модуля 2

Описание структуры варианта БДЗ и схема оценивания

Структура варианта БДЗ приведена в таблице 10.

Таблица 10
№	Описание задания
	Используя теорему Кирхгофа, найти число остовов в обыкновенном графе с пятью вершинами (граф задан списком вершин и ребер). Нарисовать диаграммы нескольких остовов.
	Найти базис циклов на графе (граф задан матрицей инцидентности).
	Найти эйлерову цепь (цикл) на графе (граф задан списком ребер) (цепь задать в виде последовательности номеров ребер).
	С помощью алгоритма Дейкстры найти расстояния от вершины ориентированного графа до остальных его вершин; указать кратчайший путь от вершины до вершины (граф задан списком дуг и весовым отображением).
	С помощью алгоритма Форда-Фалкерсона найти максимальный поток и минимальный разрез в сети (граф задан списком дуг и весовым отображением).
	Построить минимальную УБДР относительно порядка для функции , заданной формулой.

За каждое выполненное задание начисляется либо 1 балл (в случае правильного его выполнения), либо 0 баллов (при наличии ошибки). Число баллов за БДЗ вычисляется как сумма баллов, полученных за задачи.

Образец варианта БДЗ