Как найти максимальный эйлеровый подграф?

Question

Как найти максимальный эйлеровый подграф заданного графа? Под «максимальным» я подразумеваю подграф с максимальным числом ребер, вершин или обоих. Моя идея состоит в том, чтобы найти основы пространства циклов и правильно комбинировать базовые циклы, но я не знаю, как это сделать (и это хорошая идея или нет).

UPD. Исходный граф подключен.

Answer 1

Некоторые мысли. Граф является эйлеровым, если он связан (с возможными изолированными вершинами), и все вершины имеют четную степень.

Это «легко» для удовлетворения вторых критериев путем удаления (кратчайших) путей между парами вершин нечетной степени.

Связь является проблематичной, так как удаление краев может привести к несвязанной диаграмме.

Пример, который показывает, что «простое» (жадное) решение не просто произвести. Измените полный граф 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 перед удалением ребер. Это может быть сделано BFS из каждой вершины O.