# 離散構造：同時に成立する割当だけを数える — 学習ワークシート

[学習ガイド](https://unireadinglist.com/ja/guides/discrete-structures/)

[科目・テーマ: 離散数学](https://unireadinglist.com/ja/subjects/mathematics/#course-discrete-mathematics)

出典確認日: 2026-11-04

学習順路・例題の編集責任：University Reading List編集プロジェクト。

集合、論理、数え上げ、二部マッチングの入門経路。Levin は第4版、Epp は第5版、Lovász らは2003年第1版。架空の割当では仕事と枠を区別し、容量は各1、許可関係を明示する。実組織の予定表の保証ではない。

## 出発点を選ぶ

- [ ] 無料の探究型がよい
  Levin の調査問題と例、選択的なフィードバックを使い、第4版の論理・証明から始める。

- [ ] 証明の書き方から学びたい
  量化された文、関係、論証の構造を丁寧に練習するなら Epp。

- [ ] 問題を通じて深めたい
  短い証明を追えて、数え上げやグラフの問題から構造を見たいなら Lovász ら。

## 三冊を比較する

### Discrete Mathematics: An Open Introduction（離散数学：オープンな入門）

Oscar Levin · 4 · 2025
無料の論理からグラフへの導入

選ぶ場面: 小例を調べてから形式化したいとき。
別の教材が適する場面: 全問解答が必要なときや、旧版と同じ順序を想定するとき。
読む範囲: 第4版の論理・証明、グラフ、数え上げ、数列。例題にはマッチングの内容。
限界と注意点: ヒントと対話的な確認は助けになるが、証明は自分で書く。

#### 選ぶ前に試す

A,B:\{1,2\}、C:\{2,3\} の割当を、枠の重複を排除して列挙する。
確認すること: 合法なのは二つ。局所選択の積8が割当数にならない理由を述べる。

自分のメモ:

________________________________

ISBN: 9781032966168

[公式の無料教材](https://discrete.openmathbooks.org/dmoi4.html)

[書誌情報と入手方法](https://unireadinglist.com/ja/subjects/mathematics/discrete-mathematics-an-open-introduction/)

### Discrete Mathematics with Applications（応用のための離散数学）

Susanna S. Epp · 5 · 2020
論理と関係の体系

選ぶ場面: 数える前に適格性と重複禁止を明示したいとき。
別の教材が適する場面: 論理や証明を省き、グラフの問題だけを解きたいとき。
読む範囲: 第1〜5章の言語と証明、第8章の関係、第9章の数え上げ、第10章のグラフと木。
限界と注意点: グラフ応用の前に広い形式的内容を扱う。WebAssign は別商品。

#### 選ぶ前に試す

仕事から枠への単射 f で、(t,f(t)) が許可関係に入ると書く。
確認すること: 適格性と単射性の両方を述べる。単なる関数では枠の共有が可能。

自分のメモ:

________________________________

ISBN: 9781337694193

[書誌情報と入手方法](https://unireadinglist.com/ja/subjects/mathematics/discrete-mathematics-with-applications-epp/)

### Discrete Mathematics: Elementary and Beyond（離散数学：初歩とその先へ）

László Lovász; József Pelikán; Katalin Vesztergombi · 2003
問題主導の数え上げとマッチング

選ぶ場面: 例を短い論証へ変え、構造的な説明を求めるとき。
別の教材が適する場面: 形式論理・関係・アルゴリズム記法の完全な課程が必要なとき。
読む範囲: 選択した第1版の数え上げ、グラフ・木、マッチングの章題で探す。
限界と注意点: 短い問いには粘り強さが必要で、授業の未収録分野には体系書を補う。

#### 選ぶ前に試す

追試で隣接する枠が足りない仕事集合を見つける。
確認すること: \{A,B,D\} は仕事3個、隣接枠2個。枠の総数では解決しない。

自分のメモ:

________________________________

ISBN: 9780387955858

[書誌情報と入手方法](https://unireadinglist.com/ja/subjects/mathematics/discrete-mathematics-elementary-and-beyond/)

## 準備を確認する

### 関数と単射を区別できるか

自分のメモ:

________________________________

### 重複なく数えられるか

自分のメモ:

________________________________

### ホール条件とは何か

自分のメモ:

________________________________

## 六つのステップで学ぶ

- [ ] 関係を描く

読む範囲: 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。記載した組だけを許可する。仕事・枠には名前があり、確率モデルは仮定しない。

自分のメモ:

________________________________

## 前提を変えて考える: 到達できない空き枠は救済にならない

元の許可関係を保ち、仕事 D の許可枠を \{1,2\} として枠4も追加する。存在を判定せよ。次に一辺 D→4 を許可関係に追加し、修復後の完全割当数と修復辺数の最小性を説明せよ。

自分のメモ:

________________________________

## 次に進む前に

- 許可関係を満たす単射として割当を書く。
- 総容量が見逃すホール違反を示す。
- 割当数と最小修復辺数の両方を証明する。

## 解答と解釈

### 関数と単射を区別できるか

関数は各仕事に一つの枠を与える。単射は異なる仕事が同じ枠を使うことも禁じる。

### 重複なく数えられるか

仕事3個なら枠の順列6通りを適格性で検査できる。独立でない選択肢をそのまま掛けない。

### ホール条件とは何か

各仕事部分集合 S の隣接枠が |S| 個以上あるという条件。個々の仕事だけでなく全部分集合を対象にする。

### 局所選択8通りから合法割当2通りへ

1. A と B は1と2を何らかの順序で占める。重複を禁じるので C は3。仕事順の割当は (1,2,3) と (2,1,3)。
2. 単独集合の隣接数は2、\{A,B\} は2、\{A,C\} と \{B,C\} は3、全体は3。すべての部分集合がホール条件を満たす。
3. 2·2·2=8 は衝突も含む局所選択数で、単射の個数ではない。枠順列6個の検査でも合法なのは二つ。

完全割当は仕事順 A,B,C で (1,2,3)、(2,1,3) の二つ。

結果を検証する: 各組の許可と枠の重複なしを確認する。C=3 が強制され、残る1と2の順列が二つなので列挙は尽くされている。

### 前提を変えて考える: 到達できない空き枠は救済にならない

1. 修復前は S=\{A,B,D\} の隣接枠が \{1,2\}。仕事3個を枠2個に単射で写せず、全体で枠が4個あっても不可能。
2. D→4 の追加後も A と B は1と2を占めるため、D は4、C は3。A と B は枠を交換できる。
3. 仕事順 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](https://discrete.openmathbooks.org/dmoi4.html)
  著者は第4版の順序変更、全体の無料公開、CC BY-NC-SA 4.0 を明記する。

- [Cengage: exact fifth edition and contents](https://www.cengage.com/c/discrete-mathematics-with-applications-5e-epp/9781337694193/)
  Cengage は第5版の論理・関係・数え上げ・グラフの単元と別売プラットフォームを示す。

- [Springer: selected first-edition softcover](https://link.springer.com/book/10.1007/b97469)
  Springer は2003年の該当ソフトカバーと、問題主導の数え上げ・グラフ・マッチングの範囲を示す。

提案する学習活動であり、公式の課題や全巻通読の主張ではありません。

[編集と選定の方法](https://unireadinglist.com/ja/editorial/)