ark184「サークラなグラフ理論の話」(ヤバイ)

y. @waidotto

完全マッチング:⟺ちょうど1回ずつ現れるマッチング #kansaimath #kansaimath407

水槽ゼリー @Jelly_in_a_tank

とりあえず、ツイート #kansaimath407

y. @waidotto

頂点数が奇数だと，明らかに完全マッチングは存在しない．頂点数が偶数でも完全マッチングが存在しないグラフもある．例:K_{1,3} #kansaimath #kansaimath407

y. @waidotto

問題:どういうグラフが完全マッチングを持つか？ #kansaimath #kansaimath407

水槽ゼリー @Jelly_in_a_tank

姫が居ない状況 #kansaimath407

ぶくはん @buku_han

どういうグラフが完全マッチングを持つか #kansaimath #kansaimath407

ぶくはん @buku_han

みんな大好き結婚定理 #kansaimath #kansaimath407

水槽ゼリー @Jelly_in_a_tank

ふしだらな女がいなければ完全マッチング #kansaimath407

V-alg-d（ZZ） @alg_d

No絵心さんの登場 #kansaimath #kansaimath407

みい@固定ツイ見て @rakunaria

0.01秒どころか10億分の1秒でした #kansaimath407

セシル☆ @sesiru8

みんな大好き結婚定理 #kansaimath #kansaimath407

y. @waidotto

Thm(結婚定理):∀S⊂V(G) |N(S)|≥|S|なる二部グラフGは完全マッチングを持つ(N(S)はSに辺でつながっている，S以外の点(Sの近傍)) #kansaimath #kansaimath407

y. @waidotto

3．誘導部分グラフ #kansaimath #kansaimath407

my_trash(いとら) @mytrashing

完全マッチングをもつための条件を不変量で表す #kansaimath407

セシル☆ @sesiru8

あ、頂点数も辺の数も同じだからメッチャ似てる！！ #kansaimath #kansaimath407 pic.twitter.com/n47dBayKnU

拡大

y. @waidotto

頂点数と辺数が等しいからといって，グラフが似ているわけではない #kansaimath #kansaimath407

y. @waidotto

最小次数が4のグラフ:頂点を円環状に並べて各頂点から隣と2つ隣に辺を張ったグラフ，K_5をたくさん並べたグラフ，格子状のグラフ．これらも互いに"似ていない"． #kansaimath #kansaimath407

ぶくはん @buku_han

不変量だけの情報ではグラフの情報としては不十分→誘導部分グラフを考える #kansaimath #kansaimath407

y. @waidotto

Def.HがGの誘導部分グラフ:⟺Gの頂点のいくつかとその間を結ぶ全ての辺をとるとHになる #kansaimath #kansaimath407

セシル☆ @sesiru8

なるほど！目標は完全に理解した！ #kansaimath #kansaimath407

y. @waidotto

部分グラフであっても，誘導部分グラフであるとは限らない #kansaimath #kansaimath407

f_jhr @f_jhr

グラフ理論、絵を描いたら理解できるのはいいなあ #kansaimath #kansaimath407

y. @waidotto

￢(K_{1,3}≺G)なるグラフGを「K_{1,3}を禁止したグラフ」という #kansaimath #kansaimath407

y. @waidotto

グラフ禁止型ほげほげ．禁止グラフを追加できる．禁止追加型グラフ！ #kansaimath #kansaimath407

y. @waidotto

今回の目標の定理の名前がSumnerの定理(1974)． #kansaimath #kansaimath407