グラフ理論
グラフ理論またはネットワーク理論は離散数学の一分野として非常に重要視され、近年では無限の応用を示しながらその領域を広げている。生まれながらにして視覚化に有利でアルゴリズムに親和性があるため、コンピュータ科学やデータ科学とも密接な分野であるが、皮肉なことに証明過程で数式よりも言葉が多い場合が多く、むしろ数学者が扱いにくい科目でもある。好き嫌いは別として、学ぶことで時間の無駄になることは決してなく、前提知識が特にないため大学一年生にも気軽に勧められる。
基礎
スペクトラル
- グラフの行列表現
- 次数 $\deg$
- 🔒(24/10/19) グラフ間のスペクトル距離
トポロジー
決定論的グラフ
有名なグラフ
経路問題
四色問題
非決定論的ネットワーク
ランダムネットワーク
- グラフの族と特性 $2^{\binom{n}{2}}$, $\mathscr{G}_{n,m}$
- ランダムネットワーク $\mathbb{G}$
- エルデシュ=レーニモデル $\mathbb{G}_{n,m}$
- スケールフリーネットワーク
- ユークリッドネットワーク
中心性
実践
- 🔒(24/10/07) グラフのレイアウト
- Gephi:グラフの可視化および分析プログラム
- NetworkX:グラフ分析のためのPythonパッケージ
- Graphs.jl:グラフ分析のためのJuliaパッケージ
主要参考文献
- Albert, Barabási. (2002). Statistical mechanics of complex networks
- Barabási. (2016). Network Science
- Brouwer. (2011). Spectra of Graphs
- Frieze. (2015). Introduction to Random Graphs
- Newman. (2010). Networks: An Introduction
- Wilson. (1970). Introduction to Graph Theory
全體ポスト
- 数学におけるグラフとネットワーク
- グラフの同型写像
- グラフ理論における次数
- 握手補題の証明
- 握手ジレンマの証明
- グラフの行列表現
- グラフの集合表記
- サブグラフ
- グラフの補完
- ヌルグラフと完全グラフ
- レギュラーグラフ
- 二部グラフ
- 無限グラフ
- グラフ理論における歩行、道、経路、サイクル
- グラフ内の距離、近傍、直径、周囲
- グラフのオリエンテーション
- ケーニヒの定理の証明
- オイラーグラフ
- ケーニヒスベルクの橋の問題とその解決
- フルーリーのアルゴリズムの証明
- ハミルトニアングラフ
- グラフ理論におけるディラックの定理の証明
- ツリーグラフ
- ラベルツリーとケイリーの定理
- エルデシュ=ガライの定理
- ハベル-ハキミ アルゴリズムの証明
- グラフ彩色とブルックスの定理
- グラフのホモーモルフィズム
- 平面グラフとクラトフスキーの定理
- オイラーの多面体定理の証明
- グラフのk-連結性とメンガーの定理
- 幾何的デュアルグラフ
- 抽象的な双対グラフ
- 平面グラフの基本的性質
- グラフ理論における地図の定義
- 五色定理の証明
- 四色地図問題
- エルデシュ・レーニグラフ
- アンダーソン-リビングストン定理の証明
- 完全グラフ
- グラフのファミリーとプロパティ
- ランダムグラフ
- エルデシュ=レーニイモデル
- ギルバートモデル
- ネットワーク内の次数分布
- スケールフリーネットワーク
- ブルー・ルーフィットネスモデル
- バラバシ-アルバートモデル
- ネットワーク理論におけるハブノード
- グラフ(ネットワーク)の可視化及び分析プログラムGephi
- Pythonのグラフ(ネットワーク)分析パッケージNetworkX
- ジュリアのグラフ分析パッケージ Graphs.jl
- NetworkXでのGEXFファイルの読み書き
- ユークリッドグラフ
- ネットワーク理論における次数中心性
- ネットワーク理論におけるストレス中心性
- ネットワーク理論における媒介中心性
- ネットワーク理論における近接中心性
- ネットワーク理論における固有ベクトル中心性
- ハイパーグラフの定義
- 数学におけるグラフのレイアウト
- グラフ間のスペクトル距離
- グラフとグラフの間の編集距離