algorithm - n 个顶点的图，其直径为 3，补集的直径也为 3？

Question

是否有可能对每个n都有这样的图？如果是这样，是否有可能以编程方式生成这样的图？

提前致谢。

Answer 1

这对于 n < 4 是不可能的，因为您至少需要 4 个节点才能创建 3 的距离。

但是对于 n>= 4 总是可能的。

您可以选择任何顶点 A、B 和 C 并且在 A 和所有其他顶点之间有边，除了C，并且在B和C之间多了一条边​​。这可以可视化如下:

假设 D 是任何不等于 A、B 或 C 的顶点.因为我们至少有 4 个顶点，所以至少有这样一个顶点。

这张图的距离为3

这是因为每对顶点(不包括 C)表示的距离最多为 2，因为这些顶点通过 A 连接。 C只能通过路径B、A到达其他顶点，当目标为D .

因此距离为3。

补图距离为3

在补充图中...之间的距离:

• A 和C 为 1
• B和D为1
• C和D为1
• A 和 D 为 2(通过 C)
• B 和 C 为 2(通过 D)
• A 和 B 是 3(通过 C 和 D)

这列出了所有可能的无序对，包括 A、B、C 和 D。然后保留由不涉及A、B 或C 的任何对表示的距离:这样的对是补图中的边，并且所以它们的距离为 1。

因此补图的距离为3，用顶点A和B表示。

编程

给定一个顶点列表 V，您可以按如下方式进行(伪代码，边表示为括号内两个顶点的元组):

a = V[0]
b = V[1]
c = V[2]
edges = [ (b,c) ]
for each d in V:
    if d != a && d != c:
        edges.append( (a,d) )