無向グラフを最小のパスとサイクルに分解する

Question

無向グラフを、最小の数のパスとエッジが繋がっていないサイクルに分解したいと思います。

私の考えは、まず最長の経路をとることですが、多項式ではありません。

多項式アルゴリズムを知っていますか？

Answer 1

最大フロー/最小カットを使用することは楽しいことがあります - カットの最小量を使ってグラフを半分にカット - あなたが最も長いパスアルゴリズムを実行するのに扱いやすいサイズのサブセットを得るまで、これを数回再帰的に行います。

Answer 2

Jens Schmidtが説明したように、グラフの「連鎖分解」に興味があるかもしれません。

このウィキペディアの記事Ear Decompositionsに記載されています。私はそれを自分で実装しました。それは素晴らしい単純なアルゴリズムです。