-
- いいね！0
y.
@waidotto
Mを，Gのマッチングのうち辺数最大のもののうち「マッチングの端点に含まれない2点間の距離(パスの長さの最小値，連結なのでパスは必ず存在)の最小値」が最小になるようなものとする． #kansaimath #kansaimath407
2016-09-18 16:02:11
y.
@waidotto
|G|は偶数で，Gは完全マッチングを持たないとしたので，Mに含まれない点が少なくとも2つある． #kansaimath #kansaimath407
2016-09-18 16:03:31
y.
@waidotto
その2点v_0，v_mの距離が1だったとすると，それを付け加えたらより辺数の多いマッチングができてしまうので，少なくとも2以上．v_0とv_mを結ぶ最短のパスをとる． #kansaimath #kansaimath407
2016-09-18 16:04:48
y.
@waidotto
そのパスでv_0の次の点v_1を考えると，もしv_1がMの端点でなければ，v_0v_1をMに付け加えることでMより辺数の多いマッチングが作れるので，v_1はMの端点になっている． #kansaimath #kansaimath407
2016-09-18 16:06:55
y.
@waidotto
場合分け:(1)v_1を端点に持つMの辺がv_1v_2だったら，v_0v_1に付け替えるとパスの最短性に矛盾． #kansaimath #kansaimath407
2016-09-18 16:09:31
V-alg-d（ZZ）
@alg_d
無意識にヤバイと発言したark184「これは研究集会の時も(ヤバイとおそらく)言ってますね」 #kansaimath #kansaimath407
2016-09-18 16:09:44
y.
@waidotto
(2)v_1を端点に持つMの辺があるvによりv_1vだったら，さらに場合分けする．v_0，v_1，v_2，vの4点を考えると，K_{1，3}を誘導部分グラフに含まないことより， #kansaimath #kansaimath407
2016-09-18 16:12:42
y.
@waidotto
@waidotto v_0v_1，v_1v_2，v_2v_0のいずれかの辺が存在する．どの場合にも矛盾が導かれる． #kansaimath #kansaimath407
2016-09-18 16:13:05
y.
@waidotto
Sumnerの定理以降，￢(H_1,…,H_n≺G)⟹Gはhogehogeという定理が量産された #kansaimath #kansaimath407
2016-09-18 16:14:57