%\input amsppt.sty
%\documentstyle{amsppt}
\Monograph
\Russian
\TagsOnRight
\NoRunningHeads
\magnification=\magstep2
\pageno1
\topmatter
\endtopmatter
\headline={\hss\tenrm\folio\hss}


\midinsert
%\vspace{0.3 cm}
\botcaption{}
\endcaption
\endinsert
\noindent
УДК 681.3.06
\nopagebreak
\smallskip
\noindent
{\bf М.~Г.~Розинас,  Е.~А.~Тихомиpова}
\nopagebreak
\smallskip
\noindent
{\bf ПОСТРОЕНИЕ СХЕМ ВЗВЕШЕННЫХ ГРАФОВ}
\nopagebreak
\medskip

\quad Предлагается алгоритм такого изображения взвешенного графа на
плоскости,  при   котором   расстояние   между   образами   вершин
приближенно  соответствует  длине  кратчайшего  пути  между  ними.
Основная  область   применения   алгоритма   --   построение   схем
транспортных систем.

\medskip
\centerline {\bf {1. ~Математическая модель задачи}}
\smallskip

\quad      Под схемой транспортной системы понимается изображение ее  на
плоскости  с  помощью  точек  и  соединяющих  их  отрезков  прямых
(пересечения отрезков допускаются). Хотя  от  схемы  не  требуется
картографической точности, желательно, чтобы по расстояниям  между
изображениями станций на  схеме  можно  было    судить  о  длине
кратчайшего пути, соединяющего эти станции.

\quad      В работе формализуется задача построения  оптимальной  схемы,
предлагается  алгоритм  ее  приближенного  решения  и  описываются
результаты испытаний этого алгоритма.

\quad      Все используемые понятия теории графов можно найти, например,
в [2]. Пусть $R^m$   -- $m$-мерное  вещественное  пространство, $R=R^1$ и
$R^+ = \{x ~|~ x \in R ~\& ~x>0\}.$

\quad      Для   произвольного   конечного   метрического   пространства \break
$M= <~\{v_1,~\ldots,~v_n \},L~>$ его $m$-{\it меpной схемой} будем называть
произвольную
матрицу $X=(x_{i,k}),$ в которой  все  строки  попарно  различны
$(m \geq 1,
~1 \leq i \leq n,  ~1 \leq k \leq m,  ~x_{i,k} \in R).$
При  этом  вектор   $x_i =(x_{i,1} ,~\ldots,~x_{i,m})$
интерпретируется как образ точки $v_i$  в пространстве $R^m .$

\quad      Назовем $m$-мерную схему $X$ конечного метрического  пространства
$M=<~V,L~>$ {\it точной}, если для любых $v_i ,v_j \in V$  расстояние
$|x_i -x_j|$    между
точками $x_i, x_j$  в пространстве $R^m$  совпадает с $L(v_i, v_j).$
Очевидно,
из существования  точной  $m$-мерной  схемы  вытекает  существование
точных $k$-мерных  схем  для  всех  $k>m.$  Понятно  также,  что  если
${Card}(V)=n,$ то из существования точной $m$-мерной  схемы  $X$  при
$m \geq n$
следует существование точной  $(n-1)$  мерной  схемы,  а  поэтому  и
точных $k$-мерных схем для всех $k \geq n-1.$

\quad      Однако если ${Card}(V) \geq 4,$ то $M$ может и не иметь точных
$m$-мерных
схем  ни  при  каких  $m.$   Например,   метрическое   пространство \break
$M=<~\{a,b,c,d\},L~>,$ где  $L(a,b)=L(b,c)=L(c,a)=20$        и
$L(a,d)=L(b,d)=L(c,d)=11,$ не имеет точных трехмерных  схем,  откуда
вытекает отсутствие точных $m$-мерных схем при всех $m.$

\quad      Чтобы  количественно  оценивать  степень   неточности   схем,
выберем и  зафиксируем  произвольную  непрерывно  дифференцируемую
функцию $g~:~(R^+)^2 \to R^+,$ удовлетворяющую следующим свойствам:
$$
(\forall p \in R^+)~(g(p,p)=0) ,
\eqno(1) 
$$ $$
(\forall p,l \in R^+)~\big((p<l  \Rightarrow
{{\partial g(p,l)}\over {\partial p}} >0) ~\& ~
(p>l \Rightarrow
{{\partial g(p,l)}\over {\partial p}}<0)\big) ,
\eqno(2)
$$ $$
(\forall l \in R^+)~( \lim_ {p \to \infty}
 g(p,l)= \infty) ,
\eqno(3)
$$ $$
(\forall l \in R^+)~(\lim_{p \to 0} g(p,l)= \infty) .
\eqno(4)
$$

\noindent
Например, можно взять
$$
g(p,l)=(p/l)+(l/p)-2 .
\eqno(5)
$$

\quad {\it Дефектом} $m$-мерной схемы $X$ конечного метрического пространства
$M=<~\{v_1 ,~\ldots,v_n \},L>$ назовем число
$$
\Phi (X)={1\over 2} \sum_{i \ne j}g(|x_i -x_j|,~L(v_i ,v_j )~) .
\eqno(6)
$$

\quad Понятно, что дефект любой схемы неотрицателен и обращается  в
нуль  только  на  точных  схемах.   Назовем   $m$-мерную   схему   $X$
пространства  $M$ {\it оптимальной},  если
$\Phi (X) \leq \Phi (Y)$  для  любой  другой
$m$-мерной схемы $Y$ этого пространства.

\proclaim{\indent Утвеpждение 1}  Всякое конечное метрическое пространство
имеет оптимальные $m$-мерные схемы при любом $m \geq 1.$
\endproclaim

\quad \underbar {Доказательство}. Пусть $m \geq 1$ и
$M= <~\{v_1 ,~\ldots,v_n \},~L>.$
Так как дефект  $\Phi(X)$ не  меняется  при  одновременном  параллельном
переносе в $R^m$  всех строк матрицы $X,$ то можно, не  теряя  общности,
ограничиться рассмотрением множества $S$ таких схем $X,$  для  которых
$x_1 =0 \in R^m.$  Пусть $X^0 \in S$ и $\Phi^0 = \Phi(X^0 ).$
В силу (3), для каждого  $i=2,\ldots,n$
найдется такое $r_i >0,$  что
$(\forall p)~(p>r_i \Rightarrow ~g\big(p,L(v_1 ,v_i )\big)~>\Phi^0).$
Аналогично,
из (4) вытекает, что для любых $i,j=1,~\ldots,n,~ i \ne j,$  найдется  такое
$\varepsilon_{i,j} >0,$ что $(\forall p)~\big(0<p< \varepsilon_{i,j}
\Rightarrow ~g(p,L(v_i ,v_j ))>\Phi^0  \big).$
Пусть
$r=\max \{r_i |~i=2,~\ldots,n\}$ и $\varepsilon  =\min \{
\varepsilon_{i,j} |~ i,j=1,~\ldots,n; i \ne j\}.$

