メモ

シリアル番号 表題 日付

974

グラフ理論

2005/08/25

オイラーがはじめた数学の一分野。ノード(節点・頂点)の集合とエッジ(枝・辺)の集合で構成されるグラフの性質について研究する学問である。

コンピュータのデータ構造、アルゴリズムなどに広く応用されている。

1959年ハンガリー人の放浪の数学者ポール・エルデッシュ(Erdosh)のランダム・グラフ論、すなわちランダムリンクが全ての街を結びつけることを証明。

1971年、社会学者ミルグラムの8次の隔たりをマーク・グラノヴェーターはグラフ理論を使って強い絆は3角形になると点に縮退できる。したがって弱い絆が社会のブリッジになっていることを証明。

1998年スティーブン・ストロガッツ(Steven Strogatz)、ダンカン・ワッツがスモール・ワールド・ネットワークをグラフ理論 で説明。強い絆で結ばれたノードはクラスター化しているためエッジがノードに縮退し、弱い絆で結ばれた不規則なノードが残り、隔たり次数をすくなくすることに貢献。


トップ ページヘ