Главная страница


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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 Построить граф по матрице   Alexander Pashchenko   03 Dec 2002 22:21:28 
 Re: Построить граф по матрице   Alex Kozhushko   04 Dec 2002 09:58:10 
 Построить граф по матрице   Alexander Pashchenko   05 Dec 2002 01:41:46 
 Re: Построить граф по матрице   Andrey Belyakov   05 Dec 2002 16:40:41 
Архивное /ru.algorithms/38923dee78a6.html, оценка 2 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional