如何找到最大欧拉子图？
How to find maximal eulerian subgraph?
如何找到给定图的最大欧拉子图？ "maximal" 是指具有最大边数、顶点数或两者的子图。我的想法是找到循环的基础 space 并以适当的方式组合基础循环，但我不知道该怎么做（这是否是个好主意）。
更新。源图已连接。
一些想法。图是欧拉的当且仅当它是连通的（可能有孤立的顶点）并且所有顶点的度数都是偶数。
通过移除奇数度顶点对之间的（最短）路径来满足第二个条件'easy'。
连通性有问题，因为删除边会产生不连通的图。
一个例子表明'simple'（贪婪）解决方案不容易产生。通过将每条边分成两条（或更多条）边来修改完整图 K5。取两个这些修改后的 K5 图，并从每个图取两个顶点（第一个是 A、B，第二个是 C、D）。连接 A-C 和 B-D。贪心方法会删除这些添加的边，因为它们是最短路径。与该图变得不相关。解决方案是删除路径 A-B 和 C-D。
在我看来，算法应该在删除边的同时注意子图的连通性。当然，算法应该保留奇数度顶点的每个子集，其中没有一对用于删除它们之间的路径，应该具有大于子集基数的连通性。
我会尝试（进行测试）具有优化的递归蛮力解决方案。 O 是奇数度顶点的列表。
def remove_edges(O, G):
if O is empty:
return solution
for f in O:
for t in O\{f}":
G2 = G without path edges between (f,t)
if G2 is unconnected:
continue
return remove_edges(O\{f,t}, G2)
优化可以是按具有最短路径的顶点对集合 O 和 O{f} 进行排序。这可以通过在删除边之前从 O 中找到所有顶点对之间的最短长度来完成。这可以通过每个 O 顶点的 BFS 来完成。
1979年证明，判断给定图是否包含生成欧拉子图是NP-complete。
参考：W. R. Pulleyblank，关于图表的注释
欧拉图，J. Graph Theory 3，1979，pp.
309–310,
请参考this
寻找图的生成欧拉子图（如果存在）的最大尺寸（边数）是一个活跃的研究领域。
如何找到给定图的最大欧拉子图？ "maximal" 是指具有最大边数、顶点数或两者的子图。我的想法是找到循环的基础 space 并以适当的方式组合基础循环，但我不知道该怎么做（这是否是个好主意）。
更新。源图已连接。
一些想法。图是欧拉的当且仅当它是连通的（可能有孤立的顶点）并且所有顶点的度数都是偶数。
通过移除奇数度顶点对之间的（最短）路径来满足第二个条件'easy'。
连通性有问题，因为删除边会产生不连通的图。
一个例子表明'simple'（贪婪）解决方案不容易产生。通过将每条边分成两条（或更多条）边来修改完整图 K5。取两个这些修改后的 K5 图，并从每个图取两个顶点（第一个是 A、B，第二个是 C、D）。连接 A-C 和 B-D。贪心方法会删除这些添加的边，因为它们是最短路径。与该图变得不相关。解决方案是删除路径 A-B 和 C-D。
在我看来，算法应该在删除边的同时注意子图的连通性。当然，算法应该保留奇数度顶点的每个子集，其中没有一对用于删除它们之间的路径，应该具有大于子集基数的连通性。
我会尝试（进行测试）具有优化的递归蛮力解决方案。 O 是奇数度顶点的列表。
def remove_edges(O, G):
if O is empty:
return solution
for f in O:
for t in O\{f}":
G2 = G without path edges between (f,t)
if G2 is unconnected:
continue
return remove_edges(O\{f,t}, G2)
优化可以是按具有最短路径的顶点对集合 O 和 O{f} 进行排序。这可以通过在删除边之前从 O 中找到所有顶点对之间的最短长度来完成。这可以通过每个 O 顶点的 BFS 来完成。
1979年证明，判断给定图是否包含生成欧拉子图是NP-complete。 参考：W. R. Pulleyblank，关于图表的注释 欧拉图，J. Graph Theory 3，1979，pp. 309–310,
请参考this
寻找图的生成欧拉子图（如果存在）的最大尺寸（边数）是一个活跃的研究领域。