Какой алгоритм должен соответствовать этому конкретному графику

Question

конкретный вопрос здесь. Предположим, у вас есть график, где каждый Vertice определяет, сколько соединений они сусло должны еще вершин и следующие правила/свойства не применяются:

1- График может быть неполным (нет необходимости в каждом Vertice, чтобы иметь связь с каждый другой)

2 Между двумя вершинами могут быть два соединения , если они находятся в противоположных направлениях (например: точки B, B указывает на A).

3 Предположим, что они находятся на 2D-плоскости , не может быть пересечения соединений (даже не касательных).

4- Theres не интересует для кратчайшего пути, просто уважая свойства и зная, является ли решение уникальным или нет.

5- Там не может быть возможным решением

EDIT: Хорошо, ребята, извините за не специфичны. Я попытаюсь прояснить свою точку зрения: мне нужно дать несколько вершин, узнать, связан ли граф (если все точки имеют хотя бы соединение с графиком). Указанные вершины могут быть невозможны для построения графика, поэтому я хочу знать, есть ли решение, если решение уникально или нет или (наихудший сценарий), если нет возможного решения. Я думаю, что это разъясняет точки 4 и 5. Граф неориентирован, соединения не могут быть кривой, а только прямые. Узлы (вершины) фиксированы, у нас есть их позиция или вход W/E. Я хотел знать наилучший подход, и я занимаюсь исследованиями, и это проблема с подключением, хотя, возможно, какой-то конкретный alg может быть более эффективным для выполнения этой задачи. Это все, извините за поздний ответ

EDIT2: Хорошо ребята проблема будет отличаться, если мы считаем, что каждый Vertice на строки и столбца плоской матрицы, и они могут соединяться только с другими Вершины на же столбец или строка? Таким образом, это будет просто 90/180/270/360 прямых соединений. Это сильно сократило бы возможности?

Answer 1

Я собираюсь предположить, что вопрос: учитывая степень каждой вершины, выработайте график, который передает все указанные ограничения.

Я думаю, что вы можете уменьшить это до очень большой задачи программирования целых чисел - линейных ограничений, но с переменными, которые должны быть целыми (на самом деле либо 0 или 1), что затрудняет задачу, чем обычное линейное программирование.

Пусть неизвестные имеют вид Xij, где Xij равно 1, если есть ребро от узла i до узла j, а 0 в противном случае. Тогда требования к числу подключений соответствуют требованиям формы SUM_ {all i} Xij = K для некоторого K, зависящего от требования. Требование, чтобы график был плоским, сводится к требованию, чтобы граф не содержал двух известных графов в качестве подграфов - https://en.wikipedia.org/wiki/Graph_minor. Каждый возможный подграф затем создает ограничение, такое как X01 + X02 + ... < 5 - будет огромное количество этих ограничений - настолько большое, что для большого количества узлов, просто создающих все ограничения, может оказаться слишком дорогостоящим, чтобы быть практичным, не говоря уже о их решении. Количество ограничений возрастает как минимум на 6-й мощности числа узлов. Однако это многочлен, поэтому теоретически целесообразно записать MIP для решения - так что, возможно, это лучше, чем никакого алгоритма.

Answer 2

Предполагая, что вы просите нас:

Выясните, если это возможно, чтобы произвести один или-более направленные планарные графы таким образом, что каждая вершина имеет данный вне степени (не обязательно же из -дегре на вершину).

Предположим также, что вы хотите, чтобы график был подключен.

Если есть n вершины и степени вершин d_1 ... d_n то для вершины i есть C(n-1,d_i) = (n-1)!/((d_i)!*(n-1-d_i)!) возможные комбинации затраченных ребер из этой вершины. Взятие произведения всех этих комбинаций по всем вершинам даст вам верхнюю границу числа возможных графов.

Наивный подход:

• Сформировать все возможные графики.
• Отфильтровать графики только для связанных графиков.
• Заполните planarity test на графе, чтобы узнать, является ли он плоским (вы можете считать, что график не показан на этом шаге); отбросьте, если это не так.
• Прибыль!