私は与えられた質問に対する答えを探していました。提供されるその他の詳細は次のとおりです。容量が 0 より大きいグラフ内の各リンクは p であり、容量が 0 未満のリンクの確率は 1-p です。{1,2,3,4} のようなデータ ベクトルがノード 1 からノード 5 に正常に送信される確率はどのくらいですか。
この種の問題には max-flow の概念があることは知っていますが、そのようなネットワークを介した送信が成功する確率はまだわかりません。
2 番目の質問: max-flow の概念を探す前に。開始ノードと宛先ノードを考えると、単純に BFS を実行して、ソース ノードから宛先ノードまでの多くの可能なパスを見つけ、それらをタップし続けることができると考え始めました (パスが無限にある場合、それは指数関数的な時間になることに気付きました)。巨大なスペースの複雑さを持つアルゴリズムですが、それはかなり有限のネットワークだと言います)。次に、P（成功した送信）を計算するために、次の方法でアプローチできますか？
ノード 1 からノード 5 へのパスの数が 4 の場合、P(ノード 1 とノード 5 の間の成功した伝送は)= P(パス 1)+p(パス 2)+p(パス 3)+p(パス 4)-p(パスの交差点） どこ、
P(交差) は、次のような 2 つ以上のパスがエッジを共有する可能性がある確率です。 4.
また、そのパス内のエッジの p(path#)=p^no。私のアプローチは正しいですか？また、このように考えてよろしい場合、これを無限パスの可能性に拡張するにはどうすればよいですか?
どんな助けや指針も大歓迎です!! ありがとうございました。