離散構造：同時に成立する割当だけを数える
各仕事の選択肢数を掛けると、衝突する割当まで数えてしまう。適格性を関係として表し、完全なマッチングの存在を調べてから、全制約を満たすものを数えよう。
学習順路・例題の編集責任：University Reading List編集プロジェクト。 編集と選定の方法 · 出典確認日:
このページの目次
対象と編集責任
集合、論理、数え上げ、二部マッチングの入門経路。Levin は第4版、Epp は第5版、Lovász らは2003年第1版。架空の割当では仕事と枠を区別し、容量は各1、許可関係を明示する。実組織の予定表の保証ではない。
出発点を選ぶ
無料の探究型がよい
Levin の調査問題と例、選択的なフィードバックを使い、第4版の論理・証明から始める。
問題を通じて深めたい
短い証明を追えて、数え上げやグラフの問題から構造を見たいなら Lovász ら。
三冊を比較する
Discrete Mathematics: An Open Introduction（離散数学：オープンな入門）
Oscar Levin · 版: 4 · 2025
無料の論理からグラフへの導入
- 選ぶ場面
- 小例を調べてから形式化したいとき。
- 別の教材が適する場面
- 全問解答が必要なときや、旧版と同じ順序を想定するとき。
- 読む範囲
- 第4版の論理・証明、グラフ、数え上げ、数列。例題にはマッチングの内容。
- 限界と注意点
- ヒントと対話的な確認は助けになるが、証明は自分で書く。
選ぶ前に試す
A,B:{1,2}、C:{2,3} の割当を、枠の重複を排除して列挙する。
確認すること: 合法なのは二つ。局所選択の積8が割当数にならない理由を述べる。
Discrete Mathematics with Applications（応用のための離散数学）
Susanna S. Epp · 版: 5 · 2020
論理と関係の体系
- 選ぶ場面
- 数える前に適格性と重複禁止を明示したいとき。
- 別の教材が適する場面
- 論理や証明を省き、グラフの問題だけを解きたいとき。
- 読む範囲
- 第1〜5章の言語と証明、第8章の関係、第9章の数え上げ、第10章のグラフと木。
- 限界と注意点
- グラフ応用の前に広い形式的内容を扱う。WebAssign は別商品。
選ぶ前に試す
仕事から枠への単射 f で、(t,f(t)) が許可関係に入ると書く。
確認すること: 適格性と単射性の両方を述べる。単なる関数では枠の共有が可能。
Discrete Mathematics: Elementary and Beyond（離散数学：初歩とその先へ）
László Lovász; József Pelikán; Katalin Vesztergombi · 2003
問題主導の数え上げとマッチング
- 選ぶ場面
- 例を短い論証へ変え、構造的な説明を求めるとき。
- 別の教材が適する場面
- 形式論理・関係・アルゴリズム記法の完全な課程が必要なとき。
- 読む範囲
- 選択した第1版の数え上げ、グラフ・木、マッチングの章題で探す。
- 限界と注意点
- 短い問いには粘り強さが必要で、授業の未収録分野には体系書を補う。
選ぶ前に試す
追試で隣接する枠が足りない仕事集合を見つける。
確認すること: {A,B,D} は仕事3個、隣接枠2個。枠の総数では解決しない。
準備を確認する
関数と単射を区別できるか
関数は各仕事に一つの枠を与える。単射は異なる仕事が同じ枠を使うことも禁じる。
重複なく数えられるか
仕事3個なら枠の順列6通りを適格性で検査できる。独立でない選択肢をそのまま掛けない。
ホール条件とは何か
各仕事部分集合 S の隣接枠が |S| 個以上あるという条件。個々の仕事だけでなく全部分集合を対象にする。
六つのステップで学ぶ
完了したステップ: 0 / 6
自己記録用のチェックであり、評価ではありません。チェック情報は当サイトに送信されません。
-
関係を描く
読む範囲: Levin のグラフ、Epp の関係。
取り組む課題: 二部グラフと許可された組の表を作る。
確認すること: 仕事同士の辺や隠れた容量を入れない。
-
有効性を形式化
読む範囲: Epp の数学言語と関数。
取り組む課題: 完全な割当の条件を量化して書く。
確認すること: 全仕事を割り当て、組が許可され、枠が重複しない。
-
構成的に数える
読む範囲: Levin または Lovász の数え上げ。
取り組む課題: 全合法割当を列挙し、C の枠が強制される理由を示す。
確認すること: C は3、A と B は1と2を交換する。
-
構造を確認する
読む範囲: マッチングの内容。
取り組む課題: {A,B,C} の空でない部分集合7個の隣接数を表にする。
確認すること: どの部分集合にも不足がなく、存在と数え上げが整合する。
-
壊して修復する
読む範囲: マッチングと追試。
取り組む課題: D と枠4を加え、障害を示してから D→4 を加え再計数する。
確認すること: 枠を増やすだけでは失敗し、一辺の追加で修復する。
-
証明書を区別する
読む範囲: 二つの解答。
取り組む課題: 存在、不可能性、個数のそれぞれの根拠を書く。
確認すること: 具体的割当は存在、ホール違反は不可能性を証明する。個数には尽くした議論が要る。
解答付きの例題
局所選択8通りから合法割当2通りへ
仕事 A,B,C を異なる枠1,2,3へ割り当てる。許可枠は A:{1,2}、B:{1,2}、C:{2,3}。すべての完全割当を求め、ホール条件で存在も確かめよ。
前提
各仕事は一枠を使い、枠の容量は各1。記載した組だけを許可する。仕事・枠には名前があり、確率モデルは仮定しない。
- A と B は1と2を何らかの順序で占める。重複を禁じるので C は3。仕事順の割当は (1,2,3) と (2,1,3)。
- 単独集合の隣接数は2、{A,B} は2、{A,C} と {B,C} は3、全体は3。すべての部分集合がホール条件を満たす。
- 2·2·2=8 は衝突も含む局所選択数で、単射の個数ではない。枠順列6個の検査でも合法なのは二つ。
解答と解釈
完全割当は仕事順 A,B,C で (1,2,3)、(2,1,3) の二つ。
結果を検証する
各組の許可と枠の重複なしを確認する。C=3 が強制され、残る1と2の順列が二つなので列挙は尽くされている。
前提を変えて考える
到達できない空き枠は救済にならない
元の許可関係を保ち、仕事 D の許可枠を {1,2} として枠4も追加する。存在を判定せよ。次に一辺 D→4 を許可関係に追加し、修復後の完全割当数と修復辺数の最小性を説明せよ。
- 修復前は S={A,B,D} の隣接枠が {1,2}。仕事3個を枠2個に単射で写せず、全体で枠が4個あっても不可能。
- D→4 の追加後も A と B は1と2を占めるため、D は4、C は3。A と B は枠を交換できる。
- 仕事順 A,B,C,D で (1,2,3,4)、(2,1,3,4)。辺追加ゼロでは不可能、一辺で可能なので最小辺数は1。ただし修復方法が唯一とは限らない。
解答と解釈
追加辺の前は0通り、D→4 の後は2通り。最小修復辺数は1。
結果を検証する
枠4の容量は仕事が到達できて初めて役立つ。D→4 が唯一の一辺修復だとは主張しない。
よくある誤り
選択を独立だと思う
容量制約で選択が結びつく。積の法則には合法な逐次計数が必要。
全体の総数だけを見る
枠が十分でも一部の仕事に狭いボトルネックがありうる。
存在と個数を混同する
一つの割当やホール定理は存在を判定する。個数には別の尽くした議論が要る。
次に進む前に
- 許可関係を満たす単射として割当を書く。
- 総容量が見逃すホール違反を示す。
- 割当数と最小修復辺数の両方を証明する。
出典と版の確認
出典確認日:
- Author: fourth edition and reorganization
著者は第4版の順序変更、全体の無料公開、CC BY-NC-SA 4.0 を明記する。
- Cengage: exact fifth edition and contents
Cengage は第5版の論理・関係・数え上げ・グラフの単元と別売プラットフォームを示す。
- Springer: selected first-edition softcover
Springer は2003年の該当ソフトカバーと、問題主導の数え上げ・グラフ・マッチングの範囲を示す。
提案する学習活動であり、公式の課題や全巻通読の主張ではありません。