グラフ理論

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

基礎

• グラフとネットワーク
  • 同型（アイソモルフィズム）
  • 位相同型（ホメオモルフィズム）
• ハイパーグラフの定義

スペクトラル

• グラフの行列表現
• 次数 $\deg$
  • 握手補題
  • 握手のジレンマ
• グラフ間のスペクトル距離

トポロジー

• グラフの集合表現
  • 部分グラフ
• 距離、近傍、直径、周長 $d$, $N$, $\text{diam}$, $\text{girth}$
• グラフの補グラフ $\overline{G}$

決定論的グラフ

有名なグラフ

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

経路問題

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

四色問題

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

非決定論的ネットワーク

ランダムネットワーク

• グラフの族と特性 $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