2006-07-09

2.2 木、閉路、カット (グラフ) 駆け足で読む B.コルテ/J.フィーゲンの　組合せと最適化-理論とアルゴリズム

駆け足で読むシリーズアルゴリズムグラフ組み合わせ Java

グラフにおける閉路とカット
- 閉路はぐるっと一巡するタイプのグラフ
  - 定義としては、点と辺を交互にたどってもとの点に戻ってくるような点と辺の集合である。ただし、このとき点と辺はそれぞれ１度ずつしか使用しないし、１度は使用するものとする。
- カットは、あるグラフの点集合の部分集合を端点とする辺の集合のこと。有向グラフの場合には、有向カットがあり、これは、点集合の部分集合に入る辺がないときに定義され、この点部分集合から出て行く辺の集合のこと。
代数的グラフ理論におけるベクトル空間
- 代数的グラフ理論(algebraic graph theory -> Wikipedia の記事はこちら)
- グラフ $G$ の辺 $E$ の数の実数成分からなるベクトル $(x_e)_{e￥in E(G)}$ を要素とするベクトル空間 $￥bf {R}^{E(G)}$
- 特に重要な２つの線形部分空間、サイクル空間(cycle space)とコサイクル空間(cocycle space)
  - 有向グラフGの辺の数の要素を持つベクトルを、Gの無向閉路について定める方法は掲載図の通り。ことばで表すと、無向閉路に含まれない辺には０を与える。含まれる辺には、１か-１を与える。１を与えるか-１を与えるかは、次のようにして決める。無向閉路は、有向閉路になっていないので、無向閉路の辺をこっち向きとあっち向きの２群に分けて、どちらかの１群には１を、もう片方の１群には-１を与える。この規則だと、有向閉路に対するベクトル成分は、０か１かになることになり、１を持たないベクトルを持つ閉路は(通常)ないことになる
  - この説明図は、サイクルがこちら、カットがこちら
  - サイクル空間
    - 上述のGの無向閉路に対して定義されたベクトルが張る部分空間をサイクル空間と言う
  - コサイクル空間
  - 有向グラフGのサイクル空間とコサイクル空間は互いに直行する
サイクル基底(cycle basis)とコサイクル基底(cocycle basis)、基本閉路(fundamental circuit)と基本カット(fundamental cut)
- ある有向グラフGにおいて、閉路の数はグラフに固有である。カットの数は、点の数Vnについて、 $2^{Vn}-1$ である。閉路とカットとに定められるベクトルが互いに直行することは、上で述べ、それぞれがサイクル空間、コサイクル空間を張ることも述べた。張られる空間には、基底が存在し、基底の数が次元である。閉路ベクトルとカットベクトルとは相互に直行するので独立だが、閉路ベクトル同士、カットベクトル同士は独立とは限らない。閉路ベクトルの中のいくつかが閉路ベクトル空間の基底となり、カットベクトルの中のいくつかがカットベクトル空間の基底となることがわかる。これらをサイクル基底、コサイクル基底と呼ぶ
- サイクル基底とコサイクル基底の見出し方
  - サイクル基底とコサイクル基底との取り方は一通りではないが、Gの持つ、無向閉路を持たない極大部分グラフTを基準にして選ぶ方法がある。その選ぶ作業において登場するのが、(ある辺に定められた)基本閉路、と、(同じくある辺に定められた)基本カットである。これについての説明図は基本閉路がこちら、基本カットがこちら。
  - 今、無向閉路を持たない極大部分グラフTの辺の数をe(T)とし、それ以外の辺の数をe(G)-e(T)とすると、Tはe(G)-e(T)個の基本閉路を持つ。この基本閉路の構成辺は、Tに含まれない唯一の辺によって異なるので、対応するベクトルは相互に独立である。同様に、Tに対する基本カットはe(T)本の辺に対応して存在し、これらに対応するベクトルも相互に独立である。従って、Tについての基本閉路が作るサイクル空間は次元がe(G)-e(T)、Tについての基本カットが作るコサイクル空間は次元がe(T)。今、任意のサイクル空間のベクトルとコサイクル空間のベクトルが直行することはすでに示したから、Tに対応する基本閉路と基本カットの次元はそれぞれの次元の和となり、それは、e(G)になる
集合システム、ラミナー、クロスフリー
- 集合システム(set system)
  - 空でない有限集合UとUの部分集合の族Fの対(U,F)を集合システムと呼ぶ。ハイパーグラフ(hypergraph)とも言う。
