グラフ理論

グラフ理論またはネットワーク理論は離散数学の一分野として非常に重要視され、近年では無限の応用を示しながらその領域を広げている。生まれながらにして視覚化に有利でアルゴリズムに親和性があるため、コンピュータ科学やデータ科学とも密接な分野であるが、皮肉なことに証明過程で数式よりも言葉が多い場合が多く、むしろ数学者が扱いにくい科目でもある。好き嫌いは別として、学ぶことで時間の無駄になることは決してなく、前提知識が特にないため大学一年生にも気軽に勧められる。

基礎

• グラフとネットワーク
  • アイソモーフィズム
  • ホモエオモーフィズム
• 🔒(24/08/28) ハイパーグラフの定義

スペクトラル

• グラフの行列表現
• 次数 $\deg$
  • 握手補題
  • 握手ジレンマ

トポロジー

• グラフの集合表現
  • サブグラフ
• 距離、近傍、直径、周長 $d$, $N$, $\text{diam}$, $\text{girth}$
• グラフコンプリメント $\overline{G}$

決定論的グラフ

名前付きグラフ

• ヌルグラフと完全グラフ $K_{n}$
• レギュラーグラフ
• 二部グラフ $G(A,B)$
• 無限グラフ
  • ケーニヒの定理
• エルデシュ-ガライの定理
• ハベル-ハキミのアルゴリズム
• 木グラフ
  • ラベル付き木とケイリーの定理
• １因子グラフ
  • アンダーソン-リビングストンの定理
• 完全グラフ

パス問題

• ウォーク、トレイル、パス、サイクル
  • グラフのオリエンテーション
• オイラーグラフ
  • ケーニヒスベルクの橋の問題とその解
  • フルーリーアルゴリズム
• ハミルトングラフ
  • ディラックの定理

4色問題

• 平面グラフとクラトフスキーの定理
  • オイラーの多面体定理
  • 単純平面グラフの性質
• グラフの色塗りとブルックスの定理
• グラフのk-連結性とメンガーの定理
• 幾何学的双対グラフ
• 抽象的双対グラフ
• グラフ理論における地図の定義
• 5色定理
• 4色地図問題

非決定論的ネットワーク

ランダムネットワーク

• グラフのファミリーとプロパティ $2^{\binom{n}{2}}$, $\mathscr{G}_{n,m}$
• ランダムネットワーク $\mathbb{G}$
  • 次数の分布
• エルデシュ-レニーモデル $\mathbb{G}_{n,m}$
  • ギルバートモデル $\mathbb{G}_{n,p}$
• スケールフリーネットワーク
  • チュン-ルーフィットネスモデル
  • バラバシ-アルバートモデル
• ユークリッドネットワーク

中心性

• ハブノード
• 次数中心性
• 仲介中心性
  • ストレス中心性
• 近接中心性
• 固有ベクトル中心性

実践

• Gephi: グラフの可視化と分析プログラム
• NetworkX: グラフ分析用Pythonパッケージ
  • GEXFファイルの読み書き
• 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