“場合の数”を俯瞰する&グラフ理論の”結婚定理”

“現代応用数学の基礎(1)” というのを借りて本日読了.
日本評論社から数学セミナーの別冊として刊行された本書は現在は絶版のようで
3章立てで,第一章フーリエ級数と超関数,第二章組合せ論,第三章グラフ理論 となっている.

でも,日本評論社のHPで”現代応用数学の基礎”シリーズを見つけた.
どうやら,フーリエ級数と超関数で一冊に,第二章と第三章は”組合せ論・グラフ理論”として分けられて再販してる模様.

Amazonマーケットプレイスか,日本評論社のHPから手にすることができるらしい.

学んだことを書き残しておく.

次のような,場合の数の問題を考える.

領域1,2,3…mに色1,2,3…nを塗る.
(1) 何の制限もなく,全領域で色を塗るのは何通りか.
(2) 同じ色を二回以上使わない色の塗り方は何通りか.
(3) 全部の色をどこかで使う色の塗り方は何通りか.
(4) m=nとして,全部の色をちょうど1回使う色の塗り方は何通りか.

この4題の問題は全て別々のように思えるが,実は見通しよく考えることができる.

そのためには写像についての復習をする.

有限集合X,Yがあり,写像f:X\rightarrow Yとする.|X|は集合Xの要素の個数を表して,|X|=m,|Y|=nとおく.

fが単射とは,f(x_1)=f(x_2) \Rightarrow x_1 =x_2で,m \leq nが成立.変数値が異なれば関数値も異なるということ.

fが全射とは,\forall y, \exists x s.t. f(x)=yで,m \geq nが成立.対応もれがないということ.

fが全単射とは,単射であり全射であること.m = nが成立.

そして次が成立する.証明は本書を参照せよ.

  1. XからYへの写像の全体M(X,Y)
    |M(X,Y)|=n^m
  2. XからYへの単射の全体I(X,Y)
    |I(X,Y)|=n(n-1)(n-2)\cdots (n-m+1)
  3. XからYへの全単射の全体S(X,Y)
    |S(X,Y)|=\displaystyle \sum _{k=0}^{n} (-1)^k {}_{n}C_{k} (n-k)^m
  4. XからYへの全単射の全体B(X,Y)
    |B(X,Y)|=n!

これを用いれば,彩色問題は領域という有限集合Xから,色という有限集合Yへの写像を考えたらよい.

何の制限もなく色を塗るのは写像の全体に対応し,
同じ色を二回以上使わずに色を塗るのは使わない色があってもよいということだから,単射の全体に対応し,
全部の色をどこかで使って色を塗るのは色の重複があるから,全射の全体に対応し,
全部の色をちょうど一回使うのは,全単射に対応する.

だから,上の問題の解答は

(1) n^m
(2) n(n-1)(n-2)\cdots (n-m+1)
(3) \displaystyle \sum _{k=0}^{n} (-1)^k {}_{n}C_{k} (n-k)^m
(4) n!

となる.場合の数の問題を考えるときは写像の概念が背景にあったんだな.知ってると問題を俯瞰できるかも.

もうひとつは,グラフ理論の”結婚定理”の話.

ずばり,皆が幸せになる結婚は存在するか,という定理である.

同人数の男性と女性の2グループを想定する.それぞれの女性は結婚してもよいと思う男性が何人かいて,それぞれの男性は自分と結婚してもよいと思っている女性と結婚できれば幸せである.ここで,全員が幸せになるような組合せ(結婚)は可能だろうか.

たとえば,A子はa男,b男,d男となら結婚しても良いと考えているとする.B子はa男,c男となら結婚しても良いと考えているとする.C子はc男しか妥協しないお高き女で.D子はa男とc男となら結婚しても良いと考えている.

この時,全員が結婚できるだろうか?グラフ理論ではこれを”完全マッチング”という.

そして,この女性の集合をV={A,B,C,D}, 男性の集合をE={a,b,c,d}として,グラフG=(V,E)のようにかく.

つぎに,N(U)はU内の女性から好意のある男全体の集合とする.たとえばN({A,B,C,D})={a,b,c,d},N({B,C,D})={a,c}である.

結婚定理
空でない有限集合V_1 ,V_2に対する2部グラフG=(V_1 \cup V_2 ,E)について,
すべてのU\subseteq V_1について|U|\leq |N(U)| \Leftrightarrow G上の完全マッチングが存在する.

だから,今回の例では|N({A,B,C,D})|=|{a,b,c,d}|=|{A,B,C,D}|=4であるが,|N({B,C,D})|=|{a,c}|=2 \leq |{B,C,D}|=3であるから,G上の完全マッチングは存在しない.つまり,C子のワガママのせいでみんなの結婚が御破算となったwww

組合せ論やグラフ理論も面白いかもなー

広告

“場合の数”を俯瞰する&グラフ理論の”結婚定理”」への1件のフィードバック

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中