"Красивая" визуализация графа. Уточнение.

From

Evgenij Masherov (2:5020/175.2)

To

Evgenij Masherov

Date

2002-07-25T20:26:10Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Tue Jul 23 2002 23:34, Evgenij Masherov wrote to Nickita A Startcev:

 
 NAS>> Какие есть идеи по красивой визуализации графа?
 NAS>> Для  каждой пары вершин известно "псевдорасстояние" между ними,
 NAS>> хочется чтоб "близкие" вершины отображались рядом, а далекие - далеко.

 
 EM>  Лично мне в похожей задаче весьма помогли элементы собственных векторов
 EM> матрицы смежности графа, принимаемые за координаты точек по Х и У. Вот
 EM> только кто поможет моему склерозу - это были С.В. для максимальных или
 EM> минимальных С.З.?

 
Рассмотрим задачу минимизации суммы квадратов длин отресков, соединяющих
вершины графа.
SUM ij A(i,j)*((x(i)-x(j))^2+(y(i)-y(j))^2)
A(i,j) - матрица смежности графа.
Возьмем вместо нее иную матрицу В, из диагональных элементов которой вычтены
степени соответствующих вершин (поскольку эти элементы умножаются на ноль -
это не изменит задачу), ограничимся на первом этапе минимизацией лишь по Х, и
раскроем скобки. После приведения подобных увидим, что задача эквивалентна
максимизации квадратичной формы xtBx, что достигается для х, равного
собственному вектору В, соответствующему максимальному собственному значению.
Для минимизации по у возьмем следующий вектор, по построению он будет
ортогонален первому. Можно так и далее...

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)