В общем понадобилось сделать следующее. Есть не ориентированный граф. Его надо уложить на плоскость, но если бы просто уложить, то я бы тут не спрашивал. Дополнительные требования следующие: 1) все рёбра на плоскости должны быть прямыми отрезками; 2) у графа на плоскости должно быть как можно меньше самопересечений. Возможно, что задача не сложная, но чего-то не соображаю.
Ну, вообще-то, задача сформулирована непонятно. А из того, что понятно, посмотри как отрисовываются хордовые диаграммы, а наименьшее пересечение можно через двудольные графы посчитать. В целом непонятно, о каких графах идет речь? Случайный ориентированный? Записать в виде матрицы смежности и посмотреть, приводиться ли она к треугольному виду? что значат эти "должны быть прямыми"? Шаг сетки грамотно подобрать, что бы как можно больше вершин легло? Непонятно
Нет, граф не ориентированный. Вершины графа -- точки на плоскости, рёбра -- линии, соединяющие эти точки, так вот, эти линии должны быть отрезками прямых. Причём здесь сетка? Нет никакой сетки. В общем попробую сформулировать получше, Есть не ориентированный граф и есть плоскость, нужно каждой вершине графа сопоставить точку на плоскости, а каждому ребру графа сопоставить отрезок, соединяющий соответствующие точки на плоскости так, чтобы пересечений разных отрезков (сопоставленных рёбрам) было минимально возможное количество.
По любому, если две точки соединить, будет отрезок. Т.е. тут всего лишь говориться, что дуги нельзя, т.е. многомерное векторное пространство надо отобразить в плоскость, но все точки сучайы. Так, а как метрику расстояния тогда ввести? Меньше отрезков, это что? Что бы на отрезке еще точки лежали? Ну так может взять вершину и по кругу от нее прямыми лучами настрелять, меняя угол? Радаром. Рекурсивно, взяли вершину, пробежались по переменной "угол", посчитали пригадлежность точек прямой. Но все же, я бы думал в сторону хордовых диаграмм. Расположил бы все точки по окружности, потом соединил с минимальным количеством перекрестных путей, ну и думал бы как свернуть окружность в другую, с меньшим количеством точек на окружности. --- Сообщение объединено, 10 фев 2022 --- пронумеровали вершины, расположили тем самым на прямой. Построили дуги - ребра между вершинами. Отсортировали по количеству правых и левых соседей, Разбили на классы. Может префиксно все получиться закодировать. В конце концов, у Вас же многомерные вектора - они же кодовые слова. --- Сообщение объединено, 10 фев 2022 --- Или если подумать про матрицы смежности и граничные случаи. Матрица из случайных нулей и единиц симметрична, ведь граф не ориентированный. В самом идеальном случае по одной единичке в строке и столбце. Как так накидывать единиц, что бы не создавать пересечений? --- Сообщение объединено, 10 фев 2022 --- Понял, что меня смущает в задаче. вот вы вырезали из листа бумаги окружность, вот разрезали на полоски. Самопересечения будут считаться в рамках одной полоски, или сумарно по всем полоскам? --- Сообщение объединено, 10 фев 2022 --- и могут ли быть изолированные, не соединенные ни с кем, вершины? --- Сообщение объединено, 10 фев 2022 --- Можно каждой вершине сопоставить число - количество ребер из нее. Представить это как гистограмку и подумать, как она будет меняться от случая к случаю. Когда мы имеем дело с солнышком, и когда идеальный случай попарного разбиения на классы эквивалентности.