\quad Рассмотрим множество
$$
Z=\{X \in R^{mn} |~(x_1 =0) \wedge
(\forall i=2,\ldots,n)~(|x_1| \leq r) \wedge
$$ $$
(\forall ~i,j=1,\ldots,n;~i \ne j)~(|x_i -x_j| \geq \varepsilon \}
$$

\noindent
Понятно, что $Z$ -- непустое замкнутое  ограниченное  подмножество  в
$R^{mn}$ и $Z \subset S.$ По теореме Вейерштрасса, непрерывная  функция
$\Phi (X)$  на
компакте $Z$ достигает минимума в некоторой точке $X^*$. В силу  выбора
$r$ и $\varepsilon, ~(\forall X \in S\setminus Z)~(\Phi (X)>\Phi^0 ).$
Так как $\Phi (X^0)=\Phi^0,$  то  отсюда  вытекает,
что $X \in Z$ и, следовательно, $\Phi (X^*) \leq \Phi^0.$
Получаем, что в $X^*$  достигается
минимум функции $\Phi$  не только на $Z,$ но и на $S$ и, следовательно, $X^*$
-- оптимальная $m$-мерная схема.

\quad Оптимальные  $m$-мерные  схемы  являются  точками   глобального
минимума функции $\Phi : R^{mn} \to R^+.$
Схемы, на которых достигается локальный
минимум этой функции, назовем {\it локально-оптимальными}.

\quad Пусть $G=<V,E,C>$ -- взвешенный связный неориентированный граф с
множеством вершин $V=\{v_1,~\ldots,v_n \},$  множеством  ребер  $E$  и
весовой
функцией $C:E \to R^+.$  Обозначим  через  $L(u,v)$  минимальный  из  весов
путей, соединяющих вершины  $u$ и $v.$  Очевидно, $M=<V,L>$  является
метрическим пространством, $m$-мерные схемы которого  будем  считать
$m$-мерными схемами взвешенного  графа  $G.$  Введенные  выше  понятия
дефекта   и   оптимальной   схемы    также    очевидным    образом
распространяются на связные неориентированные взвешенные графы.

\quad Ясно, что понятие  оптимальной  двумерной  схемы  взвешенного
графа в определенной мере  отражает  интуитивное  представление  о
"хорошем"   изображении   графа   на   плоскости.   Конечно,   при
практическом построении схем транспортных систем  оценка  качества
построенных  схем  субъективна  и  дальнейшая   ее   формализация,
видимо, нецелесообразна.

\quad Так как в  практически  интересных  случаях  дефект  является
многоэкстремальной функцией в пространстве высокой размерности, то
построение  оптимальных  схем  представляется  весьма  трудоемким,
поэтому  мы  ограничимся  только   задачей   построения   локально
оптимальных   схем.   Ввиду   неполного    соответствия    дефекта
интуитивному  понятию  качества  схемы  такое  ограничение  вполне
оправданно. %\pagebreak

\medskip
%\newpage
\centerline{\bf {2. Метод постpоения локально-оптимальных схем}}
\smallskip

\quad Для поиска  локального  минимума  функции $\Phi (X)$  предлагается
использовать некоторую модификацию метода  тяжелого  шарика  (см., \linebreak
напр.,[1]). Напомним,  что  этот  метод  основан  на  рассмотрении
дифференциального уравнения
$$
\ddot x + \gamma \dot x + grad \Phi (x) = 0
\eqno(7)
$$

\noindent
при некотором $\gamma \in R^+.$

\quad Нетрудно  проверить  [2, с.338],  что  для  любого   решения
$x:R^+ \to R^{mn}$ этого уравнения функция
$v(t)=\Phi (x(t))+(\dot x(t),\dot x(t))/2$
удовлетворяет условию
$$
\dot v=-\gamma (\dot x, \dot x) \leq 0,
$$

\noindent
поэтому  $\dot v(t)$ всегда неотрицательно и $\dot v(t)<0$
при всех $t$, кроме тех,
для которых $\dot x(t)=0.$

\quad Пусть $X^*$  -- точка  строгого  локального  минимума  функции  $\Phi$.
Определим функцию $x^* :R^+ \to R^{mn}$ формулой
$(\forall t \in R^+ )~(x^* (t)=X^*).$  Очевидно,
$x^*$  является решением (7). Рассмотрим функцию
$$
      V(x,\dot x)=\Phi (x)-\Phi (X^*)+(\dot x,\dot x)/2 .
$$

\noindent
В силу сделанных  предположений  $V$  непрерывно    дифференцируема,
не\-от\-рицательна и -- в некоторой окрестности точки $X^*$  -- обращается в
нуль только при $x=X^*$  и $\dot x=0.$ Вместе с условием
$\dot v \leq 0$ это означает,  что $V$
является функцией Ляпунова для функции $x^*,$ причем $V$  обращается  в
нуль только  при $x=0$ и $\dot x=0.$  Отсюда  следует,  что  решение $x^*$
асимптотически устойчиво по Ляпунову [3, с.55].

\quad Содержательно это означает существование такой окрестности  $U$
точки $X^*$, что всякое решение $x$ задачи Коши  для  уравнения  (7)  с
начальным значением $x(0) \in U$ сходится к $X^*.$

\quad Минимизация $\Phi (X)$ методом тяжелого  шарика  допускает  простую
физическую интерпретацию. Пользуясь симметричностью метрик в $M$  и
$R^m,$ а также формулой
$$
|x_j - x_i|= \sqrt{\sum_{k=1}^m(x_{jk}-x_{ik})^2},
$$
из (6) получаем
$$
{{\partial \Phi}\over {\partial x_{ik}}}=
\sum_{j \ne i}{{\partial g}\over {\partial p}}
\big(|x_j -x_i |,~L(v_j,v_i)\big)
{{(x_{ik}-x_{jk})}\over {|x_i-x_j|}},
\eqno(8)
$$

\noindent
что позволяет записать (7) в виде
$$
\ddot x_{ik}=-\gamma \dot x_{ik}+
\sum_{j \ne i}
{{\partial g}\over {\partial p}}
\big(|x_j -x_i |,~L(v_j,v_i)\big)
{{(x_{jk}-x_{ik})}\over {|x_j-x_i|}},
\eqno(9)
$$

\noindent
($i=1,~\ldots,n; ~k=1,~\ldots,m$), или
$$
\ddot x_i=-\gamma \dot x_i+
\sum_{j \ne i} e_{ij} \cdot
{{\partial g}\over {\partial p}}
\big(|x_j -x_i |,~L(v_j,v_i)\big)
\qquad (i=1,~\ldots,n),
\eqno(10)
$$

\noindent
где $e_{ij}$ -- единичный вектор, направленный вдоль $(x_j -x_i).$

\quad Представим теперь, что в $m$-мерном пространстве расположены  $n$
точек  единичной  массы.  Пусть  каждая  пара  точек  $i,j$  связана
пружиной, имеющей  в  ненапряженном  состоянии  длину  $L(v_i ,v_j)$  и
действующей на точку $i$ с силой
$$
f_{ij}=
{{\partial g}\over {\partial p}}
\big(|x_j -x_i |,~L(v_j,v_i)\big),
\eqno(11)
$$

\noindent
направленной по вектору $x_j -x_i.$ В силу (2), точки притягиваются при
растяжении  пружины  и  отталкиваются  при  сжатии.  Если  на  эти
материальные точки действует также сила  трения,  пропорциональная
их скорости (с коэффициентом трения $\gamma$), то движение такой  системы
точек как раз и описывается уравнениями (10).

\medskip
\centerline{\bf {3. Пpактическая pеализация метода}}
\smallskip

\quad Понятно,  что  при  практическом  построении  схем  на  основе
численного решения задачи Коши для дифференциального уравнения (7)
можно столкнуться со следующими трудностями:

\quad --  отсутствием  сходимости  из-за   неудачного   выбора   шага
интегрирования  и  (или)  ограничений  на  точность  представления
данных в ЭВМ;

\quad -- сходимостью к локально-оптимальной схеме, весьма далекой  от
оптимальной и  не  отвечающей  интуитивному  понятию  качественной
схемы (в частности, из-за неудачного выбора начального  условия  в
задаче Коши);

\quad -- высокой временной сложностью алгоритма,  препятствующей  его
практическому применению.

\quad Конечно,  построение   практически   эффективного   алгоритма
возможно только  путем  экспериментального  сравнения  алгоритмов,
основанных на применении разных численных методов  решения  задачи
Коши и различных эвристических  приемов,  подсказанных  спецификой
задачи и ее физической интерпретацией.  Излагаемый  ниже  алгоритм
получен  именно  таким  способом   и   представляется   достаточно
эффективным и пригодным для практического применения.

\quad Разумеется,  при  таком  подходе   к   разработке   алгоритма
необходимо ограничиться определенным классом задач, поэтому  далее
будем  рассматривать  только  построение  двумерных  схем  связных
взвешенных графов.

\quad Алгоритм  зависит  от  ряда  числовых  параметров,   значения
которых  сильно  влияют  на  его   эффективность.   При   введении
каждого  параметра  в  скобках  будет  указано  его   приближенное
значение  (или  диапазон  значений),  обеспечивающее  --   согласно
проведенным экспериментам -- достаточно высокую эффективность.

\quad Изложение   алгоритма   начнем   с   описания   используемого
численного  метода  решения  задачи  Коши.  Поскольку   вычисление
$grad \Phi (x)$ весьма трудоемко (см. (8)), а нас  интересует  не  точное
решение (7), а только его предел при $t \to \infty$, то  значения
$x$  и  $x$  в
точке $t+\Delta t$ вычислялись по формулам, представляющим  собой  "смесь"
методов Эйлера и Рунге~-~Кутта второго порядка (см.,напр.[1, c.360]).

\quad Сначала, в соответствии с методом Эйлера, вычислялись
$$
\dot x^* (t+ \Delta t)=\dot x(t)+\Delta t \big(-\gamma x - grad \Phi(x)\big),
\eqno(12) 
$$ $$
x^* (t+ \Delta t)=x(t)+ \Delta t \cdot \dot x(t).
\eqno(13)
$$

\noindent
После этого $x(t+ \Delta t)$ вычислялось по методу Рунге~-~Кутта по формуле
$$ x^* (t+\Delta t)=x(t)+{{\Delta t}\over 2}
\big(\dot x(t)+\dot x^* (t+\Delta t)\big),$$

\noindent
однако, во избежание вычисления $grad \Phi\big(x^* (t+\Delta t)\big),$
полагалось
$$
x(t+\Delta t)=x^* (t+\Delta t).
$$

\noindent
Такой подход позволил  ограничиться  при  переходе  от $t$ к $t+\Delta t$
вычислением $grad \Phi (x)$ только в одной точке.

\quad Численное решение задачи Коши для дифференциального уравнения
(7) выполнялось с переменным шагом  по  времени.  На  каждом  шаге
итерации  величина  $\Delta t$  выбиралась  так,  чтобы  путь,  пройденный
каждой из движущихся точек  по  любой  из  координат, не  превышал
$\rho L_{min},$  где $L_{min}=\min\{L(v_i ,v_j)|
 i,j=1,~\ldots,n; ~i \ne j\})$  --  минимальное
