【文件属性】:
文件名称:最终版实验.docx
文件大小:24KB
文件格式:DOCX
更新时间:2023-07-03 15:24:10
数学建模
§5 匹配问题
定义 若 ) ( G E M ⊂ , M e e
j i
∈ ∀ , ,
i
e 与
j
e 无公共端点( j i ≠ ),则称 M 为图
G 中的一个对集; M 中的一条边的两个端点叫做在对集 M 中相配; M 中的端点称为
被 M 许配; G 中每个顶点皆被 M 许配时, M 称为完美对集; G 中已无使 | | | ' | M M >
的对集 ' M ,则 M 称为最大对集;若 G 中有一轨,其边交替地在对集 M 内外出现,则
称此轨为 M 的交错轨,交错轨的起止顶点都未被许配时,此交错轨称为可增广轨。
若把可增广轨上在 M 外的边纳入对集,把 M 内的边从对集中删除,则被许配的
顶点数增加 2,对集中的“对儿”增加一个。
1957 年,贝尔热(Berge)得到最大对集的充要条件:
理 定理 2 M 是图 G 中的最大对集当且仅当 G 中无 M 可增广轨。
1935 年,霍尔(Hall)得到下面的许配定理:
理 定理 3 G 为二分图, X 与 Y 是顶点集的划分, G 中存在把 X 中顶点皆许配的
对集的充要条件是, X S ⊂ ∀ ,则 | | | ) ( | S S N ≥ ,其中 ) ( S N 是 S 中顶点的邻集。
由上述定理可以得出:
论 推论 1: :若 G 是 k 次( ) 0 > k 正则 2 分图,则 G 有完美对集。
所谓 k 次正则图,即每顶点皆 k 度的图。
由此推论得出下面的婚配定理:
理 定理 4 每个姑娘都结识 ) 1 ( ≥ k k 位小伙子,每个小伙子都结识 k 位姑娘,则每位
姑娘都能和她认识的一个小伙子结婚,并且每位小伙子也能和他认识的一个姑娘结婚。
人员分派问题等实际问题可以化成对集来解决。
人员分派问题:工作人员
n
x x x , , ,
2 1
L 去做 n 件工作
n
y y y , , ,
2 1
L ,每人适合做其
中一件或几件,问能否每人都有一份适合的工作?如果不能,最多几人可以有适合的工
作?