如何将无向图划分为最少数量的子路径？

这个问题可以通过图论中的欧拉路径相关定理解决，核心思路基于图中奇点（度数为奇数的顶点）的数量确定最少子路径数，具体如下：

核心原理 #

无向图中奇点的数量必然是偶数，以此为基础：

• 若图连通且奇点数量为0：整个图可被1条欧拉回路覆盖（最少子路径数为1），回路能遍历所有边且不重复。
• 若图连通且奇点数量为2k（k≥1）：最少需要k条路径覆盖所有边，每条路径都是连接一对奇点的欧拉路径。
• 若图不连通：对每个连通分支分别计算最少路径数，最终结果为各分支路径数之和。

算法实现步骤 #

1. 预处理：统计奇点与连通性 #

• 遍历所有顶点，统计每个顶点的度数，筛选出所有奇点。
• 用DFS/BFS判断图的连通性，若不连通则拆分出所有连通分支。

2. 构造最少路径 #

针对每个连通分支：

• 若奇点数量为0：直接用Hierholzer算法构造欧拉回路，这就是唯一的子路径。
• 若奇点数量为2k：
  1. 将奇点两两配对（配对方式不影响最少路径数，可任意选择），每对奇点间添加一条虚拟边（仅用于构造欧拉回路，不参与实际路径）。
  2. 对添加虚拟边后的图（此时奇点数量为0），用Hierholzer算法构造欧拉回路。
  3. 遍历欧拉回路，每当遇到虚拟边时拆分回路为独立路径，去掉虚拟边后得到原图的k条子路径。

3. Hierholzer算法核心逻辑（伪代码） #

def hierholzer(start):
    stack = [start]
    path = []
    while stack:
        current = stack[-1]
        if adj[current]:  # adj为存储未访问边的邻接表
            next_node = adj[current].pop()
            adj[next_node].remove(current)  # 无向图需删除反向边
            stack.append(next_node)
        else:
            path.append(stack.pop())
    return path[::-1]  # 反转得到正确路径顺序

结合你的示例说明 #

你的示例图中，奇点为B（度数1）和I（度数1），共2个（k=1），因此最少只需1条子路径即可覆盖所有边，例如：B-A-C-D-E-G-F-C-I。你给出的两种划分（BACI+CDEGFC、BACDEGFC+CI）是可行的覆盖方式，但并非最优解。

内容的提问来源于stack exchange，提问作者niico