algorithm - 有向グラフでエッジがばらばらなパスの最大数を見つける

Question

有向グラフでエッジがばらばらなパスの最大数を見つけるにはどうすればよいですか。グラフは重み付けされていません。グラフが次のようなものだとします...

1 - 2 , 1 - 3 , 4 - 1 , 5 - 1

したがって、グラフには2つのエッジのばらばらのパスがあります4->1->2。5->1->3

マッチングアルゴリズムを使用して問題を解決するにはどうすればよいですか？

私の問題は...有向グラフがあると仮定します（サイクルが含まれている可能性があります）。ノードに「ガード」を配置すると、そのノードからの移動を開始できます。警備員は、他の警備員がすでに訪れている都市であっても、任意の都市を何度も訪れることができます。目的は、すべてのノードを保護するためのガードの最小数を見つけることです。

Answer 1

すべてのパスを数える：

• グラフ内のすべてのエッジを、使用可能なエッジのリストとして開始します。
• まだ利用可能なエッジがある間、パスを抽出してカウントし続けます。

パスの抽出：

• 最初の（または任意の）使用可能なエッジを削除し、それを現在のパスと呼びます。
• 現在のパスの開始または終了を、使用可能なエッジの終了または開始に一致させてください。
• 使用可能なエッジが一致しない場合、このパスは終了します。
• 使用可能なエッジがパスを長くする可能性がある場合は、それを現在のパスに追加し、使用可能なエッジのリストからそのエッジを削除して、パスを長くしようとし続けます。