-3

这里的具体问题。假设您有一个图，其中每个顶点指定它们必须与另一个顶点有多少连接，并且适用以下规则/属性：

1-图形可能不完整（不需要每个顶点都相互连接）

2-只有当两个顶点的方向相反时，它们之间才能有两个连接（例如：A 点做 B，B 点到 A）。

3-假设它们在2D 平面上，不能有交叉连接（甚至没有切线）。

4-对最短路径没有兴趣，只需尊重属性并知道解决方案是否唯一。

5-不可能有解决办法

编辑：好的，抱歉没有具体说明。我将尝试在这里澄清我的观点：我想要做的是给定多个顶点，知道一个图是否连接（如果所有点都至少与图有一个连接）。给定的顶点可能无法绘制它的图表，所以我想知道是否有解决方案，解决方案是否唯一，或者（最坏的情况）是否没有可能的解决方案。我认为这阐明了第 4 点和第 5 点。图形是无向的，连接不能弯曲，只有直线。节点（顶点）是固定的，我们有它们的位置或 W/E 输入。我想知道最好的方法，我一直在研究，这是一个连接问题，尽管也许一些特定的算法可能更有效地完成这项任务。就是这样，抱歉回复晚了

EDIT2：好吧，如果我们认为每个顶点都在平面矩阵的行和列上并且它们只能与同一列或行上的其他顶点连接，那么问题会有所不同吗？所以它只是 90/180/270/360 直接连接。这会大大缩短可能性，对吗？

4

2 回答 2

0

假设您要求我们：

找出是否有可能生成一个或多个有向平面图，以使每个顶点具有给定的出度（不一定每个顶点具有相同的出度）。

我们还假设您希望连接图形。

如果存在n顶点并且顶点具有度数d_1 ... d_n，那么对于顶点，可能i存在C(n-1,d_i) = (n-1)!/((d_i)!*(n-1-d_i)!)来自该顶点的出边的组合。对所有顶点进行所有这些组合的乘积将为您提供可能图形数量的上限。

天真的方法是：

  • 生成所有可能的图表。
  • 过滤图表以仅具有连接的图表。
  • 对图进行平面性测试，判断是否为平面（这一步可以认为图是无向的）；如果不是则丢弃。
  • 利润！
于 2016-03-30T00:50:25.893 回答
0

我将假设问题是：给定每个顶点的度数，计算出一个通过所有给定约束的图。

我认为您可以将其简化为一个非常大的整数规划问题 - 线性约束，但变量需要是整数（实际上是 0 或 1），这使得问题比普通的线性规划要困难得多。

令未知数为 Xij 的形式，如果从节点 i 到节点 j 有一条边，则 Xij 为 1，否则为 0。然后，对连接数的要求相当于 SUM_{all i}Xij = K 形式的要求，其中一些 K 取决于要求。图是平面的要求减少到图不包含两个已知图作为子图的要求 - https://en.wikipedia.org/wiki/Graph_minor. 然后，每个可能的子图都会产生一个约束，例如 X01 + X02 + ... < 5 - 会有大量这些约束 - 如此之大，以至于对于大量节点来说，简单地产生所有约束可能太昂贵而无法实用，更不用说解决它们了。约束的数量至少是节点数量的 6 次方。然而，这是多项式，所以理论上写下要解决的 MIP 是可行的 - 所以这也许总比没有算法好。

于 2016-03-29T18:40:12.380 回答