Построить граф по матрице

From

Alexander Pashchenko (2:5062/17.212)

To

Alex Kozhushko

Date

2002-12-05T00:41:46Z

Area

RU.ALGORITHMS

Hello Alex.

04 Dec 02 08:58, Alex Kozhushko wrote to me:

 AP>> 1. О том, какой граф строить (орграф или простой) узнаём сравнив
 AK> половины
 AP>> матрицы относительно главной диагонали.
 AK> Смотря как определять неориентированный граф.
Наверное к часу ночи я потупел, но всё же: что означает вышеприведенная фраза?
Что граф можно определить по другой матрице?
 >> 2. Выясняем количестов вершин (из размерности таблицы) и расставляем их по
 >> кругу, на равном расстоянии друг от друга.
 AP>>    ЗЫ: Как разместить точки (вершины) равноудалённо друг от друга, по
 AK> кругу?
 AP>> Сдаётся мне, здесь пахнет x=sin(?) y=cos(?).
 AK> А есть варианты?
Ну мне бы хотелось узнать [поточнее] что писать на месте вопросов, да ещё, чтобы точки были на равном расстоянии друг от друга.
ЗЫ сейчас попробую набросать в Паскале, но мне кажется что ничего хорошего не  выйдет, слишком долго не спал :(((
 AP>>    ЗЗЫ: Или лучше разместить точки как-то подругому?
 AK>Да как угодно!
А всё же?
 AK>Это уже вопросы эстетики.
Т.е. можно и рандомно вершины разбросать?
 AK>Например, отсортировать вершины
В смысле?
 AK> (благо, транзитивное замыкание отношения смежности - предпорядок).
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^  (1)
Бррр. Наверно нам дискретку неполно преподают или мы не дошли, что есть (1)
 AP>> 3. Как лучше оформить вершины: записи-элементы в массиве, объекты... еще
 AP>> как-то. Мне кажется, что объекты, но может Алл знает, что-нибудь получше
 AK> ??? Объекты-то зачем? Какие операции для вершины можно инкапсулировать?
Допустим можно хранить список смежных вершин. Или его можно еще откуда-то узнать. (Вот блин, уже не соображаю).
 AK> Вершина - целое число. Координаты изображений вершин - массив записей.
Угу. А ты случаем не знаешь ссылок на хороший модуль/описание структур и алгоритмов/  динамических списков и/или динамических массивов.
А то как ни возьмусь делать, все себе путаница получается (главное на бумаге всё в ажуре).
 AK> Представление таблицы смежности - и то интереснее.
???
 AP>> 4. Как провести ребро: допустим граф имеет кратные рёбра. Соеденить две
 AK> точки
 AP>> линией просто, но как провести вторую/третью/... не затирая её, т.е. по
 AK> другой
 AP>> тректории? Точнее, как провести то еще пол-беды, а вот как
 AK> выбрать/создать
 AP>> новую.
 AK> А если сначала узнать, сколько линий надо проводить?
Ну знаю, если строю по матрице инцидентности.
 AK> Третьи точки дуг вычислятся сами.
Как сами? А если они наложаться друг на друга (в смысле дуги).
 AK> Еще смешнее - возле каждого ребра кратность указывать.
ГЕНИАЛЬНО! только надо с преподавательнией обговорить можно ли так, или ей иначе надо.
 AP>> ЗЗЫ блин, а для инцидентности то как строить?
 AK> Посмотреть, какая вершина с другой стороны ребра - Заратустра не
 AK> позволяет?
Уууу. Лучше уж я завтра перечитаю :)


ЗЫ извини за сумбур, но вторую ночь не сплю, а задачка больно интересная.
ЗЗЫ мож в мыло, а то больше никто не ответил.

Alexander

... np: silence
--- GoldED+/W32 1.1.5-020726
 * Origin: Имею свежие свопы на продажу: Win9x,Win2K,OS/2,... д (2:5062/17.212)