- Uの部分集合の族は、Uのべき集合、power setに似ているが、Uの部分集合のすべてが要素として存在していない点が違う。また、(おそらく)集合システムの方は『族family)』なので、同一の要素を持てるのに対し、power setでは、同一の要素は１つとしてとらえる点が違う
  - 実際、Uの集合システムの中には、ラミナーと呼ばれる特徴や、クロスフリーと呼ばれる特徴を有するものもあり、これらの要素数はそれぞれ、高々Uの要素数の2倍(2x|U|)、Uの要素数の４倍-2(4x|U|-2)であることからもわかる(ちなみに、べき集合の要素数は $2^{|U|}$
- ラミナーとそれに対応する木の作り方
  - 有限な要素数を持つ集合Uがある。Uの部分集合の族Fと、その対(U,F)の集合システムを考える。
  - ラミナーである集合システムとは、Fの要素である集合が入れ子構造になっており、入れ子の原則から逸脱する要素を持たないものである。
  - ラミナーである集合システムは、有向木として表現できるし、有向木であるようなグラフ表現ができる集合システムはラミナーであることが知られている。
  - その作り方を以下に示す。(解説図はこちら)
    - 今、辺の数がFの要素数 |F| であるような、木を作る。これから作る木では、この |F| 個の辺がFの要素である集合に対応する。木なので、この木の点の数は |F|+1である。Uの要素はこの木の |F|+1 個の点の１つに対応させる。|U|と|F|+1とは等しいとは限らないので、１つの点に0,1,2個以上のUの要素が対応することとなる。
    - 入れ子構造の一番内側にあたるFの要素集合の要素であるUの要素を１つの点に対応させる
    - 次に、入れ子構造の一回り外側のFの要素集合の要素で、内側の要素集合の要素でないUの要素を別の点に対応させ、その2点を辺で結ぶ。その辺の向きは、入れ子の内側要素に対応する点に向かうものとする。
    - ２つ以上の部分集合の和であるような部分集合がある場合には、点にはUの要素を対応させずに、それぞれの部分集合とその1点との間に辺を結ぶ。向きは入れ子の内側へ向かわせる。
    - このようにして点と辺とを対応させていくと、1つ以上の木ができており、対応するUの要素をいまだ与えられておらず、辺を持たない点が１つ余っているはずである。また、それ以外の点はUの要素をもつか、持たない場合には、辺で部分木に属しているはずである。Uの要素のうち、Fの要素集合のいずれにも属さないものがある場合には、余っているUの要素を余っている点に対応させ、Uの要素に余りがないときには何も対応させずに、すでにできている木(1点でできていることもある)の根との間に辺を渡す。向きは既作成木へ向かわせる。
    - このようにしてできたグラフにおいて、各辺はFの要素集合であり、このFの要素集合の要素は、この辺から到達可能な点に与えられたUの要素となっている
- クロスフリーとそれに対応する木の作り方
  - クロスフリーでは、ラミナーの対応グラフが有向木(どの点も入る辺の数が１つ)だったのに対し、向きを無視したグラフ(無向基礎グラフ)が木であるが、有向木とは限らないような木で表される集合システムである。辺が集合要素に対応し、その辺から到達可能な点に対応したUの要素が集合要素の要素になっている点ではラミナーに同じ。
  - 今、辺の数がFの要素数 |F| であるような、木を作る。これから作る木では、この |F| 個の辺がFの要素である集合に対応する。木なので、この木の点の数は |F|+1である。Uの要素はこの木の |F|+1 個の点の１つに対応させる。|U|と|F|+1とは等しいとは限らないので、１つの点に0,1,2個以上のUの要素が対応することとなる。
  - ラミナーと同じ作業を行う。
  - (解説図はこちら)
  - ある時点で、点と辺も余ったまま、ラミナー作業が続けられなくなる。
  - そのようなときには、あるひとつの点に与えられたUの要素を除けば、ラミナー入れ子の構造が見つかる。そのようなときには、例外の要素を別の点に移動し、例外要素を持つ点から、移動前の点へと辺を渡す。その上で、ラミナーと同様の作業上位の点・辺の作業を行う
  - このようにしてできたグラフにおいて、各辺はFの要素集合であり、このFの要素集合の要素は、この辺から到達可能な点に与えられたUの要素となっている。