graph - 有向加重グラフのすべての全域木を検索

Question

私はこれまでにこの論文を見つけました。時代遅れですか？より速く、より良い実装はありますか？

ちなみに、ウィキペディアによると、無向グラフにはn^n-2のスパニングツリーが存在する可能性があります。有向グラフにはスパニングツリーをいくつ含めることができますか？

Answer 1

無向グラフのみ....

n^n-2 スパニング トレスは、完全なグラフに対してのみ可能です....任意のグラフのスパニング ツリーの総数を見つけるには、この方法を適用できます.....

1. グラフの隣接行列を見つけます。
2. 列の値が「i」で表され、行のエントリが「j」で表される場合...
3. i=j...の場合、値は頂点の次数になります
4. 頂点 v1 と v2 の間に単一のエッジがあると仮定すると、マトリックス エントリの値は -1 になります...7 エッジが 2 つある場合は -2 になります...など...
5. 隣接行列を構築した後....行と列を除外します...つまり、N番目の行とN番目の列....
6. 答えは、スパントレスの総数になります。

Answer 2

あなたが言及した論文の用語を使用し、有向グラフのスパニング ツリーを頂点 r をルートとするツリーとして定義し、r から他の頂点への一意のパスを持つ場合:

有向グラフが最大数のスパニング ツリーを持つ場合の最悪のケースが完全なグラフであることは明らかです (任意のペアに a->b および b->a エッジがあります)。方向を「忘れる」と、無向グラフの場合と同様に、n^{n-2} スパン ツリーが得られます。このスパニング ツリーのいずれについても、ルートを選択するための n 個のオプションがあり、この選択により、使用する必要があるエッジの方向が一意に定義されます。取得するすべてのツリーがスパンし、一意であり、他に選択肢がないことを理解するのは難しくありません。したがって、n^{n-1} スパニング ツリーが得られます。厳密な証明には時間がかかるので、簡単な説明で十分だと思います。

したがって、このタスクは、最悪の場合、頂点数に応じて指数関数的な時間がかかります。出力のサイズ (すべてのスパニング ツリー) を考慮すると、任意のグラフの場合、アルゴリズムを大幅に高速化および改善することはできないと結論付けています。すべてのスパニングツリーを処理しないように、元の問題を何らかの形で再定式化する必要があると思います。検索は、いくつかの基準でのみ必要になる場合があります。