グラフ理論
平成18年度 T-12
設問1
cost(f_1)=5設問2
まず双方向に枝がのびている場合、これを無視していい。なぜならばこの枝のペアはかならずどちらかが整合しどちらかが整合しない。
よってどのようにラベリングしてもOPT(G)には+1だけ必ず寄与する。
そのようにして双方向の枝を省いたとき、閉路ができる。閉路ではどのようにがんばっても閉路の枝数mに対してm-1しかOPT(G)に寄与できない。
よって以下のようにラベリングしたとき、costは6
消去した2組の双方向枝を加えてOPT(G)=8
設問3
必要条件を証明するすなわち「OPT(G)=|E|」⇒「Gが有向閉路を持たない」
対偶をとって「Gが有向閉路を持つ」⇒「OPT(G)<|E|」
Gの有向閉路の部分を取り出して考える。
閉路を構成する枝数をmとし、閉路の頂点へのラベリングを連結順にL_1 ・・・ L_mとすると
OPT(G)=|E|となるためにはL_1<L_2<・・・<L_m<L_1となる必要があり不可能。
十分条件を証明する
すなわち「Gが有向閉路を持たない」⇒「OPT(G)=|E|」
有向閉路をもたないならば、出る枝しかない頂点と、入る枝しかない頂点が存在する。
出る枝しかない頂点には可能な割り当てのうち最小の割り当てを、入る枝しかない頂点には最大の割り当てを行う。
そして割り当てた頂点について、枝ごと消去する。
このとき消去した枝は全て整合する枝であることに注意する。
こうして新たに出来たグラフはやはり有向閉路を持たない。
この操作を繰り返すことにより全ての枝を消去できる。
つまりOPT(G)=|E|
設問4
「OPT(G)=|E|-k」⇔「消去することにより有向閉路がなくなる枝の最小数=k」十分条件を証明する
消去することにより有向閉路がなくなる枝の最小数をkとすると、
そのk本の枝を消去して有向閉路を消去し、そのグラフに最適ラベリングをすればcost=|E|-kは実現できる。
costが|E|-kを越えないことを証明する。
そのようなラベリングfが存在したとして、そのときに整合していない枝の本数をm=|E|-cost(f)とすると
その枝を消去したグラフは設問3の証明から有向閉路を持ってはいけない。
しかし仮定よりm<kでは有向閉路を消去することは出来ない。
よってそのようなラベルリングは存在しない
つまりOPT(G)=|E|-k
必要条件を示す。
OPT(G)=|E|-kにも関わらず、消去することにより有向閉路がなくなる枝の最小数=m≠kとする。
十分条件からOPT(G)=|E|-m
これは矛盾であるから、消去することにより有向閉路がなくなる枝の最小数=k
設問5
あるGについてOPT(G)=m<|E|/2とする。そのOPT(G)を与える割り当てをfとする。
ここでfの反転割り当てgを考えると
(昇順を降順へ、1,2,3,...をn,n-1,n-2...へ変更)
gはfで整合する枝をすべて整合しなく、整合しない枝をすべて整合するようにする。
よってcost(g)=|E|-m>|E|/2
これは矛盾であるから、OPT(G)≧|E|/2
平成17年度 T-12
設問1
VC(G)=4IS(G)=4
CQ(G)=3
Color(G)=3
枝(3,4)を被覆するために3と4のどちらかを選択することになるが
明らかに3を選択するほうが効率的である。
このあと残った枝について
枝(7,8)を被覆するために7より8を選択するほうが良い。
あとは自動的
ISは設問2からわかる。
Colorは2色で塗れないことはすぐわかる。
3色は実際ぬれることを示す。
設問2
A「ある頂点被覆を取る」⇒「その反転は独立頂点」B「ある独立頂点をとる」⇒「その反転は頂点被覆」
この２つを示せばよい。
Aについて、頂点被覆外の頂点は、頂点被覆を通らずに
他の頂点被覆外の頂点へはつながっていない。
そのような経路があるならばその枝は被覆されていないから。
Bについて、独立頂点を枝を残してすべて消去したとき
宙ぶらりんの枝は存在しない。
よって残された頂点をすべて選択すれば、それは頂点被覆になっている。
以上から頂点被覆が最小のとき、独立頂点は最大となり
つまりVC(G)+IS(G)=|V|
設問3
クリークとは部分完全グラフを構成する頂点集合のことであるが、クリーク内からは多くとも1つの独立頂点しか輩出できない。
2つ以上できるとしたらクリークの定義に反する。
よって独立頂点集合は最大でも、クリーク外の頂点すべて＋クリーク内の頂点1個、である。
よってIS(G)+CQ(G)≦|V|+1
設問4
Gに最小の色分けを行ったとすると、このうち同じ色のものだけを取り出した集合は独立頂点集合である。よって、このような集合がColor(G)=kの数だけできるが、その集合をX_1, X_2, ... X_kとすると
IS(G)≧|X_1|, IS(G)≧|X_2|, ..., IS(G)≧|X_k|
これらの和を考えてIS(G)*k≧|V|
設問5
IS(G)≦2かつCQ(G)≦2とする。CQ(G)≦2ということはつまり、
どの頂点も互いに接続されていないか(CQ(G)=1)、もしくはCQ(G)=2
どの頂点も互いに接続されていないならば、IS(G)=6なのでおかしい、よって後者のみ
IS(G)≦2ということはつまり、
Gが完全グラフであるか(IS(G)=1)、もしくはIS(G)=2
完全グラフならば、CQ(G)=6なのでおかしい。よって後者のみ。
よってCQ(G)=2かつIS(G)=2について考える。
Gから最大独立頂点集合をとってきて、A,Bと名づける。
残りをC,D,E,Fと名づける。
このときC,D,E,FはAかBに必ず接している。
(さもなければ、接していない頂点をとってきて、独立頂点集合に付け加えられる)
Aに接続しているグループ同士では接続していない
Bに接続しているグループ同士では接続していない
よってA,Bどちらにも接続している頂点は、A,Bのみにしか接続していない。
詳しく考えると、そのような頂点は存在できないことがわかる。
よってAだけに接続された組とBだけに接続された組の部分2部グラフを考えることになる。
さらに詳しく考えるとA組が2個、B組が2個とならざるを得ない。
A-CD B=EFと考えると、A,E,Fが独立頂点となっていてIS(G)=2に矛盾
よってIS(G)≧3 またはCQ(G)≧3
平成16年度 T-12
設問1
まず平面グラフであるから、4色定理より、4色以下で彩色できることがわかる。まず1色、2色で彩色できないことは三角形になってる各頂点について考えれば簡単にわかる。
よって3色で彩色できないことを示す。
色をa,b,c...で表す。
1をa、4をb、3をcでぬると、3色でぬるためには5はa、6はc、8はbと自動的に決まる。
ここで9はa,b,cの三色に接しているからどの色でも塗ることはできない。
4色で塗れることは実際にやって示す。
設問2
次数最大の頂点について考える。その頂点を中心として、それに接するD個の頂点へ1本ずつ枝がのびる図を考える。
これは周囲の頂点をD色使って塗り、中心となる頂点を残りの1色を使って塗ればよい。
それ以外の頂点について考える。
この頂点について
1.接する頂点がすべて塗られているとき
この場合、周囲で使われている色数は高々D色である。使われていない色を使って塗ればよい。
2.接する頂点に未彩色のものがあるとき
この場合も、未彩色の頂点は無視して、彩色済みの頂点と重複しないような色を適当に選んで塗ればよい。
結論：すべての頂点はこの条件に当てはまり、毎回1頂点ずつ彩色していけるから、有限の頂点数ならば正しい彩色が最後に現れる。
設問3
必要条件をまず証明する。つまり「2-彩色可能」⇒「奇数本の枝からなる閉路を持たない」
対偶を考えて「奇数本の枝からなる閉路を持つ」⇒「2-彩色不可能」
奇数本の閉路を持つグラフの中で、その閉路をまずぬりわけようとすると
A-B-A-B-・・・-A-B-A と奇数個の頂点を塗らざるを得ないが
この最初と最後の頂点が接しているためA-Aというパターンができてしまう。
よって2-彩色不可能
十分条件を証明する
つまり「奇数本の枝からなる閉路を持たない」⇒「2-彩色可能」
適当に頂点を選び出して根rとする。
このとき任意の頂点xに対してr-x路は偶数長か奇数長のどちらか一方に決定する。
(もしr-x路の取り方によって偶奇が一意にならないならば、奇数長の閉路が存在することになる)
この分類によって偶数長のものと奇数長のものの2つに色分けする。
このとき、色分けされたグループ内部でつながる枝は存在しない。
もし存在すればそれを使うことによってr-x路の偶奇を反転させることができてしまうから。
設問4
教師3人、コマ数3、クラス数2を例として考える。| 1組 | 2組 | |
| 1時限 | A | B |
| 2時限 | C | D |
| 3時限 | E | F |
このとき考えられる制限は
1.同一時限に同一教師は不可能
これはA-B C-D E-Fというように頂点を連結すればよい
2.同じクラスを同じ教師が2度教えない
これはACE同士を結び、BDF同士を結べばよい
2006年07月25日(火) 14:33:38 Modified by goriasdf
添付ファイル一覧(全1件)
bcbecbef45129d37.png (3.86KB)
Uploaded by ID:RkCNQ6LbCQ 2006年07月17日(月) 23:44:27
Uploaded by ID:RkCNQ6LbCQ 2006年07月17日(月) 23:44:27