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

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

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

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

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

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

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

	Используя теорему Кирхгофа, найти число остовов в обыкновенном графе с вершинами 1,2,3,4,5 и ребрами . Нарисовать диаграммы нескольких остовов.
	Найти базис циклов на графе, заданном матрицей инцидентности .
	Найти эйлерову цепь на графе с вершинами 1,2,3.4.5,6,7.8,9 и ребрами , , ,
	С помощью алгоритма Дейкстры найти расстояния от вершины 3 ориентированного графа до остальных его вершин; указать кратчайший путь от вершины 3 до вершины 9 (граф задан списком дуг и весовым отображением), если граф имеет вершины 1,2,3,4,5,6,7,8,9, дуги , , , а расстояние между вершинами определяется как сумма их номеров.
	С помощью алгоритма Форда-Фалкерсона найти максимальный поток и минимальный разрез в сети с вершинами 1,2,3,4,5,6,7,8,9 и дугами , , , если расстояние между вершинами определяется как сумма их номеров, вершина 1 является источником, а вершина 9 стоком.
	Построить минимальную УБДР относительно порядка для функции , заданной формулой .