Аннотация:
Назовем лесом граф, у которого все связные компоненты — деревья.
Сколько нужно лесов, чтобы покрыть все ребра заданного графа? Это один
из глубоких вопросов теории графов, имеющий отношение к оценке
сложности алгоритмов. Очень быстро мы поймем, что ответ как будто
совсем простой и лежит на поверхности. Но вот неприятность: доказать,
что наш ответ правильный, — нерешенная проблема! В курсе мы изучим
несколько чрезвычайно красивых инструментов на стыке теории графов,
теории чисел и теории вероятностей, которые позволят нам приблизиться
к решению этой проблемы.
Обратная связь: