1

给定一个连通的无向顶点标记图，图中的一条边，以及某个数n ≥ 2，是否有一种有效的算法可以找到包含该边的所有n阶连通（但不一定是诱导）子图？

我认为要做的显而易见的事情是对边进行一种递归遍历，从给定的边开始，并注意没有一条路径使用一条边超过一次（尽管允许多次访问同一个顶点）。遍历每条边后，我检查路径上有多少个顶点。如果它小于n，我继续遍历。如果它等于n，我产生与路径对应的子图并继续遍历。如果它大于n，我停止。但是，这种方法效率低下，因为它一遍又一遍地生成许多相同的子图。

（如果重要的话，原始图中的所有顶点都是 8 度的，我将寻找高达 15 的子图顺序。）

4

1 回答 1

1

David Eisenstat 对我的问题的评论建议调整他对类似问题的回答。下面的伪代码就是那个适配，我已经验证过它是有效的，并且不会多次生成任何一个子图。其中它n指的是要返回的子图的顺序（如果要返回所有子图，可以省略对其的测试），并neighbours(e)表示与 共享端点的边集e。首次调用该函数时，subgraphEdges参数应包含给定的边，其余参数应相应设置。

GenerateConnectedSubgraphs(edgesToConsider,
                           子图顶点，
                           子图边，
                           邻接边缘）：
    让 edgeCandidates ← edgesToConsider ∩ neighbouringEdges
    如果边缘候选者 = ∅
        如果 |子图顶点| = n
           产量（子图顶点，子图边）
    别的
        选择一些 e ∈ edgeCandidates
        GenerateConnectedSubgraphs(edgesToConsider ∖ {e},
                                   子图顶点，
                                   子图边，
                                   邻接边缘）
        GenerateConnectedSubgraphs(edgesToConsider ∖ {e},
                                   subgraphVertices ∪ 端点（e），
                                   subgraphEdges ∪ {e}，
                                   neighbouringEdges ∪ neighbours(e))
于 2013-06-06T11:06:04.613 回答