Konig定理

Konig定理：最少覆盖数==最大匹配数
例题：
 有两台机器A和B及N个需要运行的任务，每台机器有M种不同的模式，而每个任务i都恰好在一台机器上运行，如果他在机器A上运行，则机器A需要设置为模式ai,如果他在机器B上运行，则机器B需要设置为模式bi，每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重新启动一次，请合理为每个任务安排一台机器并合理安排顺序，使得机器重启次数尽量少。
分析：
 本题的建模需要一点技巧。显然，机器重启次数是两台机器需要使用的不同的模式个数，但是如果把每个任务看成一个X节点，把每台机器的每个模式看成一个Y节点，则此模型没有任何意义。应该把每个任务看成一条边，即A机器的每个模式看成一个X节点，B机器的每个模式看成一个Y节点，任务i为边（a,b),本题即为求最少的点让每条边都至少和其中的一个点关联。
根据Koing定理，最少覆盖数==最大匹配数M。证明如下：
设最少覆盖数为m.
1.M>=m.反证法证明：如果存在M<m.也就是说存在一个任务（一条边）aibi.没有边和ai关联，同时没有边和bi关联。显然这两个未覆盖点可以相连，显然此M并非最大匹配。
2.在1的证明下，m==M.考虑最大匹配的这M条边，由于他们两两个无公共点，因此至少需要M个点才能把他们覆盖。