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
- X ∈ V が linked とは，任意の同サイズで素の S={s_i}, T={t_i} ∈ X が link できる
- 関数 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
