Решение задач по дискретной математике

Задание 1. (плоский граф). Построить плоский граф с помощью гамма-алгоритма Татта. Первоначальный цикл выбирается так, чтоб было как минимум два нетривиальных сегмента(нетривиальный сегмент - сегмент содержащий не менее одной вершины степени три или более; если вдруг с выбором цикла возникнут проблемы, надо обратиться ко мне).

С точки зрения оформления. Должна быть таблица сегментов и до-

ступности граней.

Часть, рисуемая на каждом шаге должна быть вы-

делена отдельным цветом в трех местах

- плоской укладке, исходном

графе и сегменте, из которого она рисуется. В ответе должно быть указано является ли граф плоским.

Задание 2. (максимальный поток и минимальный разрез). Найти максимальный поток и минимальный разрез в сети. Расстановки пометок надо внести в таблицу (по ней проверяется правильно ли их расставля-ли). Новые обратные ребра при каждом увеличении потока желательно красить отдельным цветом, это позволит отследить время их появле-ния. Подсчитать поток, затем выписать разрез(чтоб было понятно как он получен), найти его величину. В ответе должны быть величина потока и разрез. Требование -пометки в таблице должны быть расставлены правильно в соответствии с алгоритмом. В частности, при рассмотрении вершины должны появляться пометки на всех соседних вершинах, в которые можно увеличить поток. Не допускается, даже на начальных стадиях, выбор пути увеличения потока без использования алгоритма расстановки пометок