ISEGORIA / 数学百科事典
グラフ理論：経路・木・ネットワーク
最短経路・全域木・中心性を可視化します。
前提知識: 集合と初歩的なアルゴリズム
予想してから操作し、計算例と問いで理解を確かめてください。グラフは数式の図示であり、証明ではありません。
1. 最短経路
ダイクストラ法は、未確定のノードのうち暫定距離が最小のものを確定し、その隣のラベルを改善することを繰り返します。中心街の道路の混雑重みを上げたり、A から F への斜めの近道を加えたりして、任意のノードをクリックすると S からの経路が表示されます。再生すると前線が1ノードずつ広がる様子が見られます。
計算例. 混雑重み1で近道がなければ、S から T への距離は12で、2通りの経路で達成されます。
注意点. 負の辺重みがあると、確定したラベルが後で大きすぎたと分かることがあり、ダイクストラ法は誤った距離を返し得ます。
前線が最適であり続けるのはなぜですか？
確定したノードへの別経路は、必ずどこかの前線ノードを通って確定集合から出ます。そのラベルはすでに同じかそれ以上で、非負の重みは値を増やすだけだからです。
2. 最小全域木
クラスカル法は軽い辺から順に取り、閉路を作らないものだけを残します。カットを動かすと、それを横切る最軽量の辺は常に最小全域木に含まれることが分かります。候補の辺 5–8 の重みを変え、いつ木に入るかを見ます。
計算例. この10頂点の全域木は、どれも9本の辺を持ちます。
注意点. 全域木は全頂点を閉路なく結びますが、木の中の2頂点間の経路が最短経路とは限りません。
最軽量の横断辺がある最小木に属するのはなぜですか？
それを含まない最小木に加えると、カットをもう一度横切る閉路ができ、その辺は同じか重いものです。2本を交換しても木は重くならないためです。
3. 中心性と影響力
2つの群は橋のノード X を通してつながっています。ノード C に葉を加えて次数を上げ、群の間に直接のリンクを加えて X を通らない経路を作ります。どの指標でノードの大きさを決めるかを選べます。棒グラフは、描かれたグラフ上の3つの指標を比較します。
計算例. 初期設定では、橋 X の次数は4で葉を持つハブ C より小さいものの、群の間のすべての経路が通るため媒介中心性は最大です。
注意点. 中心性はモデルの選択であり、普遍的な順位ではありません。
多くの直接の隣人を評価する指標は？
次数中心性は直接の隣人を数えます。