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

Connectivity (Graph Theory, Chapter 3)

  • vertex connectivity, edge connectivity
  • cut vertex (=articulation point), bridge
  • block (= maximal 2-connected subgraphs)

2-connected

  • 任意の 2-connected graph はパスの付加を繰り返すことで構成できる

3-connected

  • 3-connected で |V|>4 なら,ある辺が存在してそれを縮約しても 3-connected
  • 3-connected ⇔ 以下のようにしてグラフを作れる
    • G_0=K_4, G_1, G_2, ..., G_n = G
    • G_i = G_{i+1}/xy, xy ∈ G_{i+1}, d(x), d(y) ≧ 3
  • 3-connected なグラフのサイクル空間は non-separating induced cycles で作られる

Menger の定理

  • 集合 A, B を分割するために削除するための必要な頂点数 k(G, A, B) は,disjoint A-B path の最大数と等しい
    • 後に最大流・最小カットとして一般化された

Mader の定理

  • induced subgraph H がある. independent な H-path を何個取れるか?
  • M_G(H) 個とれる (M_G はなんかの min)

linking

  • 定義
    • X ∈ V が linked とは,任意の同サイズで素の S={s_i}, T={t_i} ∈ X が link できる
      • link できるとは,各 s_i から t_i へのパスが存在 (終点が指定されてることに注意)
      • ただし中間には X 外の頂点のみを使って,vertex-disjoint なパスたちでつなげる
    • G は k-linked ⇔ 任意のサイズ≦2k の集合が linked
  • 関数 h であって,d(G)≧h(r) なら G が K_r を topological minor として持つようなものがある
    • ただし h(r) は 2^2^r とか(少なくともこの本の証明では)
  • 関数 f であって,f(k)-connected graph なら k-linked となるようなものがある
  • 2k-connected かつ ε(G)≧8k なら k-linked
  • δ(G)≧8k かつ |G| ≦ 16k ならば k-linked