
\section{Введение}
Уже в течение 40 лет наряду с классической задачей коммивояжёра
(TSP --- Travelling Salesman Problem) в работах многих авторов
рассматривается её естественное обобщение, каким является задача
об $m$ коммивояжёрах ($m$-PSP --- $m$-Peripatetic Salesman
Problem), где требуется найти $m$ гамильтоновых циклов, не имещих
общих рёбер, с минимальным (задача $m$-PSP-min) или максимальным
($m$-PSP-max) суммарным весом рёбер в полном взвешенном графе.

Впервые проблема $m$-PSP была упомянута Крарупом в \cite{Krarup},
и с тех пор исследовалась разными авторами в симметричном и
несимметричном (задача $m$-APSP) случаях,
для произвольной \cite{ABG_3_4,GZ_7_9}, метрической \cite{BGK_04,
AP_08,G_16} и евклидовой \cite{G_08, BG_10} весовых функций,
а также в специальных постановках, когда веса рёбер графа
принимают значения из заданного интервала или конечного числового
множества \cite{GGG,GZ_7_5,GZ_4_3,GiIv_12,GZ_7_9}. В статьях
\cite{GZ_7_5,GZ_4_3,Gord} был изучен вариант задачи, когда для
каждого гамильтонова цикла задана своя весовая функция, и были
разработаны приближённые алгоритмы для этого случая.

К числу наиболее значимых приложений можно отнести задачу о
выборе маршрутов обходчиков \cite{CC03}, когда для группы из
$m$ сторожей требуется найти систему замкнутых маршрутов без
общих участков, чтобы добиться наибольшего охвата охраняемой
территории. В работах Де Корта \cite{De_Kort2} приводятся
постановки задач из области сетевого дизайна, когда для повышения
надёжности сети требуется покрыть её узлы системой непересекающихся
цикловых соединений, а также приложения в области теории расписаний
с элементами маршрутизации, когда каждая работа должна выпоняться
на каждой машине дважды, однако недопустимо оба раза выполнять
работы в одном и том же порядке.

Все содержательные посатновки задачи $m$-PSP (как на минимум, так
и на максимум) являются NP-трудными, что вытекает из установленной
Де Кортом \cite{De_Kort,De_Kort1,De_Kort2} NP-полноты задачи о
существовании двух рёберно непересекающихся гамильтоновых циклов
в графе. В связи с этим основные направления исследований связаны
с выявлением полиномиально разрешимых случаев этих задач, разработкой
эвристических приближённых алгоритмов, вероятностных алгоритмов,
а также полиномиальных алгоритмов с гарантированными оценками
точности, асимптотически точных алгоритмов и полиномиальных
аппроксимационных схем.

Де Брей и Волегант \cite{De Brey_Vol} выделили некоторые полиномиально
разрешимые случаи задачи 2-PSP. Де Корт \cite{De_Kort,De_Kort1,De_Kort2}
указал верхние и нижние оценки для метода ветвей и границ в задаче 2-PSP.
Наибольшее количество результатов было получено в области построения
полиномиальных приближённых алгоритмов с гарантированными оценками
точности для задач $m$-PSP-min и $m$-PSP-max. Так для задачи 2-PSP-min
в метрическом случае Агеев и Пяткин \cite{AP_08}
разработали полиномиальный 2-приближённый алгоритм. Для симметричного
варианта задачи 2-PSP-max в \cite{ABG_3_4,GZ_7_9} были построены
полиномиальные алгоритмы с гарантированными оценкамии $3/4$ и $7/9$.
В \cite{GGG} было получено несколько полиномиальных приближённых
алгоритмов, включая алгоритм с оценкой точности $6/5$, для
специального случая задачи 2-PSP-min, когда веса рёбер графа принимают
значения 1 и 2 (задача 2-PSP(1,2)-min).
В работах \cite{GZ_7_5,GZ_4_3} задача 2-PSP(1,2)-min исследовалась
в случае, когда весовые функции двух гамильтоновых циклов различны.
Для этой версии задачи были разработаны полиномиальные алгоритмы
с оценками точности $7/5$ \cite{GZ_7_5} и $4/3$ \cite{GZ_4_3}.
Для метрического варианта задачи $m$-PSP-max (при произвольном $m$)
в \cite{G_16} был получен полиномиальный алгоритм с гарантированной
оценкой $5/6$, а для евклидовой задачи $m$-PSP-max в \cite{BG_10}
построен асимптотически точный полиномиальный алгоритм. Подробный
обзор полученных в указанном направлении результатов приводится в
\cite{TSP,Gimadi}. Отметим, что большинство этих результатов
относится к симметричному случаю задачи $m$-PSP.

%Возникновение новых задач маршрутизации, в частности, задач о
%распределении транспортных потоков в сетях, приводит к тому, что всё
%более актуальным становится изучение несимметричной задачи $m$-APSP.
%Заметим, что в случае $m\ge 2$ данная задача допускает две различные
%интерпретации, при одной из которых в гамильтоновых циклах
%допускаются встречные дуги (то есть дуга $(x,y)$ может принадлежать
%одному циклу, а дуга $(y,x)$ --- другому), а при другой интерпретации
%такие ситуации исключаются. Для приложений более актуален второй
%вариант задачи, однако разработка приближённых алгоритмов для этого
%случая сопряжена со значительными трудностями, так как малопригодными
%оказываются полиномиальные алгоритмы для нахождения подграфов
%экстремального веса с заданными степенями вершин. Ввиду этого
%обстоятельства практически все известные приближённые алгоритмы
%с гарантированными оценками точности для задачи $m$-APSP, включая
%алгоритм для 2-APSP-max из \cite{GZS_2/3} и алгоритм из настоящей
%статьи, разработаны для случая, когда гамильтоновы циклы могут иметь
%встречные дуги.

Изучение несимметричных постановок задач коммивояжёра и нескольких
коммивояжёров изначально оказалось слпряжено с гораздо большими
трудностями, чем исследование их симметричных аналогов. Достаточно
упомянуть, что среди известных приближённых алгоритмов для задачи
ATSP-max до сих пор одним лучших является алгоритм из \cite{KLSS},
имеющий априорную оценку точности $2/3$, в то время как для
симметричной задачи TSP-max ещё в 1984 г. Сердюковым \cite{Serd}
был разработан достаточно простой в применении полиномиальный
алгоритм с гарантированной оценкой $3/4$, а в последние годы для
этой задачи были предложены алгоритмы с оценками точности $25/33$
\cite{2533TSP}, $7/9$ \cite{PMM7/9} и $4/5$ \cite{DMPR4/5}.
Интересная особенность разработанного в \cite{KLSS}
$2/3$-приближённого алгоритма для задачи ATSP-max состоит в том,
что этот акгоритм не является чисто комбинаторным, а использует
идеи и методы, характерные для задач линейного программирования.
Разработанный в \cite{GZS_2/3} полиномиальный алгоритм для задачи
2-APSP-max также имеет оценку точности $2/3$, однако основывается
на чисто комбинаторных подходах. Предложенные в работе
\cite{GZS_2/3} методы были затем использованы авторами настоящей
статьи в \cite{GT_3/5} для разработки полиномиального
$3/5$-приближённого алгоритм для задачи 3-APSP-max.

Цель настоящей статьи состоит в том, чтобы, используя некоторые
процедуры из алгоритмов, описанных в \cite{GZS_2/3} и \cite{GT_3/5},
и дополняя их новыми процедурами преобразования частичных туров и
постронеия гамильтоновых циклов, получить для задачи $m$-APSP-max
с произвольным значением $m\ge 2$ полиномиальный приближённый
алгоритм, имеющий гарантированную оценку точности, не меньшую $3/5$,
и асимптотически стремящуюся к $2/3$ с ростом $m$. Нами будет
показано, что описанный ниже алгоритм $A_{2/3-\varepsilon}$
обладает такой оценкой точности, корректно работает при наличии
во входном графе не менее $45(m-1)$ вершин, и имеет оценку
временной сложности $O(mn^3)$. Следует отметить, что указанный
алгоритм, как и алгоритмы из \cite{GZS_2/3} и \cite{GT_3/5},
находит такое приближённое решение задачи $m$-APSP-max, при
котором различные гамильтоновы циклы не имеют общих дуг, однако
любые две встречные дуги $(X,Y)$ и $(Y,X)$ могут содержаться
в двух различных гамильтоновых циклах.

\section{Основные определения и обозначения}

Далее через $G=G(V,E,w)$ обозначается полный ориентированный
взвешенный $n$-вершинный граф, подаваемый на вход задачи
$m$-APSP-max, имеющий множество вершин $V$, множество дуг $E$
и неотрицательную весовую функцию дуг $w : E \rightarrow
\mathbb{R}^+$. Для каждого подграфа $G'$ в $G$ через $w(G')$
обозначается суммарный вес дуг в $G'$.

{\em Несимметричная задача об $m$ коммивояжёрах на максимум}
($m$-APSP-max) состоит в отыскании в орграфе $G$ набора из $m$
ориентированных гамильтоновых циклов $H_{1},\:H_{2},\ldots,:H_{m}$,
имеющих максимальный суммарный вес, и не содержащих общих дуг:
$$w(H_1)+w(H_2)+\ldots +w(H_m) \rightarrow \max.$$
При этом допускается, что если какой-то цикл $H_{i}$ содержит
дугу $(X,Y)$, то другой цикл $H_{j}$ может содержать встречную
дугу $(Y,X)$. Через $w^{*}$ обозначим вес оптимального решения
задачи $m$-APSP-max.

