Привет!
Дано:
N = число вершин в графе (max = 10)
M[NxN] = матрица смежности (или может не так называется ? не помню, но смысл в том, что Mij = 1, если между i и j есть дуга), генерится рэндомом
Надо теперь построить граф (в графическом представлении)...
Как бы если просто так их распихать, то будет ненаглядно, и много пересечений дуг...

Есть ли какие мысли по поводу того, как можно из матрицы M нарисовать граф (вершины графа - окружности (радиус R), дуги графа - линии) ?
Так, чтобы ниодна вершина не лежала на чужой дуге, пример - если расположить вершины по порядку:
1 2 3 4 5
и есть связь 1-3, то вершина 2 получится лежит на дуге 1-3...
Это первое обязательное условие.
Второе - минимальное (или примерно минимальное) число пересечений дуг...
Третье - время выполнения, не должно быть слишком тормозным (2-3 сек. максимум)

1) Расположи граф в виде правильного многоугольника, тогда ни одна вершина никогда не будет лежать на чужой дуге.
2) Что касается числа пересечений дуг, то ИМХО оно в общем случае не зависит от расположения вершин, если матрица смежности задаётся случайным образом.
3) Для 10 вершин ЛЮБОЙ алгоритм уложится в 2-3 секунды.

Так же хочу добавить, что есть 2 типа графов - орграф и неограф.
Для неографа достаточно заполнить половину матрицы. Береться матрица, приводиться условная линия с левого верхнего угла в правый нижний. Дальше заполняется верхняя половина и делается зеркальное отображение для нижней половины.
Для орграфа так же надо выяснить будит ли он сильносвязный или несильносвязный.
Сильносвязанные графы если для любой пары вершины Хi и Xj сущ пути из Хi в Xj, и из Xj в Хi.
Несильносвязанные - если для пары вершины Хi и Xj имеется пути из Хi в Xj либо из Xj в Хi.

Попробуй при написании программы учесть это.

Была идея разбить на независимые подграфы (раскраска вершин), но потом попровал расположить по кругу, как сказал Тиньков, в итоге вышло не так уж и плохо, как я думал...

Так что всем спасибо за отзывы!

Это сообщение отредактировал(а) p0s0l - 9.7.2004, 21:51