マトイドのすべての最大独立セットが同じカーディナリティを持つことを証明する方法すべての独立したマトロイドのセットは、同じカーディナリティを持ちます
Bのサブセットであり、BはJに属し、AはJに属し、
Jのメンバー独立したセットと呼ばれます。
これとは逆に、| A | < | B |,は、ではなく、は最大限に独立している。
は、次のベン図（のみ青色部分）\明らかB
Bのカーディナリティは、よりも大きいように、空でないを検討します。また、明確A \ B（のみ橙色部分）さもなければ⊂ Bとして、空で、かつ、定義により、は最大限独立していません。したがって
、交換性により、そのようなB ∪ {X} \ {Y} ∈ Jならびにその一部X ∈ A \ B、Y ∈ B \ Aがあります。このセットをCとしましょう。なお、私たちはためとCを（今青い円はCです）ベン図を引く場合：
| B | = | C |（青い円は同じサイズです）
|（A \ {x}）\ C | < | A \ B |
は、今、私たちはその上のCとについて議論を繰り返し、そしてできる（唯一のオレンジ色の部分は、前よりも小さくなっています）。ただし、Aは有限であると仮定されているため、無限に繰り返すことはできません。したがって、ある時点では、オレンジ色のセットが青色のセットに完全に含まれているという矛盾に達するでしょう。これは以前に見たものは不可能です（つまり、定義上、最大限に独立していないということです）。
我々は矛盾することにより、この使用して証明を行います。 マトロイドのすべての最大独立セットが同じ基数を持たないとしましょう。 したがって、AとBを両方とも最大の独立したセットになるように設定する必要があります。 0のカーディナリティはBの基数よりも小さい。 j A j = Pかつj B j = Q、P < Qとする。 一般性の喪失は、 X 2 A-BとY 2 B-Aとする。 XとYは常に存在するので Aは最大でBとは異なるので、Matroidの2番目の特性を使うと、B1 = f B [X g - f y gも独立集合であり、j B1 j = Qである。 X '2 A-BiとY' 2 Bi-Aから要素を取り出し、X 'を挿入してY'を取り除いて、要素がなくなるまで基数Qのの新しい独立集合を作ることができますA-Bi。 A-Bi = A、Biであるため。しかし、Biもまた基数Qを持つ独立した集合です。今度は はAが矛盾であり、したがって私たちの仮定が最大ではないと言うことができます。さまざまなカーディナリティを設定します。 したがって、すべての独立したマトロイドのセットは同じ基数を持ちます。
私たちの姉妹サイトhttp://math.stackexchange.com/をお試しください。この質問は、プログラミングとは関係がないため、ここでは話題にはなりません。 – Matsmath
私は実際のプログラミングに関する質問ではないので、この質問を議論の対象外とすることに投票しました。数学やコンピュータサイエンスはより良い場所になるかもしれません。 – m69
@ m69私は反対です - これは非常に実用的なアプリケーション（最小限のスパニングツリーなど）を持つ学部のアルゴリズムコースで標準的に教えられているトピックであり、サイトはグラフ理論的な質問で満ちています。いずれにしても、あなたが反対する場合、FYI、OffTopicとして閉じると、別のスタックエクスチェンジに移行することを推奨するオプションが既に存在します。 –