Глава 3. РАЗБИЕНИЯ И РАССТОЯНИЯ НА ГРАФАХ
3.1. Введение
В данной главе рассматриваются два основных вопроса. Первый связан с разбиением ребер, дуг или вершин графа на множество определенного структурного типа. Например, знаменитая задача о семи кенигсбергсюих мостах состоит в разбиении ребер данного графа на наименьшее число (желательно 1) циклов или цепей. Второй вопрос связан с измерением расстояний на графах. Примером задачи такого типа служит определение длиннейшего или «критического» пути в сети ПЕРТ. В этом случае кратчайшее время выполнения проекта находится как наибольший по продолжительности путь, образованный из операций этой сети.
