一般因子定理と因子を求めるアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
Gを自己閉路を含量ない有限無向グラフとし、〔G〕をその枝集合、〈G〉をその頂点集合とする。F⊆〔G〕に対してd^F(u)で頂点uに接続するFに属する枝の本数を表わすものとする。Gの各頂点uに対して、一対の非負整数p(u)、q(u)が与えられているとき、すべて頂点についてP(u)≦d^F(u)≦q(u)が成立するF⊆〔G〕をグラフGの(p、q)一因子と呼ぶ。(p、q)一因子は、とくにp(u)=q(u)=1の場合完全マッチング、p(u)=q(u)=f(u)の場合f一因子と呼ばれ、Tutteによってその存在のための必要十分条件が与えられている。またすべての頂点についてp(u)<q(u)が成り立っている場合に(p、q)一因子が存在するための必要十分条件はKorenが与えている。本論文ではp(u)とq(u)の値が一般の場合(ただし、問題が意味を持つためにはp(u)≦q(u)てなければならない)に、(p、q)一因子が存在するための必要十分条件を与える。V⊆〈G〉に対して、G(V)でグラフGから頂点集合VとVの頂点に接続するすべての枝を取り去ったグラフを表わす。X、Y⊆〈G〉に対して、Xの頂点とYの頂点を結ぶ枝の本数をd(X、Y)で表わす。また排反凌頂点集合の対S、T⊆〈G〉について、条件(1)HはG(SUT)の連結成分、(2)Hのすべての頂点についてp(u)=q(u)、(3)Σp(u)十d(〈H〉、S)二奇数u∈<H>をみたすHの個数をk(S、T)とする。(p、q)一因子が存在するための必要十分条件は次の定理で与えられる。定理与えられたグラフGに(p、q)一因子が存在するための必要十分条件は、すべての排反な頂点集合の対S、Tについて、[numerical formula]が成立することである。この定理よりTutteのf一因子定理、Korenの(P、q)一因子定理を尊びくのは容易である。
- 社団法人日本オペレーションズ・リサーチ学会の論文