Если у меня есть график разумного размера (например, ~ 100 узлов, ~ 40 ребер, выходящих из каждого узла), и я хочу представить его в R ^ 3 (т.е. сопоставить каждый узел точке в R ^ 3 ипроведите прямую линию между любыми двумя узлами, которые связаны в исходном графике) таким образом, чтобы было легче понять его структуру, что, по вашему мнению, могло бы стать хорошим критерием рисования?
Я знаю этот вопроснекорректна;это не объективно.Идея, лежащая в основе этого, легче понять в крайнем случае.Предположим, у вас есть связанный граф, в котором каждый узел соединяется с двумя и только с двумя другими узлами, за исключением двух узлов, которые соединяются только с одним другим узлом.Нетрудно видеть, что этот график, нарисованный в R ^ 3, может быть нарисован как прямая линия (узлы разбросаны по линии).Тем не менее, его можно нарисовать так, чтобы практически невозможно было увидеть его очень простую структуру, например, «развернув» его как можно больше вокруг некоторой фиксированной точки в R ^ 3.Итак, для этого простого случая ясно, что простое трехмерное представление - это прямая линия.Однако неясно, что это за свойство simplicity в общем случае.
Итак, вопрос: как бы вы определили это свойство простоты ?
Я доволен любым ответом, будь то определение «простоты», вычислимое для графов, или жадный приближенный алгоритм, который преобразует графы и сходится к «более простым» трехмерным представлениям.
Спасибо!
РЕДАКТИРОВАНИЕ
В то же время я применил идеи графического рисования , предложенные в ответе, на практике и написалПрограмма OCaml / openGL для имитации того, как может получиться наложение электрической отталкивающей силы между узлами (закон Кулона) и пружинное поведение на ребрах (закон Гука).Я разместил видео на YouTube .Видео начинается с начального графа из 100 узлов, каждый с приблизительно 1-2 исходящими ребрами, и случайным образом размещает узлы в трехмерном пространстве.Затем все силы, которые я упомянул, введены в действие, и система остается перемещаться, подчиняясь этим силам.В начале график - беспорядок, и очень трудно увидеть структуру.Ближе к концу ясно, что график почти линейный.У меня также есть опыт работы с графиками большего размера, но иногда геометрия графика - это просто беспорядок, и независимо от того, как вы его изобразите, вы не сможете ничего визуализировать.А вот еще более экстремальный пример с 500 узлами .