Для каждой вершины $v$ в орграфе $G$ (или в его подграфе $G'$)
будем использовать следующие обозначения:

$d^{+}(v)$ --- \textit{полустепень захода} $v$, то есть число
входящих в вершину $v$ дуг орграфа $G$ ($G'$);

$d^{-}(v)$ --- \textit{полустепень исхода} $v$, то есть число
исходящих из $v$ дуг орграфа $G$ ($G'$);

$d(v)=d^{+}(v)+d^{-}(v)$ --- \textit{степень вершины} $v$ в $G$
($G'$).

Будем называть подграф $G'$ орграфа $G$ $(k,k)$-\textit{регулярным},
если для каждой его вершины $v$ выполняется тождество $d^{+}(v)=
d^{-}(v)=k$. Через $G_{k,k}$ обозначим остовный $(k,k)$-регулярный
подграф максимального веса в $G$. Поскольку подграф в $G$,
образованный объединением $m$ гамильтоновых циклов из оптимального
решения задачи $m$-APSP-max, является $(m,m)$-регулярным, то
выполняется неравенство $w(G_{m,m})\ge w^*$.

Назовём {\em сдвоенным треугольником} (2,2)-регулярный орграф,
состоящий из трёх вершин $A,B,C$ и шести дуг $(A,B)$, $(B,A)$,
$(B,C)$, $(C,B)$, $(C,A)$, $(A,C)$ (то есть полный ориентированный
граф на трёх вершинах). {\em Ориентированным 2-фактором}
(или просто 2-{\em фактором}) в орграфе $G$ будем называть
любой его остовный (1,1)-регулярный подграф, то есть
набор вершинно непересекающихся ориентированных циклов,
покрывающих все вершины $G$. Под \textit{частичным туром}
(или просто {\em туром}) в орграфе $G$ (или в его подграфе $G'$)
будем понимать набор вершинно непересекающихся ориентированных
цепей, покрывающих все вершины орграфа. Любую цепь тура, состоящую
из одной вершинны, будем называть \textit{тривиальной} или
\textit{синглом}, а цепь, состоящую из более чем одной вершины,
--- \textit{нетривиальной}. Будем использовать обозначения $|T|$
и $p(T)$ для числа рёбер и числа цепей в частичном туре $T$,
соответственно. Из определения следует, что для любого частичного
тура $T$ в орграфе $G'$ выполняется равенство
%\setcounter{equation}
\begin{equation}\label{eq1}
    |T|+p(T)=|V(G')|.
\end{equation}
Ясно, что из любого ориентированного 2-фактора удалением некоторых
дуг можно получить частичный тур, а из любого частичного тура
можно получить ориентированный гамильтонова цикл, добавляя дуги
между концами цепей этого тура.

Для взвешенного орграфа $G=(V,E,w)$ определим его
\textit{двудольную модель} $D$ как (неориентированный)
взвешенный двудольный граф c долями $V$ и $V^{\prime}$, где
$V^{\prime}=\{ v' \, | \, v\in V \}$ --- множество дубликатов
вершин из $V$, и с множеством рёбер $E(D) = \{ XY^{\prime} \, |
\, (X,Y) \in E \}$, где вес ребра определяются формулой
$w(XY^{\prime})=w(X,Y)$. Из данного определения следует, что
$w(G)=w(D)$ и орграф $G$ является $(k,k)$-регулярным тогда
и только тогда, когда его двудольная модель $D$ является
$k$-регулярным графом.

\section{Используемые процедуры из предшествующих алгоритмов}

Как уже отмечалось, описанный далее алгоритм $A_{2/3-\varepsilon}$
основывается на некоторых процедурах из алгоритма $A_{3/5}$ для
задачи 3-APSP-max \cite{GT_3/5} и алгоритма $A_{2/3}$ для задачи
2-APSP-max, разработанного в \cite{GZS_2/3}.
%который имеет гарантирован\-ную оценку точности $2/3$ и кубическую
%оценку временной сложности.
Упомянутые процедуры позволяют отыскивать в орграфах специального
вида частичные туры достаточно большого суммарного веса, у которых
количество цепей ограничено снизу линейной функцией от числа вершин.
Так процедура $P_{2/3}$ из алгоритма $A_{2/3}$ за время $O(n^3)$
находит в $(2,2)$-регулярном $n$-вершинном взвешенном орграфе
$G_{2,2}$ частичные туры $T_{2/3}^{1}$ и $T_{2/3}^{2}$, суммарный
вес которых не меньше $\frac 23 w(G_{2,2})$, а количество цепей
в туре $T_{2/3}^{2}$ не меньше $n/5$. В нашем алгоритме
$A_{2/3-\varepsilon}$ помимо процедуры $P_{2/3}$ будет использоваться
основанная на ней процедура $P'_{2/3}$, описание которой приводится
в разделе 5. Основное отличие процедуры $P'_{2/3}$ от $P_{2/3}$
состоит в том, что оба построенных ею частичных тура имеют
ограничение снизу на число составляющих их цепей. При этом
суммарный вес туров также не меньше $\frac 23 w(G_{2,2})$.

Предложенная в алгоритме $A_{3/5}$ \cite{GT_3/5} процедура
$P_{3/5}$ позволяет найти во взвешенном $(3,3)$-регулярном
$n$-вершинном орграфе $G_{3,3}$ частичные туры $T_{3/5}^{1}$,
$T_{3/5}^{2}$ и $T_{3/5}^{3}$, суммарный вес которых не меньше
$\frac 35 w(G_{3,3})$. При этом тур $T_{3/5}^{2}$ состоит не менее
чем из $n/6$ цепей, а тур $T_{3/5}^{3}$ -- не менее чем из $n/4$
цепей. Время работы процедуры $P_{3/5}$ ограничено $O(n^3)$.

Ещё одна используемая нами процедура --- это разработанный
Габовым алгоритм \cite{Gabow} для отыскания во взвешенном
$n$-вершинном неориентированном графе $G$ подграфа максимального
веса с заданными степенями вершин $d_1,d_2,\ldots,d_n$. Время
работы алгоритма Габова ограничено $O(n^2\sum\limits_{i=1}^n d_i)$.
В нашем случае алгоритм Габова будет применяться для отыскания
$m$-регулярного подграфа максимального веса в двудольной
модели $D$ орграфа $G$. Данному подграфу соответствует
$(m,m)$-регулярный подграф максимального веса в орграфе $G$.
Ясно, что в этом случае время работы алгоритма Габова не
превосходит $O(mn^3)$.

Также нами будет использован алгоритм Хопкрофта и Карпа
\cite{Hopcroft}, позволяющий найти в двудольном графе
$H=(V_H,E_H)$ паросочетание наибольшей мощности за время
$O(|E_H||V_H|^{1/2})$. Применение этого алгоритма к двудольному
$m$-регулярному $2n$-вершинному графу позволяет найти в нём
совершенное паросочетание за время $O(mn^{3/2})$.

%Перейдем к подробному описанию алгоритма $A_{2/3-\varepsilon}$
%и формулировке оиновного результата.

\section{Описание алгоритма $A_{2/3-\varepsilon}$ и основной
результат работы}

Основным результатом статьи является следующая

\begin{theorem}
 Представленный ниже алгоритм
$A_{2/3-\varepsilon}$ находит в полном взвешенном
$n$-вершинном орграфе $G=G(V,E,w)$, где $n\ge 45(m-1)$,
набор из $m$ рёберно непересекающихся гамильтоновых циклов
$H_{1},H_{2},\ldots,$ $H_{m}$, суммарный вес которых составляет
не менее $\frac{2}{3}w^{*}$ при чётном $m$, и не менее
$\left(\frac{2}{3}-\frac{1}{5m}\right) w^{*}$ при нечётном $m$.
%где $w^{*}$ --- вес оптимального решения задачи $m$-APSP-max.
Трудоёмкость алгоритма $A_{2/3-\varepsilon}$ оценивается как
$O(mn^3)$.
\end{theorem}

%\smallskip
Доказательство этой теоремы составляет содержание следующих
трёх разделов статьи. Приведём формулировку алгоритма.

\medskip
{\em \large Алгоритм $A_{2/3-\varepsilon}$ для задачи $m$-APSP-max}
\nopagebreak

\medskip
{\bf Фаза 1.} Построим двудольную модель $D$ входного орграфа
$G=(V,E,w)$. При помощи алгоритма Габова~\cite{Gabow} за время
$O(mn^3)$ найдём в $D$ остовный $m$-регулярный подграф $D_m$
максимального веса. Выделим в $G$ соответствующий ему
$(m,m)$-регулярный подграф $G_{m,m}$ максимального веса.
Согласно сделанным выше замечаниям, имеем: $w(G_{m,m})\geq
w^{*}$.

\medskip
{\bf Фаза 2.} Разобьём множество дуг орграфа $G_{m,m}$ на $m$
ориентированных 2-факторов $F_1,F_2,\ldots,F_m$. Для этого
используем двудольную модель орграфа $G_{m,m}$, то есть
полученный на Фазе 1 алгоритма $m$-регулярный двудольный
граф $D_m$. Разобьём множество рёбер $D_m$ на $m$ совершенных
паросочетаний, для чего $m-1$ раз примененим алгоритм Хопкрофта
и Карпа \cite{Hopcroft}. При этом общее время работы составит
$O(m^{2}n^{3/2})$. В орграфе $G_{m,m}$ найденным паросочетаниям
соответствуют искомые рёберно непересекающиеся 2-факторы
$F_1,F_2,\ldots,F_m$.

Далее, в зависимости от чётности $m$, группируем 2-факторы
$F_1,F_2,\ldots,$ $F_m$ следующим образом:
\begin{itemize}
\item[--] если $m$ чётно, то каждую пару 2-факторов $F_{2i-1},
F_{2i}, $ $i=1,\ldots ,m/2$, объединяем в $(2,2)$-регулярный
орграф $G_{2,2}^{i}$;
\item[--] если $m$ нечётно, то три 2-фактора с наименьшим весом
объединяем в $(3,3)$-регулярный орграф $G_{3,3}$, а оставшиеся
$m-3$ 2-фактора группируем по два (произвольнным образом)
в $(2,2)$-регулярные орграфы $G_{2,2}^{i}$, где $i=1,\ldots,
(m-3)/2$.
\end{itemize}

\medskip
{\bf Фаза 3.}  Формируем в орграфе $G_{m,m}$ $m$ рёберно
непересекающихся частичных туров $T_{1},$ $T_{2},\ldots ,T_{m}$
со следующими свойствами:
$$p(T_{2})\geq \frac{n}{6}; \quad p(T_i)\geq \frac{n}{15}, \ \;
i=3,\ldots,m.$$
Для построения частичных туров применяем к выделенным на Фазе 2
регулярным орграфам $G_{2,2}^{i}$ и $G_{3,3}$ процедуры $P_{2/3}$,
$P^{\prime}_{2/3}$ и $P_{3/5}$ следующим образом:
\begin{itemize}
\item[--] Если $m$ чётно, то с помощью процедуры $P_{2/3}$
находим в орграфе $G_{2,2}^{1}$ частичные туры $T_{1}$ и $T_{2}$,
а в каждом из орграфов $G_{2,2}^{i}$, $i=2,\ldots ,m/2$, находим
пару частичных туров $T_{2i-1},T_{2i}$ с помощью процедуры
$P^{\prime}_{2/3}$, описанной в разделе 5. %В результате получаем
%набор из $m$ рёберно непересекающихся частичных туров $T_{1},T_{2},
%\ldots ,T_{m}$. %обладающие нужными свойствами.
\item[--] Если $m$ нечётно, то, применяя к $(3,3)$-регулярному
орграфу $G_{3,3}$ процедуру $P_{3/5}$, находим частичные туры
$T_{1}$, $T_{2}$, $T_{3}$, а для всех $(2,2)$-регулярных
орграфов $G_{2,2}^{i}$, $i=1,\ldots ,(m-3)/2$, применяем
процедуру $P^{\prime}_{2/3}$. В результате получаем
набор из $m$ рёберно непересекающихся частичных туров
$T_{1},T_{2},\ldots,T_{m}$.
%обладающие необходимыми свойствами.
\end{itemize}

\medskip
{\bf Фаза 4.} Достраиваем полученные на Фазы 3 частичные туры
$T_{1},T_{2},\ldots,$ $T_{m}$ до рёберно непресекающихся
гамильтоновых циклов $H_{1},H_{2},\ldots ,H_{m}$,
применяя процедуру ``Замыкание($T_1$--$T_m$)'', описанную
в разделе 6. Предъявляем набор гамильтоновых циклов
$H_{1},H_{2},\ldots ,H_{m}$ в качестве искомого
при\-бли\-жен\-но\-го решения задачи $m$-APSP-max.

\section{Модифицированная процедура построения двух
частичных туров}

В этом разделе описывается процедура $P'_{2/3}$ и
дополняющая её процедура ``Выравнивание($T'_1$--$T'_3$)''.
Обе эти процедуры основаны на процедуре $P_{2/3}$ из
\cite{GZS_2/3}, работу которой мы сейчас рассмотрим
более подробно.

Процедура $P_{2/3}$ получает на вход взвешенный
(2.2)-регулярный орграф $G_{2,2}$ и находит в каждой его
компоненте связности $K^i$ пару рёберно непересекающихся
частичных туров $T_{1}(i)$, $T_{2}(i)$. После этого
процедура объединяет туры, построенные в разных компонентах
связности, и подаёт на выход полученные два частичных
тура $T_1=\bigcup\limits_{i=1}^l T_1(i)$ и
$T_2=\bigcup\limits_{i=1}^l T_2(i)$, где $l$ --- число
компонент связности орграфа $G_{2,2}$.  .

Построение частичных туров происходит по-разному в
компонентах связности $G_{2,2}$. Каждая компонента $K^i$
относится к одному из трёх типов:
\begin{enumerate}
\item $K^i$ не содержит встречных дуг (циклов длины 2);
\item $K^i$ содержит цикл длины 2, но не является сдвоенным
треугольником;
\item $K^i$ является сдвоенным треугольником.
\end{enumerate}

Для каждой компоненты $K^i$ типа 1 или 3 процедура
$P_{2/3}$ находит в $K^i$ пару частичных туров $T_{1}(i)$,
$T_{2}(i)$ с суммарным весом дуг не менее $\frac 23 w(K^i)$
и количеством цепей в каждом туре не менее $n_i/5$, где
$n_i$ --- число вершин в $K^i$. Если же компонента связности
$K^i$ относится к типу 2, то процедура $P_{2/3}$
сначала разбивает множество дуг $K^i$ на три частичных тура
$T'_{1},T'_{2},T'_{3}$ с помощью вспомогательной процедуры
``Ациклическая 3-раскраска($K$)'', затем специальным образом
преобразует эти туры, обеспечивая выполнение неравенства
$p(T_{2}^{\prime})\ge p(T_{1}^{\prime}) \ge n_i/5$, и,
наконец, выбирает в качестве $T_{1}(i)$, $T_{2}(i)$ два из
туров $T'_{1},T'_{2},T'_{3}$, имеющие наибольший вес.
В этом случае также выполняется оценка $w(T_{1}(i))
+w(T_{2}(i)) \ge \frac 23 w(K^i)$, однако только один
из полученных туров имеет гарантированную оценку снизу
на число составляющих его цепей.

Этого оказывается достаточно для того, чтобы обеспечить
возможность соединения двух частичных туров в
непересекающиеся гамильтоновы циклы, но недостаточно
для последовательного построения $m$ рёберно
непересекающихся гамильтоновых циклов в алгоритме
$A_{2/3-\varepsilon}$. Поэтому мы вынуждены модифицировать
процедуру $P_{2/3}$ таким образом, чтобы оба построенных ею
частичных тура имели ограничение снизу на число составляющих
их цепей. Для этого в случае, когда хотя бы один из трёх
полученных процедурой ``Ациклическая 3-раскраска($K$)''
частичных туров содержит недостаточное количество цепей
(менее $\frac{n_i}{15}$), мы будем увеличивать их число,
перенося часть рёбер из этого тура в другой, содержащий
большее количество цепей. Для этого будем применять
процедуру ``Выравнивание($T'_1$--$T'_3$)''.

%Перейдем к описанию процедур $P'_{2/3}$ и
%``Выравнивание($T'_1$--$T'_3$)''.

\medskip
\textbf{Процедура $P'_{2/3}$.}

На вход подаётся (2,2)-регулярный орграф $G_{2,2}$.
Выделяем в $G_{2,2}$ все компоненты связности:
$K^1,K^2,\ldots,K^l$.

Для каждого $i=1,2,\ldots ,l$ находим в $K^i$ два
рёберно непересекающихся частичных тура
$T_{1}(i)$, $T_{2}(i)$ со следующими свойствами:
$$w(T_{1}(i))+w(T_{2}(i))\geq\frac{2}{3}w(K^i); \quad
p(T_{j}(i))\geq \frac{n_i}{15},\;\; j=1,2.$$
%где $n_i$ --- число вершин компоненты $K^i$.
Для этого к каждой компоненте $K^i$, $i=1,2,\ldots ,l$,
применяем процедуру $P_{2/3}$. При этом если $K^i$
относится к типу 2, то к построенным процедурой
``Ациклическая 3-раскраска($K^i$)'' частичным турам
$T'_{1},T'_{2},T'_{3}$ дополнительно применяем
процедуру ``Выравнивание($T'_1$--$T'_3$)''.

После того как частичные туры $T_{1}(i),T_{2}(i)$
во всех компонентах связности орграфа $G_{2,2}$
построены, определяем рёберно непересекающиеся
частичные туры $T_1,T_2$ в $G_{2,2}$, полагая
$T_j=\bigcup\limits_{i=1}^l T_j(i)$, $j=1,2$.
При этом выполняются неравенства $w(T_{1})+w(T_{2})
\ge \frac{2}{3}w(G_{2,2})\,$ и $p(T_{j})\geq
\frac{n}{15},\; j=1,2$. Подаём туры $T_1$ и $T_2$
на выход процедуры $P'_{2/3}$.

\medskip
Далее опишем процедуру ``Выравнивание($T'_1$--$T'_3$)''.
Эта процедура получает на входе три частичных тура
$T_{1}^{\prime},T_{2}^{\prime},T_{3}^{\prime}$,
построенные в компоненте связности $K$ типа 2
процедурой ``Ациклическая 3-раскраска($K$)''.
Указанные туры образуют разбиение множества дуг
$K$. Упорядочим туры по неубыванию числа цепей:
\[
p(T_{1}^{\prime})\leq p(T_{2}^{\prime})\leq
p(T_{3}^{\prime}).
\]
Предполагается, что если после какого-то
преобразования частичных туров в ходе работы процедуры
``Выравнивание($T'_1$--$T'_3$)'' это неравенство
нарушается, то процедура переобозначает туры таким
образом, чтобы неравенство выполнялось. Цель
процедуры состоит в том, чтобы обеспечить выполнение
условия:
\[
\frac{n}{15}\leq p(T_{1}^{\prime})\leq p(T_{2}^{\prime})
\leq p(T_{3}^{\prime}),
\]
где $n$ --- число вершин в $K$.

При описании процедуры ``Выравнивание($T'_1$--$T'_3$)''
нами будут использоваться следующие понятия. Пусть $T$
--- частичный тур в компоненте связности $K$. Назовём
дугу $e\in E(K)\setminus E(T)$ {\em хорошей} для тура
$T$, если при её добавлении к $T$ получается
частичный тур, и {\em плохой} иначе.

\begin{lemma}
Число плохих дуг для тура $T$ в $K$ не превосходит $3|T|$.
\end{lemma}

%\smallskip
{\sc Доказательство.} Дуга является плохой для тура
$T$, если она имеет общую начальную, либо конечную,
вершину с какой-то дугой из $T$, либо если она ведет
из конца какой-то нетривильной цепи тура $T$ в начало
этой цепи (назовём такие дуги {\em цикловыми} для
$T$). Так как компонента $K$ является (2,2)-регулярным
орграфом, то каждая дуга тура $T$ смежна с двумя
нецикловыми плохими дугами в $K$, а число цикловых
плохих дуг не превосходит числа нетривиальных цепей
в $T$, которое, в свою очередь, не превосходит числа
дуг тура $T$. Отсюда следует, что число всех плохих
дуг не превосходит $2|T|+|T|=3|T|$. \, Лемма 1 доказана.

\medskip
Перенос хорошей дуги из тура $T'_i$ в тур $T'_j$
или более сложный обмен рёбрами между турами назовём
{\em улучшающим преобразованием} для набора частичных
туров $T_{1}^{\prime},T_{2}^{\prime},T_{3}^{\prime}$,
если после выполнения преобразования параметры
$p(T'_1)$ и $p(T'_1)-p(T'_3)$ не уменьшаются, и хотя
бы один из них строго увеличивается (тем самым
происходит выравнивание числа цепей в турах).
В частности, перенос хорошей дуги из $T'_i$ в $T'_j$
является улучшающим преобразованием, если до переноса
выполняется неравенство $p(T'_j)-p(T'_i) > 1$. В этом
случае после переноса либо параметр $p(T'_1)$
увеличивается на 1, либо $p(T'_3)$ уменьшается на 1.

Будем считать, что тур $T_{i}^{\prime}$ состоит из
дуг цвета $i$ в процедуре ``Ациклическая 3-раскраска($K$)''.
Также можно считать, что $n>15$, иначе неравенства
$p(T_{i}^{\prime})\geq \frac{n}{15}$, $i=1,2,3$,
заведомо выполняются. Назовём вершину $v$ компоненты
$K$ \textit{регулярной}, если для неё имеются
входящая и исходящая дуги цвета 1 (то есть $v$
является внутренней вершиной некоторой цепи тура
$T_{1}^{\prime}$), и \textit{нерегулярной} в
противном случае.

\begin{lemma}
Если %выполняется неравенство
$p(T_{1}^{\prime})<\frac{n}{15}$, то в туре
$T_{1}^{\prime}$ найдётся дуга, оба конца которой
регулярны и соединены рёбрами из $T_{2}^{\prime}
\cup T_{3}^{\prime}$ только с регулярными вершинами
(направления этих рёбер не имеют значения).
\end{lemma}

%\smallskip
{\sc Доказательство.} Предположим противное: для
каждой дуги из $T_{1}^{\prime}$, оба конца которой
регулярны, хотя бы один из концов этой дуги соединён
ребром из $T_{2}^{\prime}\cup T_{3}^{\prime}$ с
нерегулярной вершиной. Оценим с двух сторон
количество $e_{\text{р-н}}$ таких рёбер из
$T_{2}^{\prime}\cup T_{3}^{\prime}$, которые
соединяют регулярную вершину с нерегулярной.
Поскольку нерегулярными
вершинами в $K$ являются только начала и концы
цепей из $T_{1}^{\prime}$, то число всех
регулярных вершин $n_{\text{рег}} \ge
n-2p(T_{1}^{\prime})$. Если цепь тура
$T_{1}^{\prime}$ содержит $r$ регулярных вершин,
то по предположению из них исходит не менее
$\frac{r-1}{2}$ рёбер в нерегулярные вершины.
Следовательно, $e_{\text{р-н}}\geq
\frac{n_{\text{рег}}-p(T_{1}^{\prime})}{2}\geq
\frac{n-3p(T_{1}^{\prime})}{2}$.

С другой стороны параметр $e_{\text{р-н}}$ не
превосходит числа таких концов рёбер из
$T_{2}^{\prime} \cup T_{3}^{\prime}$, которые
входят в нерегулярные вершины. Общее количество
концов рёбер из $T_{2}^{\prime}\cup
T_{3}^{\prime}$ равно $2(|T_{2}^{\prime}|+
|T_{3}^{\prime}|)=2(2n-|T_{1}^{\prime}|)=
2(n+p(T_{1}^{\prime}))$, из них ровно
$2n_{\text{рег}}$ входят в регулярные вершины.
Поэтому
$e_{\text{р-н}}\leq 2(n+p(T_{1}^{\prime}))-
2n_{\text{рег}}\leq 2(n+p(T_{1}^{\prime}))-
2(n-2p(T_{1}^{\prime}))=6p(T_{1}^{\prime})$.
Таким образом, $\frac{n-3p(T_{1}^{\prime})}{2}
\leq e_{\text{р-н}} \leq 6p(T_{1}^{\prime})$.
Отсюда получаем, что $p(T_{1}^{\prime})\geq
\frac{n}{15}$. Противоречие. \, Лемма 2 доказана.

\medskip
\textbf{Выравнивание($T'_1$--$T'_3$).}

Если $p(T_{1}^{\prime}) \ge \frac{n}{15}$, то сразу
подаём на выход процедуры набор частичных туров
$T_{1}^{\prime},T_{2}^{\prime},T_{3}^{\prime}$.
Пусть $p(T_{1}^{\prime}) < \frac{n}{15}$. Пока это
неравенство выполняется, будем осуществлять
улучшающие преобразования частичных туров.
%улучшающий перенос дуги из одного из туров
%$T_{1}^{\prime},T_{2}^{\prime}$ в один из туров
%$T_{2}^{\prime},T_{3}^{\prime}$.
При $p(T_{3}^{\prime})>\frac{9n}{16}$ переходим
на Этап 1, иначе --- на Этап 2.

\smallskip
\textbf{\textit{Этап 1.}} Пока $p(T_{3}^{\prime})>
\frac{9n}{16}$, будем выполнять улучшающий перенос
дуги из одного из туров $T_{1}^{\prime},
T_{2}^{\prime}$ в тур $T_{3}^{\prime}$.
При этом если в какой-то момент окажется,
что $p(T_{1}^{\prime}) \ge \frac{n}{15}$,
то процедура завершает работу. Иначе она
достигает выполнения неравенства $p(T_{3}^{\prime})
\le \frac{9n}{16}$ и переходит на Этап 2.

Покажем, что указанный перенос дуги возможен.
Согласно лемме 1 в турах $T_{1}^{\prime}$ и
$T_{2}^{\prime}$ имеется не более $3|T'_3|$
плохих дуг для тура $T'_3$. Из неравенства
$p(T_{3}^{\prime})>\frac{9n}{16}$, следует, что
$|T'_3| < n-\frac{9n}{16} = \frac{7n}{16}$ и
$3|T'_3| < \frac{21n}{16}$. В то же время имеем
$|T_{1}^{\prime}|+|T_{2}^{\prime}| = 2n-
|T_{3}^{\prime}| > 2n - \frac{7n}{16} =
\frac{25n}{16} > 3|T'_3|$. Это гарантирует наличие
хорошей дуги для тура $T_{3}^{\prime}$ в $T_{1}^{\prime}
\cup T_{2}^{\prime}$. Поскольку $p(T_{1}^{\prime})+
p(T_{2}^{\prime})+p(T_{3}^{\prime}) = (n-|T'_1|)+
(n-|T'_2|)+(n-|T'_3|) = 3n-2n = n$ и
$p(T_{1}^{\prime})\ge 1$, то $p(T_{2}^{\prime})<
\frac{7n}{16}-1$. Из неравенства $p(T_{3}^{\prime})
- p(T_{2}^{\prime}) > \frac{9n}{16} - \frac {7n}{16}
+ 1 = \frac{2n}{16}+1$ следует, что перенос хорошей
дуги в тур $T_{3}^{\prime}$ является улучшающим
преобразованием для набора частичных туров
$T_{1}^{\prime},T_{2}^{\prime},T_{3}^{\prime}$.

\smallskip
\textbf{\textit{Этап 2.}} Пока $p(T_{1}^{\prime})
<\frac{n}{15}$ и $p(T_{3}^{\prime}) \le
\frac{9n}{16}$, будем выполнять описанную ниже
перекраску дуг (обмен рёбер между турами),
увеличивая параметр $p(T_{1}^{\prime})$.
Согласно лемме 2 в туре $T_{1}^{\prime}$ найдётся
дуга $(A,B)$, оба конца которой регулярны
и соединены рёбрами из $T_{2}^{\prime}\cup
T_{3}^{\prime}$ только с регулярными вершинами
(см. рис.~1).

\begin{center}
\includegraphics[scale=0.8]{Fig1.eps}
\\*{\large Рис.~1.}
\end{center}

Для того, чтобы увеличить количество цепей в туре
$T_{1}^{\prime}$, перекрасим некоторые дуги %$(A,B)\in T_{1}^{\prime}$
так, чтобы хотя бы одна дуга цвета 1 окрасилась
цветом 2 или 3. Сначала предположим, что дуги
$(A,D)$ и $(E,B)$ на рис. 1 окрашены в один
цвет, например, в цвет 2. Перекрасим дугу $(A,B)$
в цвет 3. Этому может помешать только возникновение
одноцветного цикла $(A,B,F,\ldots,C,A)$, все дуги
которого окрашены цветом 3. В последнем случае
дополнительно перекрасим дугу $(B,F)$ в цвет 2.
Такое преобразование осуществимо всегда, за исключением
случая, когда $F=A$ и перекраска дуги $(B,A)$ в цвет
2 приводит к образованию одноцветного цикла $(B,A,D,
\ldots,E,B)$ цвета 2. Если $D\neq E$, то окрасим
дуги $(E,B)$, $(B,A)$ и $(A,D)$ цветом 3, а дугу
$(A,B)$ --- цветом 2.

Пусть $D=E$. Рассмотрим дуги $(X,A)$ и $(B,Y)$
цвета 1. Поскольку $X\neq Y$, то вершина $D$
отлична хотя бы от одной из вершин $X$ или $Y$.
Предположим, что $D\neq X$. Если из вершины $X$
не исходит дуга цвета 2, то, оставляем цвета дуг
 $(A,B)$, $(B,A)$, $(A,D)$ и $(D,B)$ исходными,
а дугу $(X,A)$ перекрашиваем в цвет 2.
Если из $X$ исходит дуга цвета 2, то из неё не
исходит дуга цвета 3. В этом случае перекрасим
дуги $(X,A)$ и $(A,D)$ в цвет 3, а дугу $(B,A)$
--- в 2. Пусть $D=X$. Тогда $D\neq Y$. Теперь
осуществляем аналогичную перекраску с участием
дуги $(B,Y)$: если в вершину $Y$ не входит дуга
цвета 2, то перекрасим $(B,Y)$ в 2, а если в $Y$
не входит дуга цвета 3, то перекрасим $(B,Y)$
и $(D,B)$ в 3, а $(B,A)$ --- в 2.

Теперь рассмотрим случай, когда дуги $(A,D)$ и
$(E,B)$ окрашены в разные цвета: $(A,D)$ ---
в цвет 2, а $(E,B)$ --- в цвет 3. Перекрасим
дугу $(E,B)$ в цвет 2. %а $(A,B)$ --- в 3.
Если при этом образуется цикл $(B,F,\ldots,E,B)$
цвета 2, то дополнительно перекрасим дугу
$(B,F)$ в цвет 3. Далее действуем как в
предыдущем случае (цвета дуг $(A,D)$ и $(E,B)$
теперь совпадают).

Покажем, что описанный обмен дугами между
турами, при котором какая-то дуга тура
$T_{1}^{\prime}$ переносится в $T_{2}^{\prime}$
или $T_{3}^{\prime}$, является улучшающим
преобразованием. Заметим, что при любом
варианте такого обмена из тура $T_{1}^{\prime}$
удаляется ровно одна дуга, а в каком-то из
туров $T_{2}^{\prime}$ или $T_{3}^{\prime}$
становится на одну дугу больше, либо в одном
из этих туров становится на две дуги больше,
а в другом --- на одну меньше. Отсюда следует,
что параметр $p(T_{3}^{\prime})$ либо не
увеличивается, либо возрастает на 1.
Остаётся показать, что $p(T_{1}^{\prime})$
увеличивается на 1. Для этого требуется
проверить, что до выполнения обмена выполняется
неравенство $p(T'_2)-p(T'_1) > 2$
(поскольку в процессе обмена число цепей в
каком-то из туров $T'_2$ или $T'_3$ может
уменьшиться на 2). Из неравенств
$p(T_{1}^{\prime})<\frac{n}{15}$ и
$p(T_{3}^{\prime})\leq\frac{9n}{16}$ следует, что
$p(T'_2) > n - \frac{n}{15} - \frac{9n}{16}$.
Поэтому выполняется неравенство $p(T'_2)-p(T'_1)
> \frac{7n}{16} - \frac{2n}{15}=\frac{73n}{15
\cdot 16} > 2$, так как $n>15$.

Если после обмена между турами начинает
выполняться неравенство $p(T_{1}^{\prime})
\ge \frac{n}{15}$, то процедура завершает
работу. В противном случае если
$p(T_{3}^{\prime}) \le \frac{9n}{16}$, то
совершается новое улучшающее преобразование
на Этапе 2. Если же в результате обмена
параметр $p(T_{3}^{\prime})$
увеличивается на 1 и становится больше
$\frac{9n}{16}$, то производится один
улучшающий перенос дуги из Этапа 1, после чего
процедура возвращается на Этап 2.

\medskip
Таким образом, после завершения работы процедуры
``Выравнивание ($T'_1$--$T'_3$)'' туры
$T_{1}^{\prime},$ $T_{2}^{\prime}$ и
$T_{3}^{\prime}$ в $K$ преобразуются в три
частичных тура, каждый из которых содержит
не менее $n/15$ цепей. Следовательно, для
каждой компоненты связности $K^i$ орграфа
$G_{2,2}$ оба построенных в ней процедурой
$P'_{2/3}$ частичных тура $T_{1}(i)$, $T_{2}(i)$
состоят не менее чем из $n_i/15$ цепей. Поэтому
выполненяются неравенства $p(T_{j})\geq
\frac{n}{15},\; j=1,2$.

\medskip
Трудоемкость процедуры
``Выравнивание($T'_1$--$T'_3$)'' составляет
$O(n^{2})$, так как совершается не более $O(n)$
улучшающих преобразований, на поиск и выполнение
каждого из которых затрачивается время $O(n)$.
Следовательно, трудоемкость процедуры
$P_{2/3}^{\prime}$ определяется временем работы
процедуры $P_{2/3}$  и оценивается как $O(n^{3})$.

\section{Замыкание частичных туров в гамильтоновы циклы}

В этом разделе представлена финальная процедура алгоритма
$A_{2/3-\varepsilon}$, которая получает на входе набор
рёберно непересекающихся частичных туров $T_{1},T_{2},
\ldots,T_{m}$, построенных на Фазе 3 алгоритма.
Независимо от чётности $m$, для туров $T_{2},$ $T_{3},
\ldots,$ $T_{m}$ выполняются оценки:
\[
p(T_{2})\geq \frac{n}{6}; \quad
p(T_{i})\geq \frac{n}{15}, \ \; i=3,4,\ldots, m.
\]
Учитывая, что $n\geq 45(m-1)$, справедливы неравенства:
\[
p(T_{2})\geq 4; \quad
p(T_{i})\geq 3(m-1), \ \; i=3,4,\ldots, m.
\]

Описанная ниже процедура ``Замыкание($T_1$--$T_m$)''
дополняет частичные туры $T_{1},T_{2},\ldots ,T_{m}$
до рёберно непересекающихся гамильтоновых циклов
$H_{1},H_{2},\ldots ,H_{m}$ в оргафе $G$. При этом
выполняется неравенство
$$w(H_1)+w(H_2)+\ldots  +w(H_m) \ge w(T_1)+w(T_2)+\ldots
+w(T_m).$$

\medskip
\textbf{Замыкание($T_1$--$T_m$).}

Формируем гамильтоновы циклы по порядку, начиная с $H_{1}$.
Для замыкания тура $T_{1}$ в цикл $H_{1}$ используем
любые дуги исходного графа $G$, соединяющие цепи тура
$T_{1}$ в циклическом порядке. Если какая-то дуга
принадлежит другому частичному туру $T_{i}$, то
перебрасываем её в цикл $H_{1}$. При этом число цепей
в туре $T_i$ увеличивается, что только облегчает
его последующее замыкание.
%В результате получаем гамильтонов цикл $H_{1}$.

Далее с помощью процедуры, разработанной в \cite{GZS_2/3},
за время $O(n)$ дополняем тур $T_{2}$ до гамильтонова
цикла $H_2$, не имеющего общих дуг с уже построенным
циклом $H_{1}$. Как показано в \cite{GZS_2/3}, такое
преобразование осуществимо, если тур $T_{2}$ содержит
не менее четырёх цепей.

Пусть $3\leq k \leq m$. Далее описывается процедура
замыкания частичного тура $T_{k}$ в гамильтонов цикл
$H_{k}$ при условии, что $k-1$ гамильтоновых циклов
$H_{1},$ $H_{2},\ldots ,$ $H_{k-1}$ уже построены.

Из приведённых выше неравенств следует, что частичный
тур $T_{k}$ содержит не менее $3(m-1)$ цепей. Будем
называть дуги гамильтоновых циклов $H_{1},$ $H_{2},
\ldots,$ $H_{k-1}$ {\em запрещёнными} при построении
цикла $H_k$, а все остальные дуги орграфа $G$ ---
{\em допустимыми}. Заметим, что для каждой начальной
вершины цепи тура $T_{k}$ имеется $k-1$ входящих
запрещённых дуг, а для каждой концевой вершины имеется
$k-1$ исходящих запрещённых дуг. Будем соединять цепи
тура $T_{k}$ допустимыми дугами, пока количество цепей
не станет равным $3(k-1)$. Это можно сделать, так как
при большем количестве цепей из концевой вершины
каждой цепи исходит не менее $3(k-1)$ дуг в начальные
вершины других цепей, причём не более чем $k-1$ из
этих дуг могут быть запрещёнными. Пусть полученный
частичный тур состоит из цепей $P_{1},$ $P_{2},\ldots,$
$P_{3k-4},$ $P_{3k-3}$, где $P_{i}=(s_{i},\ldots,t_{i})$
при $i=1, 2,\ldots , 3k-3$.

Докажем, что все цепи удастся соединить в одну цепь,
не имеющую общих дуг с уже построенными гамильтоновыми
циклами. Заметим, что если несколько цепей уже соединены
в одну, то к её концу нельзя добавить не более чем $k-1$
из оставшихся цепей. Поэтому удастся соединить в одну
цепь $P^{\prime}$ какие-то $2k-2$ цепи. Без ограничения
общности будем считать, что $P^{\prime}=P_{1}\rightarrow
P_{2}\rightarrow\ldots $ $\rightarrow P_{2k-3}\rightarrow
P_{2k-2}$. Докажем, что оставшиеся цепи удастся добавить
к $P^{\prime}$, вставляя их либо между некоторыми двумя
цепями, либо в начало или конец цепи $P^{\prime}$.
Действительно, всего в $P^{\prime}$ имеется $2k-1$
позиций для вставки следующей цепи $P_{2k-1}$, при этом
не более чем $2(k-1)$ из этих позиций могут быть
запрещенными (считается, что позиция между цепями $P_i$
и $P_{i+1}$ запрещена для вставки цепи $P_{2k-1}$,
если какая-то из дуг $(t_i,s_{2k-1})$ или $(t_{2k-1},
s_{i+1})$ является запрещённой). Таким образом, удаётся
добавить к $P^{\prime}$ цепь $P_{2k-1}$, а затем и все
остальные цепи, так как количество позиций для вставки
каждой следующей цепи увеличивается, а число запрещённых
позиций всегда не превосходит $2(k-1)$. В результате
получаем одну гамильтонву цепь $P$. Без потери общности
считаем, что $P=P_{1}\rightarrow P_{2}\rightarrow\ldots$
$\rightarrow P_{3k-4}\rightarrow P_{3k-3}$.

Пусть $2 \leq i \leq j \leq 3k-4$. Назовём \textit{$(P_{i},
P_{j})$-перестановкой} следующее переупорядочение цепей
внутри $P$: $(P_{1},\:P_{2},\ldots ,\:P_{3k-3})$ $\rightarrow$
$(P_{i},\:P_{i+1},\ldots ,\:P_{j},$ $P_{1},\ldots,\:
P_{i-1},$ $P_{j+1},\ldots ,\:P_{3k-3})$. Будем называть
перестановку \textit{успешной}, если дуги $(t_{j},s_{1})$,
$(t_{i-1},s_{j+1})$ и $(t_{3k-3},s_{i})$ являются
допустимыми. то есть при добавления к полученной цепи
дуги $(t_{3k-3},s_{i})$ получается гамильтонов цикл
$H_{k}$, не имеющий общих дуг с циклами $H_{1},$ $H_{2},
\ldots,$ $H_{k-1}$. Далее выполняются следующие шаги,
пока не удастся сделать успешную перестановку.

\smallskip
\noindent
\\\textit{Шаг 0.}
\\*Если дуга $(t_{3k-3},s_{1})$ допустима, то, добавляем
её к $P$ и получаем гамильтонов цикл $H_{k}$.
Иначе переходим на Шаг 1.
\medskip
\\\textit{Шаг l $(1 \leq l \leq k-2)$.}
\\*Считаем, что к началу шага $l$ следующие дуги являются
запрещёнными (иначе цикл $H_{k}$ был построен на одном
из предыдущих шагов):
\begin{itemize}
 \item[--] $(t_{3k-3},s_{1}),\:(t_{3k-4},s_{1})\:,\ldots,\:
(t_{3(k-1)-l+1},s_{1})$ --- $l$ дуг, входящих в вершину $s_{1}$;
 \item[--] $(t_{3k-3},s_{1}),\:(t_{3k-3},s_{2})\:,\ldots,\:
(t_{3k-3},s_{l})$ --- $l$ дуг, исходящих из вершины $t_{3k-3}$.
\end{itemize}

Рассмотрим множество перестановок $A_l$, состоящее из всех
$(P_{l+1}, P_{j})$-перестановок, где $j=l+1,\ldots ,3(k-1)-l$.
В этом множестве найдётся успешная перестановка, если при
некотором $j\in \{l+1,\ldots,3(k-1)-l\}$ дуги $(t_{j},s_{1})$,
$(t_{l},s_{j+1})$ и $(t_{3k-3},s_{l+1})$ являются допустимыми.
Покажем, что если ни одна из перестановок в $A_l$ не является
успешной, то дуга $(t_{3k-3},s_{l+1})$ запрещена. Заметим,
что среди $l$ известных к началу Шага $l$ запрещённых дуг,
входящих в $s_{1}$, нет дуг из множества $\{(t_{j},s_{1})
\:|\:j=l+1,\ldots ,3(k-1)-l\}$. Поэтому в этом множестве
запрещёнными являются не более $k-1-l$ дуг. Среди дуг
множества $\{(t_{l},s_{j+1})\:|\:j=l+1,\ldots ,3(k-1)-l\}$
запрещены не более чем $k-1$ дуг. Таким образом, не более
чем $(k-1-l)+(k-1)=2(k-1)-l$ перестановок из $A_l$ могут быть
неуспешными из-за запрещённости дуги, принадлежащей одному из
указанных множеств. Поскольку общее количество перестановок
в $A_l$ равно $3(k-1)-2l$, и
\[
3(k-1)-2l-(2(k-1)-l)=k-1-l \geq k-1-(k-2)=1,
\]
то в $A_l$ найдётся успешная перестановка, если дуга $(t_{3k-3},
s_{l+1})$ допустима. Поэтому можем считать, что дуга
$(t_{3k-3},s_{l+1})$ является запрещённой.

\smallskip
Теперь рассмотрим множество перестановок $B_l$, состоящее
из всех $(P_{i},P_{3(k-1)-l})$-перестановок, где $i=l+2,
\ldots,3(k-1)-l$. В этом множестве найдётся успешная
перестановка, если при некотором $i\in \{l+2,\ldots,
3(k-1)-l\}$ дуги $(t_{3(k-1)-l},s_{1})$, $(t_{i-1},
s_{3(k-1)-l+1})$ и $(t_{3k-3},s_{i})$ являются допустимыми.
Покажем, что если ни одна из перестановок в $B_l$ не
является успешной, то дуга $(t_{3(k-1)-l},s_{1})$ запрещена.
На данный момент известно $l$ запрещённых дуг, входящих
в вершину $s_{1}$, и уже $l+1$ запрещённых дуг, исходящих
из $t_{3k-3}$ (с учётом дуги $(t_{3k-3},s_{l+1})$).
Заметим, что среди последних отсутствуют дуги множества
$\{(t_{3k-3},s_{i})\:|\:i=l+2,\ldots ,3(k-1)-l\}$. Поэтому
в этом множестве запрещёнными являются не более чем
$k-1-(l+1)$ дуг. Во множестве $\{(t_{i-1},s_{3(k-1)-l+1})
\:|\:i=l+2,\ldots,3(k-1)-l\}$ запрещены не более $k-1$
дуг. Следовательно, не более чем $2(k-1)-l-1$ перестановок
из множества $B_l$ могут быть неуспешными из-за запрещённости
дуги, принадлежащей одному из указанных множеств. Поскольку
общее количество перестановок в $B_l$ равно
$3(k-1)-2l-1$, и
\[
3(k-1)-2l-1-(2(k-1)-l-1)=k-1-l \geq k-1-(k-2)=1,
\]
то в $B_l$ найдётся успешная перестановка, если дуга
$(t_{3(k-1)-l},s_{1})$ допустима. Поэтому далее считаем,
что дуга $(t_{3(k-1)-l},s_{1})$ является запрещённой, и
переходим на Шаг $l+1$.

\bigskip
Если выполнены все шаги, но среди рассмотренных
перестановок не оказалось ни одной успешной, то
имеем следующие запрещённые дуги:
\begin{itemize}
 \item[--] $(t_{3k-3},s_{1})$, $(t_{3k-4},s_{1}),\ldots,
(t_{2k},s_{1})$, $(t_{2k-1},s_{1})$ --- $k-1$ дуг,
входящих в вершину $s_{1}$;
 \item[--] $(t_{3k-3},s_{1})$, $(t_{3k-3},s_{2}),\ldots,
(t_{3k-3},s_{k-2})$, $(t_{3k-3},s_{k-1})$ --- $k-1$ дуг,
исходящих из вершины $t_{3k-3}$.
\end{itemize}
Отсюда следует, что все остальные входящие в $s_{1}$
и исходящие из $t_{3k-3}$ дуги являются допустимыми.

\smallskip
Рассмотрим множество перестановок $C_l$, состоящее
из всех $(P_{i},P_{2k-2})$-перестановок, где
$i=k, k+1,\ldots,2k-2$. В этом множестве найдётся
успешная перестановка, если при некотором $i\in
\{k,k+1,\ldots,2k-2\}$ дуги $(t_{2k-2},s_{1})$,
$(t_{i-1},s_{2k-1})$ и $(t_{3k-3},s_{i})$
допустимы. Из сделанных выше предположений следует,
что дуга $(t_{2k-2},s_{1})$ и все дуги $(t_{3k-3},
s_{i})$, где $i=k,k+1,\ldots,2k-2$, являются
допустимыми. Следовательно, если ни одна
перестановка из множества $C_l$ не является
успешной, то запрещёнными являются следующие
$k-1$ входящих в вершину $s_{2k-1}$ дуг:
$(t_{i-1},s_{2k-1})$, $i=k,k+1,\ldots ,2k-2$.
Это означает, что все другие входящие в вершину
$s_{2k-1}$ дуги являются допустимыми.

Теперь мы можем соединить все цепи тура $T_k$
кроме $P_{k-1}$ в один цикл: $(P_{1} \rightarrow
P_{2} \rightarrow \ldots $ $\rightarrow P_{k-2}$
$\rightarrow P_{2k-1} \rightarrow$ $P_{2k}
\rightarrow \ldots$ $\rightarrow P_{3k-3}
\rightarrow$ $P_{k} \rightarrow$ $P_{k+1}
\rightarrow \ldots $ $\rightarrow P_{2k-2}
\rightarrow P_{1})$, поскольку дуги $(t_{k-2},
s_{2k-1})$, $(t_{3k-3},s_{k})$ и $(t_{2k-2},
s_{1})$ допустимы. Цепь $P_{k-1}$ также можно
вставить в этот цикл между какими-то двумя
цепями, поскольку среди $3k-4$ позиций для
вставки запрещёнными являются не более чем
$2(k-1)$. Так как $3k-4>2(k-1)$ при $k\geq 3$,
то найдётся позиция, куда можно вставить
цепь $P_{k-1}$. Таким образом, получаем
гамильтонов цикл $H_{k}$, не имеющий общих
рёбер с уже построенными гамильтоновыми
циклами.

Заметим, что при построении каждого
гамильтонового цикла соединение всех
цепей тура $T_k$ в гамильтонову цепь $P$
производится за время $O(mn)$, а этап
преобразования цепи $P$ в гамильтонов цикл
также выполняется за время $O(mn)$,
поскольку просматривается порядка $m^2<mn$
возможных перестановок цепей. Таким
образом, трудоёмкость построения $m$
гамильтоновых циклов процедурой
``Замыкание($T_1$--$T_m$)'' оценивается
как $O(m^{2}n)$.

\section{Оценка точности и трудоемкости
алгоритма $A_{2/3-\varepsilon}$}

Докажем, что алгоритм $A_{2/3-\varepsilon}$
обладает оценкой точности $2/3$ при чётных
$m$ и оценкой $\frac{2}{3}-\frac{1}{5m}$
при нечётных $m$. На Фазе 1 в орграфе $G$
находится подграф $G_{m,m}$, вес которого
не меньше веса оптимального решения задачи
$m$-APSP-max. Далее в $G_{m,m}$ строятся
рёберно непересекающиеся частичные туры
$T_{1},T_{2},\ldots ,T_{m}$. Рассмотрим два
случая.

\smallskip
\textit{Случай 1.} $m$ чётно. В этом случае
каждая из пар частичных туров, полученных
процедурой $P_{2/3}$ или процедурой
$P^{\prime}_{2/3}$, имеет вес не меньше,
чем $2/3$ от веса соответствующего
$(2,2)$-регулярного орграфа $G_{2,2}^{i}$.
Поэтому выполняется цепочка неравенств
$$w(T_1)+\ldots +w(T_m)\geq \frac{2}{3}
\left(w(G^{1}_{2,2})+\ldots+w(G^{m/2}_{2,2})
\right)= \frac{2}{3}w(G_{m,m})\geq
\frac{2}{3}w^{*}.$$

\smallskip
\textit{Случай 2.} $m$ нечётно. В этом случае
для частичных туров $T_{1},T_{2},\ldots ,T_{m}$
выполняются неравенства $$w(T_1)+w(T_2)+w(T_3)
\geq \frac{3}{5}w(G_{3,3});$$
$$w(T_4)+\ldots +w(T_m)\geq \frac{2}{3}
\left(w(G^{1}_{2,2})+\ldots+w(G^{(m-3)/2}_{2,2})
\right).$$
Следовательно, $$w(T_1)+w(T_2)+\ldots +w(T_m)
\geq \frac{3}{5}w(G_{3,3})+\frac{2}{3}\left(
w(G^{1}_{2,2})+\ldots+w(G^{(m-3)/2}_{2,2})
\right)=$$
$$=\frac{2}{3}w(G_{m,m})-\left(\frac{2}{3}-
\frac{3}{5}\right)w(G_{3,3})=\frac{2}{3}
w(G_{m,m})-\frac{1}{15}w(G_{3,3}).$$

Так как орграф $G_{3,3}$ образован тремя
самыми ``лёгкими'' 2-факторами в $G_{m,m}$
(см. Фазу 2 алгоритма $A_{2/3-\varepsilon}$),
то справедливо неравенство $w(G_{3,3})\le
\frac{3}{m}w(G_{m,m})$. Отсюда следует, что
$$w(T_1)+w(T_2)+\ldots +w(T_m)\geq \left(
\frac{2}{3}-\frac{1}{5m}\right)w(G_{m,m})\geq
\left(\frac{2}{3}-\frac{1}{5m}\right)w^{*}.$$

На Фазе 4 алгоритма частичные туры $T_{1},
T_{2},\ldots,T_{m}$ дополняются до рёберно
непересекающихся гамильтоновых циклов $H_{1},
H_{2},\ldots ,H_{m}$ с помощью процедуры
``Замыкание($T_1$--$T_m$)''. При этом
суммарный вес циклов может только возрастать,
то есть выполняется неравенство
$$w(H_{1})+w(H_{2})+\ldots +w(H_{m})\ge
w(T_{1})+w(T_{2})+\ldots +w(T_{m}).$$
Следовательно, при любом чётном $m$ вес
найденного алгоритмом $A_{2/3-\varepsilon}$
при\-бли\-жён\-но\-го решения задачи
$m$-APSP-max будет не меньше $\frac{2}{3}w^*$,
а при нечётном $m$ --- не меньше $\left(
\frac{2}{3}-\frac{1}{5m}\right)w^*$.

\smallskip
Оценим трудоемкость алгоритма
$A_{2/3-\varepsilon}$. Фаза 1 выполняется
за время $O(mn^{3})$, определяемое
применением алгоритма Габова из \cite{Gabow}.
Трудоёмкость Фазы 2 определяется временем
работы алгоритма Хопкрофта и Карпа из
\cite{Hopcroft} и оценивается как
$O(m^{2}n^{3/2})$. На Фазе 3 не более чем
$m/2$ раз применяются процедуры, время
работы каждой из которых не превосходит
$O(n^3)$. Поэтому трудоёмкость Фазы 3
оценивается как $O(mn^{3})$. Наконец,
время выполнения Фазы 4 не превосходит
$O(m^{2}n)$. Учитывая, что $m<n$, можно
сделать вывод о том, что общее время
работы алгоритма $A_{2/3-\varepsilon}$
оценивается как $O(mn^{3})$. \,
Теорема 1 доказана.

\section{Заключительные замечания}

Нетрудно видеть, что отличие оценки
точности полученного нами алгоритма от
$2/3$ при нечётных значениях $m$ вызвано
однократным применением процедуры
$P_{3/5}$ из \cite{GT_3/5} на Фазе 3
алгоритма. Это отличие не представляется
%представляется несколько искусственным
непреодолимым и обусловлено лишь
спецификой избранного нами подхода по
разбиению $(m,m)$-регулярного орграфа
$G_{m,m}$ на $(2,2)$-регулярные подграфы
и применению процедур из известных
алгоритмов. Поэтому целью ближайших
исследований может стать разработка
для задачи $m$-APSP-max полиномиального
алгоритма, имеющего гарантированную оценку
точности $2/3$ при любых значениях $m\ge 2$.

\smallskip
\begin{thebibliography}%{99}

\bibitem{ABG_3_4}
\textbf{Агеев~А.~А., Бабурин~А.~Е., Гимади~Э.~Х.} Полиномиальный
алгоритм с оценкой $3/4$ для нахождения двух реберно
непересекающихся гамильтоновых циклов максимального суммарного веса
~// Дискрет. анализ и исслед. операций. Сер.~1. 2006. Т.~13, \No~2.
С.~11--20.

\bibitem{AP_08}
\textbf{Агеев~А.~А., Пяткин~А.~В.} Приближённый алгоритм решения
метрической задачи о двух коммивояжёрах с оценкой точности 2~//
Дискрет. анализ и исслед. операций. 2009. Т.~16, \No~4. С.~3--20.

\bibitem {BG_10}
\textbf{Бабурин~А.~Е., Гимади~Э.~Х.} Об асимптотической точности
эффективного алгоритма решения задачи $m$-PSP на максимум в
многомерном eвклидовом пространстве~// Тр/ ин-та математики и
механики УРО РАН. 2010. Т.~16, \No~3. С.~12--24.

\bibitem{BGK_04}
\textbf{Бабурин~А.~Е., Гимади~Э.~Х., Коркишко~Н.~М.} Приближенные
алгоритмы для нахождения двух реберно непересекающихся гамильтоновых
циклов минимального веса~// Дискрет. анализ и исслед. операций.
Сер.~2. 2004. Т.~11, \No~1. С.~11–-25.

\bibitem {G_08}
\textbf{Гимади~Э.~Х.} Асимптотически точный алгоритм отыскания
одного и двух реберно непересекающихся маршрутов коммивояжера
максимального веса в eвклидовом пространстве~// Тр. ин-та математики
и механики УРО РАН. 2008. Т.~14, \No~2. С.~23--32.

\bibitem {GGG}
\textbf{Гимади~Э.~Х., Глазков~Ю.~В., Глебов~А.~Н.} Приближенные
алгоритмы решения задачи о двух коммивояжерах в полном графе с
весами ребер 1 и 2~// Дискрет. анализ и исслед. операций. Сер.~2.
2007. Т.~14, \No~2. С.~41--61.

\bibitem{GiIv_12}
\textbf{Гимади~Э.~Х., Ивонина~Е.~В.} Приближенные алгоритмы решения
задачи о двух коммивояжерах на максимум~// Дискрет. анализ и исслед.
операций. Сер.~2. 2012. Т.~19, \No~1. С.~17--32.

\bibitem{GZ_7_5}
\textbf{Глебов~А.~Н., Гордеева~А.~В., Замбалаева~Д.~Ж.} Алгоритм с
оценкой $7/5$ для задачи о двух коммивояжерах на минимум с
различными весовыми функциями~// Сибирские электронные
математические известия. 2011. Т.~8. С.~296--309.

\bibitem{GZ_7_9}
\textbf{Глебов~А.~Н., Замбалаева~Д.~Ж.} Полиномиальный алгоритм с
оценкой точности $7/9$ для задачи о двух коммивояжёрах на максимум
~// Дискрет. анализ и исслед. операций. 2011. Т.~18, \No~4.
С.~17–-48.

\bibitem{GZ_4_3}
\textbf{Глебов~А.~Н., Замбалаева~Д.~Ж.} Приближённый алгоритм
решения задачи о двух коммивояжёрах на минимум с различными весовыми
функциями~// Дискрет. анализ и исслед. операций. 2011. Т.~18. \No~5,
С.~11--37.

\bibitem{GZS_2/3}
\textbf{Глебов~А.~Н., Замбалаева~Д.~Ж., Скретнева~А.~А.}
$2/3$-при\-бли\-жён\-ный алгоритм для несимметричной задачи о двух
коммивояжёрах на максимум~// Дискрет. анализ и исслед. операций.
2014. Т.~21, \No~6. С.~11–-20.

\bibitem{GT_3/5}
\textbf{Глебов~А.~Н., Токтохоева~С.~Г.}
Полиномиальный $3/5$-при\-бли\-жён\-ный алгоритм для несимметричной
задачи о трёх коммивояжёрах на максимум~// Дискрет. анализ и исслед.
операций. 2019. Т.~26, \No~2. С.~30–-59.

\bibitem{Gord}
\textbf{Гордеева~А.~В.} Полиномиальные алгоритмы с гарантированными
оценками точности для метрической задачи о двух коммивояжёрах на
максимум~// Выпускная дипломная работа специалиста. Новосибирск,
НГУ, 2010.

\bibitem{Serd}
\textbf{Сердюков А.~И.} Алгоритм с оценкой для задачи коммивояжера
на максимум~// Управляемые системы. Сб.~науч.~тр. Вып.~25. ---
Новосибирск: Ин-т математики СО~АН~СССР, 1984. С.~80--86.

\bibitem{CC03}
\textbf{Wolfter Calvo~R., Cordone~R.} A heuristic approach to the
overnight security service problem~// Computers and Operations
Research. 2003. Vol.~30, P.~1269--1287.

\bibitem{De Brey_Vol}
\textbf{De Brey~M.~J.~D., Volgenant~A.} Well-solved cases of the
2-Peripatetic Salesman Problem~// Optimization. 1997. Vol.~39,
No.~3. P.~275--293.

\bibitem{De_Kort}
\textbf{De Kort~J.~B.~J.~M.} Lower bounds for symmetric $K$-PSP ~//
Optimization. 1991. Vol.~22, No.~1. P.~113--122.

\bibitem{De_Kort1}
\textbf{De Kort~J.~B.~J.~M.} Upper bounds for the symmetric 2-PSP~//
Optimization. 1992. Vol.~23, No.~4. P.~357--367.

\bibitem{De_Kort2}
\textbf{De Kort~J.~B.~J.~M.} A branch and bound algorithm for
symmetric 2-PSP~// EJOR. 1993. Vol.~70. P.~229--243.

\bibitem{DMPR4/5}
\textbf{Dudycz~S., Marcinkowski~J., Paluch~K., Rybicki~B.~A.}
$4/5$-appro\-xi\-ma\-tion algorithm for the maximum Traveling
Salesman Problem~// from book Integer Programming and Combinatorial
Optimization: Proc. 19th International Conference, IPCO 2017.
(Waterloo, ON, Canada, June 26--28, 2017). Lect. Notes Comput. Sci.
Vol.~10328. Springer, 2017. P.~173--185.

\bibitem{Gabow}
\textbf{Gabow~H.~N.} An efficient reduction technique for
degree-restricted subgraph and bidirected network flow problems~//
Proc. 15th Annu. ACM Symp. Theory of Comput. (Boston, April 25-–27,
1983). New York: ACM, 1983. P.~448–456.

\bibitem{Gimadi}
\textbf{Gimadi~E.~Kh.} Approximation efficient algorithms with
performance guarantees for some hard routing problems~// In Proc. of
the II International Conference ''Optimization and Applications'',
OPTIMA-2011. (Petrovac, Montenegro, Sertember 25 -- October 2,
2011). Moscow: VC RAN, 2011. P.~98--101.

\bibitem{G_16}
\textbf{Glebov~A.~N., Gordeeva~A.~V.} An algorithm with
approximation ratio $5/6$ for the Metric Maximum $m$-PSP~// In
Kochetov~Yu. et al (eds.) DOOR-2016. Lect. Notes Comput. Sci.
Vol.~9869. Springer, Heidelberg, 2016. P.~159--170.

\bibitem{2533TSP}
\textbf{Hassin~R., Rubinstein~S.} Better approximations for max TSP
~// Information Processing Letters. 2000. Vol.~75, No.~4.
P.~181--186.

\bibitem{Hopcroft}
\textbf{Hopcroft~J.~E., Karp~R.~M.} An $n^{5/2}$~algorithm for
maximum matchings in bipartite graphs~// SIAM~J. COMPUT. 1973.
Vol.~2, No.~4. P.~225-–231.

\bibitem{KLSS}
\textbf{Kaplan~H., Lewenstein~M., Shafrir~N., Sviridenko~M.}
Approximation algorithms for asymmetric TSP by decomposing directed
regular multigraphs~// JACM. 2005. Vol.~52, No.~4. P.~602-–626.

 \bibitem{Krarup}
\textbf{Krarup~J.} The peripatetic salesman and some related
unsolved problems~// Combinatorial programming: methods and
applications (Proc. NATO Advanced Study Inst., Versailles, 1974).
Advanced Study Inst. Ser., Ser. C: Math. and Phys. Sci. Vol.~19.
Dordrecht: Reidel, 1975. P.~173--178.

\bibitem{PMM7/9}
\textbf{Paluch~K., Mucha~M., Madry~A.} A $7/9$-approximation
algorithm for the maximum Traveling Salesman Problem~//
Approximation, Randomization, and Combinatorial Optimization.
Algorithms and Techniques (Proc. 12th International Workshop, APPROX
2009, and 13th International Workshop, RANDOM 2009. Berkeley, CA,
USA, August 21--23, 2009). Lect. Notes Comput. Sci. 2009. Vol.~5687.
Springer, 2009. P.~298--311.

\bibitem{TSP}
\textbf{Gutin~G., Punnen~A.~P.} (eds.) The Traveling Salesman
Problem and its variations~// Kluver Academic Publishers:
Dordrecht/Boston/London, 2002.

\end{thebibliography}
