|
合コンです(婚活パーティーと呼ぶのがよいかもしれません).男女7人ずつが出席しているとします.宴も酣(たけなわ)となったところで,それぞれの出席者に,結婚してもよいと思った異性を,複数回答可で挙げてもらい,お互いにそう思っているペアの中から,なるべくたくさん結婚するペアを作ることを考えます.
すると、お互いに結婚してもよいと思っているペアを辺で結べば,下のようなグラフが出来上がりました.
試しにペアを作ってみました.
このような辺の選び方をマッチングと呼びます.男女が1人ずつペアにならずに余っていますが,この合コンの場合、うまく全員が結婚できるような組合せがあるでしょうか.あるならその組み合わせを求め、なければその理由を述べてください。
解答
上記サイトより Orz〜
「実は答えはノーです.その理由は上の図を見れば一目瞭然です.二重丸になっている4頂点のつながっている先が,併せて3頂点しかありませんので,4人のうちの一人は余ってしまうことになります.
|

- >
- Yahoo!サービス
- >
- Yahoo!ブログ
- >
- 練習用



