Комбинаторные алгоритмы

Курс состоит из двух семестров. В каждом семестре нужно решить три задачи, по одной из каждой темы. Темы первого семестра: Поиск в графе 1 – явное применение алгоритмов поиска в ширину и глубину для решения задачи. 2. Поиск в графе 2 – применения тех же алгоритмов для проверки различных свойств графов. 3. Пути в сетях – задачи на алгоритм Дейкстры, алгоритм Форда-Беллмана, нахождение кратчайшего пути в ациклическом графе. Темы второго семестра: Минимальный остов – применение алгоритма Ярника-Прима-Дейкстры и алгоритма Борувки-Краскала. 2. Максимальный поток и паросочетания – алгоритм Форда-Фалкерсона, алгоритм Куна. 3. Задачи на разные темы – построение графовой модели, применение различных алгоритмов, в том числе из предыдущих тем. Все задачи на курсе общедоступны, но для каждого студента формируется индивидуальный набор обязательных задач. Номер задачи в теме определяется следующим образом: \( N = (Q - 1) \mod M + 1 \) , где \( N \) – номер задачи в теме \( Q \) – номер студента в группе \( M \) – количество задач в теме Например, в теме 10 задач, тогда студент с номером 12 получает задачу с номером \( (12-1) \mod 10 + 1 = 2 \)$\lt math xmlns="http://www.w3.org/1998/Math/MathML"\gt<mo stretchy="false">(</mo><mn>12</mn><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo><mspace width="0.667em"></mspace><mi>mod</mi><mspace width="thinmathspace"></mspace><mspace width="thinmathspace"></mspace><mn>10</mn><mo>+</mo><mn>1</mn><mo>=</mo></math>$