0

私が知りたいのは、与えられたグラフのすべてのエッジのエッジ接続性を決定するためのアルゴリズムについて読むことができる文献があるかどうかです。

特定のエッジのエッジ接続性（私が理解しているように）は、特定のエッジを通過する（diffノード間の）最短パスの数です。つまり、すべてのノードから他のすべてのノードに移動する場合、特定のエッジを何回通過するかということです。

ヘルプ/リソースをいただければ幸いです

4

2 に答える 2

1

私が知る限り、これはエッジ間と呼ばれます。これは、頂点の中間性のための優れたアルゴリズムの論文です。エッジの中間性に簡単に一般化できます。

Brandes、Ulrik (2001)。「媒介中心性のためのより高速なアルゴリズム」(PDF)。Journal of Mathematical Sociology 25: 163–177 http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf

于 2012-09-30T19:35:01.517 に答える
0

ダイクストラ アルゴリズムを使用して、最短パスを見つけます。このアルゴリズムを繰り返し使用して、ノードのすべてのペアの最短経路を決定します。これで、各パスの各エッジの発生を単純に合計できます。

于 2012-09-30T09:51:46.963 に答える