расстояние между вершинами графа,  а $\rho$ -  коэффициент,  значение
которого (первоначально равное $0.1 \sim 0.2$), изменяется описанным ниже
способом.

\quad Заметим,  что  при  подсчете  длины  пути,  пройденного  $k$-й
координатой $i$-й точки $x_{i,k}$ предполагается, что в течение  периода
$[t,t+\Delta t]$ эта координата непрерывно изменяется по формуле
$$
x_{i,k} (t+\tau)=x_{i,k} (t)+ \tau(x_{i,k} (t)+\tau \ddot x_{i,k}(t)),
$$

\noindent
где $\ddot x_{i,k}(t)$ вычисляется по формуле (9). В частности, если знаки
$\dot x_{i,k}(t)$ и $\dot x_{i,k}(t+\Delta t)$ различны, то  длина  пути,
пройденного  $k$-й
координатой,  может  существенно  превышать
$|x_{i,k}(t+\Delta t)-x_{i,k}(t)|.$
Если  же  при  выборе $\Delta t$ исходить   из   достаточной   малости
$|x_{i,k}(t+\Delta t)-x_{i,k}(t)|,$ то это может привести --
и часто приводит -- к расходимости метода.

\quad Решения  задачи  Коши  для  дифференциального  уравнения  (7)
сходятся к  локально-оптимальным  схемам  независимо  от  значения
коэффициента трения $\gamma$, поэтому  нам  позволительно  изменять
$\gamma$ в
процессе решения.  Из  физической  интерпретации  метода  тяжелого
шарика для нашей задачи понятно, что движение связанных  пружинами
точек будет подвержено  колебаниям,  для  более  быстрого  гашения
которых целесообразно увеличить коэффициент трения. В связи с этим
начальное значение $\gamma  ~(0.2 \sim 0.3)$ увеличивается в
$1.2 \sim 1.5$ раза всякий
раз при возникновении колебаний. Вопрос распознавания  наступления
колебаний рассмотрим ниже.

