13.4
Matching Theory
313706025 吳冠廷
Matching Theory
Establish a one-to-one correspondence between X and Y.
X
Y
Theorem 13.5
任意取球下
球的數量 ≦ 可以被這些球丟入的箱子數
Theorem 13.5
A
R(A)
No Complete Matching
Proof of Theorem 13.5
1) Introduce new vertices a (source) and z (sink)
2) Draw new edges between a and each edges of X with capacity of 1
3) Draw new edges between z and each edges of Y with capacity of 1
4) Assign each edges in G the capacity M, M ≧ |X|
⇒
Proof of Theorem 13.5
Proof of Theorem 13.5
Every cut in network N has atleast capacity of |X|
Example 13.14
Example 13.14
⇒
Example 13.14�
Corollay 13.3
MAX(每顆球能丟進的箱子數) ≧ k ≧ MAX(每個箱子能被多少顆球丟進去)
Definition 13.6
Definition 13.7
A
R(A)
Theorem 13.6
Example 13.18
A telephone switching network is built to route telephone calls from incoming lines to outgoing trunk lines. There are 30 incoming lines, equally divided into the three categories I, II, and III, and there are 24 outgoing trunk lines. Each incoming line in category I is connected so that it can be switched to one of four outgoing trunk lines. An incoming line for category II can be switched to one of two outgoing trunk lines; a category III incoming line has only one possible outgoing trunk line for a connection. Furthermore, engineering restrictions are such that the number of incoming lines that can be switched to one outgoing trunk line is at most three. Based on this information, if there are telephone calls at all 30 incoming lines, we want to find a lower bound for the maximum number of these calls that can be switched to the 24 trunk lines at the very least.
Example 13.18
Example 13.18
m
n
p
First category
Second category
Third category
y
Thank you