シリアル番号 | 表題 | 日付 |
974 |
グラフ理論 |
2005/08/25 |
オイラーがはじめた数学の一分野。ノード(節点・頂点)の集合とエッジ(枝・辺)の集合で構成されるグラフの性質について研究する学問である。
コンピュータのデータ構造、アルゴリズムなどに広く応用されている。
1959年ハンガリー人の放浪の数学者ポール・エルデッシュ(Erdosh)のランダム・グラフ論、すなわちランダムリンクが全ての街を結びつけることを証明。
1971年、社会学者ミルグラムの8次の隔たりをマーク・グラノヴェーターはグラフ理論を使って強い絆は3角形になると点に縮退できる。したがって弱い絆が社会のブリッジになっていることを証明。
1998年スティーブン・ストロガッツ(Steven
Strogatz)、ダンカン・ワッツがスモール・ワールド・ネットワークをグラフ理論
で説明。強い絆で結ばれたノードはクラスター化しているためエッジがノードに縮退し、弱い絆で結ばれた不規則なノードが残り、隔たり次数をすくなくすることに貢献。