\quad Вместе с тем увеличение  коэффициента  трения $\gamma$ допускалось
только до определенной максимальной величины $(\sim 0.8).$ Если же
$\gamma$ уже
достиг  максимального  значения,  а   колебания   тем   не   менее
продолжались, то использовался другой  прием  --  уменьшение  длины
шага.  Для  этого  коэффициент $\rho$,  используемый  при  выборе $\Delta t,$
уменьшался в некоторое число $(\sim 2)$ раз.

\quad Очевидным способом  уменьшения  размерности  задачи  является
последовательное   построение   схем,   включающих   все   большее
количество точек -- начиная с трех (когда  всегда  можно  построить
точную схему) и кончая схемой, содержащей все $n$  точек.  При  этом
схема из $m-1$ точки используется  --  вместе  с  добавленной  к  ней
точкой $m$ --  в  качестве  начального  приближения  при  построении
$m$-точечной схемы $(3<m \leq n).$  Однако  неудачный  выбор  начального
положения точки $m$ может при этом привести  к  локально-оптимальной
схеме $m$ точек, весьма далекой от оптимальной. Такой  пример  легко
привести даже для одномерных схем.

\quad Пусть взвешенный  граф  образует  треугольник $A_1A_2A_3$, причем \linebreak
$A_1 A_2 = 1,~A_1 A_3 =A_2 A_3 =10$
и  при  построении  его  одномерной   схемы
используется функция $g$ из (5). Если сначала построить  оптимальную
одномерную схему точек $A_1$  и $A_2,$ полагая $x_1 =0$ и $x_2 =1$,
то при  выборе
начального значения $x_3 \in (0,1)$ метод тяжелого шарика  приведет,  как
легко  проверить,  к   локально-оптимальной   схеме,   в   которой
$x_3 =(x_1 +x_2)/2.$ Понятно, что дефект такой  схемы  значительно  выше,
чем  у  оптимальной  схемы,  полученной  при  начальном   значении
$x_3 \notin [0,1],$ в которой точки $x_1$  и $x_2$  лежат рядом, по одну
сторону  от
$x_3$  и на значительном удалении от  нее.  Аналогичный  пример  легко
привести и для двумерных схем.

