Для решения поставленной задачи будем использовать метод ветвей и границ. Решением задачи является последовательность вершин графа. Пусть R - частичное решение задачи - последовательность длиной Len(R), start - номер вершины, с которой надо начинать строить цепочку, а MinWayLen - минимальная требуемая длина цепочки (максимальная длина из уже построенных цепочек). При выборе очередной вершины и вставки ее в конец последовательности R граф разбивается удалением этой вершины на компоненты связности (связные подграфы). Составим массив таких компонентов ( т.е. множеств вершин). Упорядочим компоненты по убыванию количества вершин. Дальнейший ход алгоритма описывается циклом: 1. Пусть i - первый (следующий) компонент связности. 2. Если Len(i)<=MinWayLen, то выйти из цикла; 3. Решаем задачу внутри i для каждой начальной вершины start из множества вершин i, смежных текущей вершине start; 4. повторять с 1, взяв вместо i следующый компонент. Для того чтобы рассмотреть все возможные длиннейшие пути, надо решать задачу для start = 1,2,...,N и выбрать среди N решений наидлиннейшее.