构建一个图，使得两个节点之间的最大距离（边数）等于二。

Question

我需要使用Python构建一个算法：

1. 该算法必须构建一个图，给定节点数n的情况下，边数最少。
2. 我们必须使用最多两条边从一个节点到另一个节点。
3. 有些节点不能相邻。
4. 保证对于给定的输入，我们将能够找到满足上述三个条件的解决方案。

函数签名可以是createGraph(n: int,forbidenEdge: list[int]) -> list[int]

一个例子：n = 4，forbidenEdge = [[1,3]]

该函数返回必须构建的边，以便在图中具有最少的边数。

对于给定的示例，我们有以下可能的输出（有时我们可以有多个输出）：[[1, 2],[4, 2],[2, 3]]

我不确定我想要实现的解决方案是否正确。

如果我们没有任何限制，或者至少有一个节点可以连接到任何节点，则最小边数等于（n-1）。我们可以选择一个可以连接到所有其他节点的节点。问题在于，当没有节点可以连接到所有其他节点时。为此，我正在考虑创建以下算法，但我不确定它是否正确。对于这种情况，我考虑以下算法：

我们必须检查每个节点可以进行的连接数量，并根据此数量将它们排序到列表中。我们必须检查不能连接到节点中心的节点是否能够连接到所有其他节点（如果可能，我们连接可以连接到节点中心的节点，而将其他节点连接到彼此...我们打印连接），如果不可能，我们必须选择另一个节点中心，即排序列表中的下一个节点。我们重复此过程，直到找到一个节点中心，选择该节点中心后，可以以一种方式在节点之间建立边缘，从任何节点都可以通过两个边缘移动到另一个节点。

对于这个算法，如果我们有n = 4，forbidenEdge = [[1,3],[2,4]] ... 节点3可以是节点中心。节点1不能连接到节点中心，因此它连接到所有其他节点。因此，我们的输出为：[[1,2],[1,4],[2,3],[3,4]]。

这个算法对于任何n和任何forbidenEdge列表都能正确吗？我该如何证明呢？

- Alucard

---

你尝试过实现它吗？如果没有，请尝试一下！如果有，发生了什么？在不同的测试用例上运行代码通常是验证算法是否有效的一种方法。如果这是为了竞争性编程，问题提示通常会提供测试用例，您可以针对这些测试用例运行算法，并告诉您是否出错。 - CoderTang

给定直径不超过2的图形（V，E），我们想要找到最小的E'子集，使得图形（V，E'）的直径不超过2。似乎很困难，你有在线评测链接吗？ - David Eisenstat

有向图还是无向图？ - chrslg

这里肯定需要使用路径压缩。 - Julia

他指的是连接到所有/大多数其他节点的节点。它以这种方式促进了直接连接到它的节点之间的连接，起到了中央枢纽的作用。在微不足道的情况下，您可以选择一个节点作为“节点中心”，该节点可以连接到所有其他节点，然后您的图形看起来像一个以所选节点中心为中心的星形。 - MangoNrFive

Answer 1

简而言之：您可以通过连接矩阵与其自身的点积来计算双边跳数。单边跳数就是连接矩阵本身。

---

不是解决方案，但有一些考虑因素，希望对您寻找解决方案有所帮助：

考虑您是否有一个连接矩阵（每个节点都有一列和一行，如果节点之间有边，则为1，否则为0）。例如，对于禁止的边缘[[1, 2], [3, 4]和n = 4，连接矩阵如下：

[
    [0, 0, 1, 1],
    [0, 0, 1, 1],
    [1, 1, 0, 0],
    [1, 1, 0, 0]
]

如果您已经了解两个节点之间单边跳的数量，那么通过连通性矩阵本身（到目前为止都很平凡）就可以知道。但更有趣的是，您可以通过将连通性矩阵与自身进行点积来计算两个节点之间的双边跳数！这个想法是，点积基本上计算了两个节点之间的共同邻居。

现在的目标基本上是删除边缘（在连通性矩阵中将数字设置为零），直到不能再删除为止。一个算法可能如下所示：

1. 用对角线为0初始化你的连通矩阵cm（一个节点永远不会直接连接到自己，即使允许这样做，当目标是最少边数时，该边也会被修剪，因为它不会添加任何有用的连接到图中）。
2. 在连通性矩阵中将所有禁止边的节点对设置为0。
3. 通过计算两个边跳数（numpy.dot(cm, cm)）来计算节点之间的路径总数。
4. 通过添加一次边跳（连通矩阵）和二次边跳（步骤3中计算的）来计算节点之间的总路径数。
5. 如果步骤4中计算出的矩阵中的任何数字为0，则连通矩阵无效，如果这发生在第一次迭代中，则问题无法解决，或者最后删除的边使连通矩阵无效（如果正确实现，则不应发生）。
6. 现在来到难点，选择一个节点对从连通矩阵中删除并重复步骤3-6，直到不能再删除边为止。

对于步骤6，我有一些想法，可以通过在numpy数组上进行过滤来实现。

1. 显然只能移除有边相连的边（在连通性矩阵中为1）。
2. 只有当矩阵计算出的值至少为2时，才能移除边。否则你会删除最后一个连接。
3. 不能删除那些是非直接连接的节点对的两条边跳的最后一个连接。我还没有找到直接检查它的方法。

很遗憾这并不能解决你的问题，但也许你或其他人可以在此基础上进行改进或灵感得到启发。可能还有更多的数学原理可以被利用，比如从点积计算两步跳的数量。结合快速的numpy实现，则可以采用聪明的暴力方法（当然也取决于节点的最大数量）。

- MangoNrFive

---

充其量，这只是迈向另一个算法的一步。但问题并不在于另一个算法。他们已经有了一个算法，问题是它是否正确以及如何证明它的正确性。我不明白这个答案怎么可能有用。 - Kelly Bundy

你说得对，它并没有回答算法是否可以被证明是正确的问题。但是有人可能会争辩，根本问题是如何解决图形问题，而证明Alucard算法只是其中一种方法。我发表了我的答案，因为我得出了一些（至少对我来说）有趣的结论。我认为这些结论对Alucard和其他人也可能很有趣，即使它们与确切的问题没有直接关系。如果我在那个假设上犯了错误，我很抱歉。 - MangoNrFive