\quad Чтобы  избежать  при  построении  плоских   схем   неудачного
начального  положения  добавляемой  на   очередном   шаге   точки,
предлагается размещать ее сначала вне плоскости, содержащей  ранее
построенную схему. При  этом  переход  от  $(m-1)$-точечной  схемы  к
$m$-точечной разбивается  на  две  части:  движение  новой  точки  в
пространстве, а старых  -  на  плоскости  (эта  часть  завершается
установкой новой точки на плоскости) и движение всех  $m$  точек  на
плоскости (до получения схемы m точек).

\quad При движении новой точки в пространстве  будем  считать,  что,
кроме  сил   взаимодействия   со   стороны   старых   точек   (они
рассчитываются по формуле (11) с использованием расстояний в $R^3$) и
силы трения, на нее воздействует некая сила "притяжения плоскости"
$f^*,$ действующая по направлению от новой точки  к  ее  проекции  на
плоскость. Сила $f^*$  рассчитывается по формуле, близкой к (11):
$$
f^*=\cases{
  \mu {{\partial g}\over {\partial p}}(|z_m|, ~\varepsilon),
     &если $~|z_m|> \varepsilon L_{min}$,\cr
  \mu {{\partial g}\over {\partial p}}(\varepsilon,\varepsilon),
     &если $~|z_m| \leq \varepsilon L_{min}$,
}
$$

\noindent
где $z_m$  -- координата точки $m$  по  вертикали  (т.е.  в  направлении,
ортогональном   плоскости), $\varepsilon$  --   некоторое достаточно малое
положительное число $(0.1 \sim 0.05),$ а $\mu$ -- коэффициент,
характеризующий
силу  притяжения  новой  точки  к  плоскости  (начальное  значение
$0.1 \sim 1$).

\quad Если движение точек завершилось, но положение новой  точки  в
пространстве стабилизировалось на достаточно большом расстоянии
от
плоскости -- пpевышающем $\delta L_{min}$  (здесь паpаметp
$\delta \approx 0.3$), то сила
притяжения к плоскости  увеличивается.  Для  этого  коэффициент $\mu$
увеличивается  в  некоторое  число   $(\sim 10)$   раз.   Это   вызывает
возобновление движения,  при  стабилизации  которого  новая  точка
приближается к плоскости.

\quad Процесс движения новой точки в пространстве  продолжается  до
тех пор, пока - после  очередной  стабилизации  движения  -  новая
точка не окажется  на  расстоянии  от  плоскости,  не  превышающем
$\delta L_{min}.$
После этого заменяем новую точку ее проекцией на  плоскость
и переходим к движению точек на плоскости.

