Графы, деревья и выигрышные стратегии — тест

В игре с полной информацией и конечным числом ходов выигрышная стратегия существует всегда — вопрос лишь в том, у кого именно и как её найти.

Что проверяется

Простейшие свойства графов: вершины и рёбра, степень вершины, связность, сумма степеней и число рёбер, ориентированные и взвешенные графы. Способы представления графа: матрица смежности, матрица инцидентности, списки рёбер и списки смежности, выбор представления по плотности графа. Алгоритмы обхода связного графа: обход в ширину и в глубину, порядок посещения вершин, поиск кратчайшего пути в невзвешенном графе. Мосты и точки сочленения: рёбра и вершины, удаление которых нарушает связность, их роль в задачах о надёжности сетей. Деревья: определение, число рёбер, единственность пути между вершинами, остовное дерево. Каркас минимального веса и жадный алгоритм его построения. Дерево игры: позиции и ходы, полный перебор вариантов. Построение выигрышной стратегии, выигрышные и проигрышные позиции, инвариант стратегии, игра как модель задачи управления.

Выигрышные и проигрышные позиции

Позиция выигрышная, если из неё есть ход в проигрышную для соперника. Разметив позиции от конца игры к началу, стратегию находят без перебора всех партий целиком.

Мост в сети

Мост — ребро, при удалении которого граф распадается. В компьютерной сети это канал без резервного пути: его обрыв отрезает часть узлов.

Как устроена работа

Одиннадцать заданий: выбор варианта, соответствие между понятием теории графов и его определением, восстановление пропусков, упорядочивание шагов построения каркаса минимального веса и подсчёты рёбер и степеней. Разбор к каждому заданию показывает ход рассуждения. Работа рассчитана примерно на двадцать пять минут, отметка выставляется по шкале пятьдесят, семьдесят и восемьдесят пять процентов. Отдельные вопросы посвящены обходу в ширину и разметке позиций игры.

Как и на чём выполнять тест

Тестирование одинаково удобно и на компьютере, и на смартфоне. Период выполнения задаётся гибко, поэтому работу проводят и в классе, и дома. От списывания помогает наблюдение за переходами в другие вкладки и приложения в ходе прохождения.