II ハイパーグラフ：ぱらぱらめくる『Introduction to Graph and Hypergraph Theory』

Chap 7 ハイパーグラフの基礎概念
- 基礎の基礎
  - Vertices
  - Hyperedges (Vertidesセット)
  - 隣接は、同様のものの間の関係(Vertices間、Hyperedges間)
  - Hyperedgesの隣接
  - VeritexとHyperedgeとの関係「Incident」
  - 次数：ノードの次数、エッジの次数
- Incidence とDuality
  - Incidence matrixはノードとハイパーエッジの関係を表した０，１行列
  - Dualはグラフと線グラフとの関係のように、ノードとハイパーエッジの関係を反転させたもの
- ハイパーグラフの分類・基本特性表現
  - 完全k-ハイパーグラフ
  - Connected
  - Bipartiteとr-partite
  - Isomorphic
- ハイパーグラフの基礎演算
  - ノードの除去(強除去と弱除去)
  - ハイパーエッジの除去(強除去と弱除去)
  - Contraction(収縮・縮小)
- サブハイパーグラフ
- Helly property
  - ハイパーエッジ(それは部分集合)同士にintersectionがある(おしなべてある)性質についてきちんと定義したものがHelly property
- Star
  - 全ハイパーエッジに含まれるノードがあるようなハイパーグラフ
- Self-duality
  - 双対と自身が同じ
Chap 8 ハイパー木、Chordal ハイパーグラフ
- サイクルがないのが木
- サイクルはあっても、弧(対角線)を引いて最小化されているのがChordal graph
- その定義をハイパー化したもの
- Cyclomatic number of Hypergraph
  - サイクルがグラフを複雑にしている元凶
  - その複雑さと取り組むための武装がCyclomatic number
Chap 9 その他のRemarkable ハイパーグラフ
- バランスのとれたハイパーグラフ
- インターバルを扱ったハイパーグラフ
- "Normal"なハイパーグラフ
- Planar ハイパーグラフ
Chap 10 ハイパーグラフの彩色
- 彩色問題をハイパーグラフにも拡張せずにはいられない…