極値組合せ論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/20 09:41 UTC 版)
多くの極値的な問題では集合族を扱う。次はその簡単な例である。「要素数nの集合の部分集合の族で、どの2つも交わるようものの最大サイズはいくつだろうか？」 答えは、部分集合全体の数の半分であり、すなわち、2n-1である。証明：Sを要素数nの集合とする。任意の部分集合Tとその補集合S − Tの中で高々1つしか選ぶことができない。これによって、選ぶ部分集合の最大数が部分集合の総数の半分以下になることが証明された。実際にこの数を達成できることを示すためには、Sの1要素xを持ってきて、xを含む全ての部分集合を選べばよい。 より難しい問題は、極値解を特徴付けることである。この場合は、要求を満たしたまま他の選び方をすると最大数が達成できないことを示すことになる。 極値f(n)を見つけることでさえ難しい場合もよくあり、そのときには漸近的な評価を与えることになる。
※この「極値組合せ論」の解説は、「組合せ数学」の解説の一部です。
「極値組合せ論」を含む「組合せ数学」の記事については、「組合せ数学」の概要を参照ください。
ウィキペディア小見出し辞書の「極値組合せ論」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 極値組合せ論のページへのリンク
