| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Построение графа по матрице |
| Автор: p0s0l 4.7.2004, 15:47 |
| Привет! Дано: N = число вершин в графе (max = 10) M[NxN] = матрица смежности (или может не так называется ? не помню, но смысл в том, что Mij = 1, если между i и j есть дуга), генерится рэндомом Надо теперь построить граф (в графическом представлении)... Как бы если просто так их распихать, то будет ненаглядно, и много пересечений дуг... Есть ли какие мысли по поводу того, как можно из матрицы M нарисовать граф (вершины графа - окружности (радиус R), дуги графа - линии) ? Так, чтобы ниодна вершина не лежала на чужой дуге, пример - если расположить вершины по порядку: 1 2 3 4 5 и есть связь 1-3, то вершина 2 получится лежит на дуге 1-3... Это первое обязательное условие. Второе - минимальное (или примерно минимальное) число пересечений дуг... Третье - время выполнения, не должно быть слишком тормозным (2-3 сек. максимум) |
| Автор: Тиньков 6.7.2004, 08:26 |
| 1) Расположи граф в виде правильного многоугольника, тогда ни одна вершина никогда не будет лежать на чужой дуге. 2) Что касается числа пересечений дуг, то ИМХО оно в общем случае не зависит от расположения вершин, если матрица смежности задаётся случайным образом. 3) Для 10 вершин ЛЮБОЙ алгоритм уложится в 2-3 секунды. |
| Автор: Zaman 6.7.2004, 22:59 |
| Так же хочу добавить, что есть 2 типа графов - орграф и неограф. Для неографа достаточно заполнить половину матрицы. Береться матрица, приводиться условная линия с левого верхнего угла в правый нижний. Дальше заполняется верхняя половина и делается зеркальное отображение для нижней половины. Для орграфа так же надо выяснить будит ли он сильносвязный или несильносвязный. Сильносвязанные графы если для любой пары вершины Хi и Xj сущ пути из Хi в Xj, и из Xj в Хi. Несильносвязанные - если для пары вершины Хi и Xj имеется пути из Хi в Xj либо из Xj в Хi. Попробуй при написании программы учесть это. |
| Автор: p0s0l 9.7.2004, 21:50 |
| Была идея разбить на независимые подграфы (раскраска вершин), но потом попровал расположить по кругу, как сказал Тиньков, в итоге вышло не так уж и плохо, как я думал... Так что всем спасибо за отзывы! |