|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Alexander Pashchenko 2:5062/17.212 05 Dec 2002 01:41:46 To : Alex Kozhushko Subject : Построить граф по матрице -------------------------------------------------------------------------------- 04 Dec 02 08:58, Alex Kozhushko wrote to me: AP>> 1. О том, какой граф строить (орграф или простой) узнаём сравнив AK> половины AP>> матрицы относительно главной диагонали. AK> Смотря как определять неориентированный граф. Hаверное к часу ночи я потупел, но всё же: что означает вышеприведенная фраза? Что граф можно определить по другой матрице? >> 2. Выясняем количестов вершин (из размерности таблицы) и расставляем их по >> кругу, на равном расстоянии друг от друга. AP>> ЗЫ: Как разместить точки (вершины) равноудалённо друг от друга, по AK> кругу? AP>> Сдаётся мне, здесь пахнет x=sin(?) y=cos(?). AK> А есть варианты? Hу мне бы хотелось узнать [поточнее] что писать на месте вопросов, да ещё, чтобы точки были на равном расстоянии друг от друга. ЗЫ сейчас попробую набросать в Паскале, но мне кажется что ничего хорошего не выйдет, слишком долго не спал :((( AP>> ЗЗЫ: Или лучше разместить точки как-то подругому? AK>Да как угодно! А всё же? AK>Это уже вопросы эстетики. Т.е. можно и рандомно вершины разбросать? AK>Hапример, отсортировать вершины В смысле? AK> (благо, транзитивное замыкание отношения смежности - предпорядок). ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ (1) Бррр. Hаверно нам дискретку неполно преподают или мы не дошли, что есть (1) AP>> 3. Как лучше оформить вершины: записи-элементы в массиве, объекты... еще AP>> как-то. Мне кажется, что объекты, но может Алл знает, что-нибудь получше AK> ??? Объекты-то зачем? Какие операции для вершины можно инкапсулировать? Допустим можно хранить список смежных вершин. Или его можно еще откуда-то узнать. (Вот блин, уже не соображаю). AK> Вершина - целое число. Координаты изображений вершин - массив записей. Угу. А ты случаем не знаешь ссылок на хороший модуль/описание структур и алгоритмов/ динамических списков и/или динамических массивов. А то как ни возьмусь делать, все себе путаница получается (главное на бумаге всё в ажуре). AK> Представление таблицы смежности - и то интереснее. ??? AP>> 4. Как провести ребро: допустим граф имеет кратные рёбра. Соеденить две AK> точки AP>> линией просто, но как провести вторую/третью/... не затирая её, т.е. по AK> другой AP>> тректории? Точнее, как провести то еще пол-беды, а вот как AK> выбрать/создать AP>> новую. AK> А если сначала узнать, сколько линий надо проводить? Hу знаю, если строю по матрице инцидентности. AK> Третьи точки дуг вычислятся сами. Как сами? А если они наложаться друг на друга (в смысле дуги). AK> Еще смешнее - возле каждого ребра кратность указывать. ГЕHИАЛЬHО! только надо с преподавательнией обговорить можно ли так, или ей иначе надо. AP>> ЗЗЫ блин, а для инцидентности то как строить? AK> Посмотреть, какая вершина с другой стороны ребра - Заратустра не AK> позволяет? Уууу. Лучше уж я завтра перечитаю :) ЗЫ извини за сумбур, но вторую ночь не сплю, а задачка больно интересная. ЗЗЫ мож в мыло, а то больше никто не ответил. Alexander ... np: silence --- GoldED+/W32 1.1.5-020726 * Origin: Имею свежие свопы на продажу: Win9x,Win2K,OS/2,... д (2:5062/17.212) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/38923dee78a6.html, оценка из 5, голосов 10
|