\quad Вычислительные эксперименты  показали  хорошие  результаты  в\break
случае, когда критерием стабилизации  движения  служит  достаточно
малый модуль вертикальной составляющей скорости  новой  точки,  не
превышающий $\beta \ast L_{min}.$ Здесь $\beta$  -- параметр метода
$(0.1 \sim 0.2).$ Начальное
положение новой точки $x_m$  в пространстве выбиралось  так:  проекция
$x_m$  на плоскость определяется вектором
$$
\Big(\sum_{i=1}^{m-1}x_i/L(v_i,v_m)\Big)/
\Big(\sum_{i=1}^{m-1}1/L(v_i,v_m)\Big),
\eqno(14)
$$

\noindent
а  третья  координата
$z_m =\min\{L(v_i ,v_m)| ~i<m\}.$  Заметим,  что   (14)
представляет собой взвешенную сумму векторов $x_i ~(i=1,~\ldots,m-1)$  c
весовыми коэффициентами, обратно пропорциональными $L(v_i ,v_m).$

\quad На этапе движения новой точки в пространстве  под  колебанием
(приводящим к увеличению коэффициента трения) понималось изменение
знака вертикальной составляющей скорости новой точки.

\quad Распознавание колебаний на этапе движения точек на  плоскости
происходит следующим образом. Для каждой координаты  каждой  точки
на всех шагах (кроме двух первых) проверяется, не достигла ли  эта
координата на предыдущем шаге своего экстремального значения, т.е.
не была ли она больше  (меньше)  как  своего  предыдущего,  так  и
последующего значений. Предполагается,  что  обнаружено  колебание
системы, если каждая координата каждой точки дважды достигла своих
экстремальных значений (очевидно, максимума и минимума).

\quad После первого колебания системы для каждой координаты  каждой
точки уже встретились по крайней мере два экстремальных  значения,
поэтому можно определить текущий размах колебания как  максимум  --
по всем координатам всех точек --  модулей  разностей  между  двумя
последними   экстремальными   значениями    координат.    Условием
завершения движения точек на плоскости служит  уменьшение  размаха
колебаний до достаточно малой величины $\chi L_{min}.$ Здесь
$\chi$ --  параметр метода $(0.1 \sim 0.2).$

\quad Изложенный алгоритм, применимый для построения плоских \break схем
произвольного конечного метрического  пространства,  был  дополнен
некоторыми  эвристическими  приемами,  основанными   на   графовой
природе  рассматриваемой  задачи.

\quad Прежде всего заметим,  что  для  подсчета  минимального  веса
путей между  всеми  парами  вершин  графа  использовался  алгоритм
Флойда~-~Варшалла [4].

\quad Для ускорения работы алгоритма  в  исходном  графе \break $G=<V,E,C>$
предварительно удалялись все вершины второй степени и --  описанным
выше  алгоритмом  --  строилась  плоская  схема  только  для  этого
множества вершин $V^*.$ Если в $G$ имелись  пары  вершин  степени  выше
второй, соединенные более чем одной цепью, то на каждой  из  этих
цепей выбиралось по одной вершине и эти вершины добавлялись к $V^*.$
Если же $G$ содержит простой цикл, только одна из вершин    которого
имеет  степень  выше  второй,  то  к $V^*$ добавляем  пару  вершин,
выбранных на этом цикле. Понятно, что вершины из $V\setminus V^*$
представляют
собой  объединения   внутренних   точек   цепей,   концы   которых
принадлежат $V^*.$

\quad Как оказалось,  для  построения  локально-оптимальной  схемы,\break
близкой к оптимальной, важен определенный порядок добавления новых
точек к уже построенной части  схемы.  Первой  рассматривается  та
пара вершин $u,v \in V^*$,  для которой расстояние $L(u,v)$ максимально. Если
схема  для  множества  точек  $W \subset V^*$   уже  построена,  то  следующей
рассматривается  такая  вершина $v \in V^* \setminus W,$
на  которой  достигается
максимум выражения $\min\{L(u,v)|~ u \in W\}.$

\quad После того как схема  для  множества  вершин $V^*$   построена,
вершины второй  степени  устанавливаются  на  плоскости  следующим
образом.  Внутренние  вершины  каждой  цепи  с  концами  в $v,u \in V^*$
изображаются на прямой,  соединяющей  изображения  вершин,  после
чего для схемы, содержащей  уже  все  вершины  графа,  выполняется
второй этап алгоритма добавления новой точки -- движение  точек  на
плоскости.  Впрочем,  этот  последний  этап   (обычно   достаточно
длительный, ввиду резкого  увеличения  числа  точек)  можно  и  не
выполнять, т.к. схема,  в  которой  многие  вершины  лежат  на
отрезках прямых, представляется более удобной.

