Comment trouver le sous-graphe eulérien maximal d'un graphe donné? Par "maximal", j'entends un sous-graphe avec un nombre maximal d'arêtes, de sommets, ou les deux. Mon idée est de trouver la base de l'espace du cycle et de combiner les cycles de base d'une manière appropriée, mais je ne sais pas comment le faire (et c'est une bonne idée ou non).Comment trouver le sous-graphe eulérien maximal?
UPD. Le graphique source est connecté.
Quelques pensées. Le graphe est eulérien ssi il est connecté (avec des sommets isolés possibles) et tous les sommets ont un degré pair.
Il est 'facile' de satisfaire le deuxième critère en supprimant (les plus courts) les chemins entre les paires de sommets de degré impair.
La connectivité est problématique car la suppression des arêtes peut produire un graphe non connecté.
Un exemple qui montre qu'une solution «simple» (gourmande) n'est pas facile à produire. Modifiez le graphe complet K5 en divisant chaque arête en deux arêtes (ou plus). Prenez deux graphes K5 modifiés et prenez chacun deux sommets (A, B du premier et C, D du second). Connectez A-C et B-D. Une approche gourmande supprimerait ces bords ajoutés car ce sont les chemins les plus courts. Avec ce graphique devient déconnecté. La solution serait de supprimer les chemins A-B et C-D.
Il me semble que l'algorithme devrait faire attention à la connectivité sous-graphique tout en supprimant les bords. Pour sûr, l'algorithme devrait préserver que chaque sous-ensemble de sommets de degré impair, dont aucune paire n'est utilisée pour supprimer le chemin entre eux, devrait avoir une connectivité plus grande que la cardinalité du sous-ensemble.
Je voudrais essayer (pour un test) avec une solution de force brute récursive avec optimisation. O est la liste des sommets de degré impair.
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)
L'optimisation peut être d'ordonner des ensembles O et O {f} par des sommets qui ont des chemins les plus courts. Cela peut être fait en trouvant les longueurs les plus courtes entre toutes les paires de sommets de O avant de supprimer les arêtes. Cela peut être fait par BFS à partir de chaque sommet O.