文件名称：最终版实验.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 ，每人适合做其 中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工 作？