\medskip
\centerline{\bf {4. Пpимеpы пpименения алгоpитма}}
\smallskip

\quad Понятно, что при использовании алгоритма, включающего  многие
эвристические  элементы,   нельзя   гарантировать   ни   получения
оптимальной   плоской   схемы,    ни    даже    сходимости.    Для
экспериментального  изучения  предложенного   алгоритма   (и   его
разнообразных  модификаций)   была   разработана   соответствующая
программа  (Pascal,  MS-DOS,  IBM  PC).   Рассмотренные   варианты
алгоритмов  тестировались  и  сравнивались  как  на   классических
примерах теории графов (полные и полные двудольные графы, деревья,
графы  правильных  многогранников,  граф  Петерсена),  так  и   на
построении схем конкретных транспортных  систем  (трамвайная  сеть
Иванова, метрополитены Москвы и Киева).

\quad На рис. 1 показаны  различные  варианты  плоских  схем  графа
Петерсена, полученные изложенным  выше  алгоритмом  при  различных
весах ребер. На рис. 2 показана полученная тем же  способом  схема
Московского метрополитена. Расстояния между станциями определялись
по их положению на карте города,  но  расстояния  между  соседними
станциями вне кольцевой линии полагались равными единице.

\quad При практическом применении программу, реализующую  алгоритм,
целесообразно  дополнить  блоком,  позволяющим  в  режиме  диалога
кор\- %-\pagebreak
%.\pagebreak
%\newpage

%\noindent
ректировать автоматически построенную схему в  целях  получения
более  наглядного  и  привычного  изображения.   Например,   может
оказаться,  что  автоматически  построенная   схема   транспортной
системы становится более похожей на ее карту только  после  осевой
симметрии и поворота. Корректировка  положения  отдельных  станций
также  желательна,  поскольку  в  полученной   схеме   изображения
некоторых вершин графа могут попасть на изображения  неинцидентных
им ребер. Так, в схеме на рис. 2 на отрезке,  соединяющем  станции
"Киевская" и "Парк культуры" (западная и юго-западная  станции  на
кольцевой линии), оказалась (с учетом точности  изображения  схемы
на принтере) не лежащая на нем  станция  "Смоленская"
Арбатско-Покровской линии.

\quad Как и следовало ожидать, время работы алгоритма быстро растет
с ростом числа вершин и  повышением  требований  к  точности.  При
этом время исполнения первого этапа алгоритма (установка вершин из
множества $V^\star $) зависит от мощности $V^\star,$ а второго --
от общего  числа
вершин. \pagebreak

\newpage
\pagebreak

\newpage
\noindent
Так,  при  использовании  процессора  80486SX  с  тактовой
частотой 33 МГц схемы на рис. 1 (все десять вершин  входят  в $V^\star$)
строились за 25~-~35 секунд, а схема на рис. 2 (111 вершин,  из  них
35 входят в $V^\star$) -- 40 минут, из которых 22 минуты заняло выполнение
второго этапа алгоритма. При этом полученная к концу первого этапа
схема  почти  не  отличалась  от   окончательной,   поэтому   -- при
последующей корректировке схемы в режиме  диалога  --  второй  этап
алгоритма можно и не выполнять.

\bigskip
\centerline{\bf Список использованной литеpатуpы}
\nopagebreak
\medskip

\noindent
1. {\it Бахвалов Н.С., Жидков Н.П., Кобельков Г.М.}
Численные методы. М.,\linebreak
\phantom {ны} 1987. 598 c.

\noindent
2. {\it  Емеличев В.А., Мельников О.Е., Саpванов В.И. и дp.}
Лекции по \linebreak
\phantom {ны}  теории  графов. М., 1990. 382 c.

\noindent
3. {\it Хаpтманеp Ф.}
Обыкновенные дифференциальные уравнения.  М., \linebreak
\phantom {ны} 1970. 720 c.

\noindent
4. {\it Warshall S.} Teorem on Boolean Matrices //
J. of the ACM. 1962. \No ~9.\hfill\break
\phantom {ны}  P. 11~-~12.

\end