スペクトルグラフ理論

SGCライブラリ  190

スペクトルグラフ理論

線形代数からの理解を目指して
定価:
2,420
(本体:2,200円+税)
難易度:上級

発行日:2024年3月25日

発行:サイエンス社

ISBN:978-4-7819-1601-9

サイズ:並製B5

ページ数:176ページ

在庫:在庫あり

内容詳細

スペクトルグラフ理論は,グラフという組合せ的対象を線形代数という代数的道具を用いて考察する,応用分野でも広く使われる重要な理論である.本書では,スペクトルグラフ理論の数学的な側面に注目し,理論計算機科学においてよく知られていることや,最近得られた結果を中心に解説する.また必要に応じて理論的成果がいかに応用分野で使われているかについても言及している.

目次

第1章 線形代数の基礎
  1.1 基本的な概念
  1.2 対称行列
  1.3 半正定値対称行列
  1.4 射影行列
  1.5 トレース
  1.6 行列式
  1.7 固有多項式
  1.8 ベクトル集合の等方性
  1.9 シューア補行列

第2章 グラフのスペクトル
  2.1 グラフの基礎知識
  2.2 ラプラシアン
  2.3 基本的なグラフとその固有値
  2.4 ラプラシアンの二次形式
  2.5 グラフ描画
  2.6 連結性
  2.7 隣接行列
  2.8 二部グラフ性

第3章 全域木
  3.1 全域木の数え上げ
  3.2 全域木上の一様分布
  3.3 全域木中心性

第4章 電気回路
  4.1 電流
  4.2 電流伝達行列
  4.3 エネルギーによる特徴付け
  4.4 有効抵抗
  4.5 シューア補行列との関係
  4.6 電流中心性

第5章 チーガー不等式とその周辺
  5.1 クラスタリング
  5.2 正規化された隣接行列とラプラシアン
  5.3 チーガー不等式
  5.4 最大固有値と二部グラフ性
  5.5 高階チーガー不等式

第6章 ランダムウォーク
  6.1 無向グラフ上のランダムウォーク
  6.2 確率不等式
  6.3 電気回路的な解釈
  6.4 疎カット

第7章 頂点膨張率と最速混合問題
  7.1 最速混合問題とその性質
  7.2 マッチング膨張率とその性質

第8章 疎化
  8.1 導入
  8.2 ランダムサンプリングに基づく疎化
  8.3 線形サイズの疎化器

第9章 ラプラス方程式の高速解法
  9.1 低伸長木
  9.2 組合せ的アルゴリズム 

第10章 ハイパーグラフと有向グラフ
  10.1 チーガー不等式
  10.2 ハイパーグラフの疎化
  10.3 ラプラシアン

参考文献
索引

サポート情報

関連書籍

ニュートリノの物理学

林 青司

2,640円(税込)

上級
ブラックホールの数理

石橋明浩

2,547円(税込)

中級
共振器量子電磁力学

越野和樹

2,640円(税込)

上級