読者です 読者をやめる 読者になる 読者になる

Matching, Covering and Packing (Graph Theory, Chapter 2)

  • k-factor = 全域部分グラフであって,全頂点の次数が k

2 部グラフのマッチング

  • 2 部マッチングのサイズ = 頂点被覆のサイズ
  • $|N(S)| \geq |S|$ for all $S \subseteq A$
  • stable matching は常に存在

一般グラフのマッチング

  • G が 1-factor 持つ ⇔ $q(G-S) \leq |S|$ for all $S \subseteq V(G)$
    • q(G-S) := 奇数頂点数の連結成分数

パッキング,カバーリング

  • packing, covering (グラフクラス H というのが与えられて)
  • Erdos-Posa property

木のパッキング

  • Arboricity: グラフ G の分割であって森たちにする最小の個数
    • maximum local density の指標
    • star-arboricity とか亜種がある
  • Path cover