资源描述：
《第八讲图论中的匹配与逻辑推理问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第八讲图论中的匹配与逻辑推理问题先看一个例题•中、H、韩三个足球队进行比赛，已知A不是第一名,B不是韩国队，也不是第二名，第一名不是日木队，中国队第二•问A、B、C各代表哪国队？各是第几名？一般解这类题都归于逻借推理类问题.我们先来降低难度•先只要求你判断出中、日、韩各是第几名（不必判断A、B、C）•可以把中、日、韩各用一个点代表，列于上一行•第一、二、三名各用一个点代表，列于下一行，记为：Vl=｛中，F1,韩｝,V2=｛第1名，第2名，第3名｝.①②VI中的点与V2中某一个点有肯定关系的，就画一条实线，如宙和②.否定关系的两点Z间画一条虚线，如虧不是②；
2、归）不是①•把已知条件不加任何推理地农现丁图上•虚线2条，实线1条，共3条线.现在，有两个明显的事实；第一，VI中每点有且只有一条实线与V2中相应点配对，V2中每点有口只有一条实线与VI中相应点配对・VI内部点Z间不会有线相联结，V2内部点Z间也不会有线相联结•第二，从VI（或V2）中某一个点，例如说a点如发出了一条实线向着V2（或V1）中某一个点，例如说x点，那么a点与V2（或V1）中其他点Z间必然只能用虚线联结.（这是逻辑推理中的排它性）由此，我们很容易将小、日、韩的名次判出.这样的问题，抽象起来可归屈于图论中称Z为“二分图的匹配”问题.图论的名词术语
3、太多，这里不作详细定义，只是描述性介绍一下，大家以前在“一笔画”等讲中已初步接触.所谓二分图，就是顶点集合可以划分成两个部分，V二V1+V2,如VI有p个点，记为Vl=｛vl,v2・・・，vp｝,V2有q个点，记为V2二｛vp+1,vp+2…，vp+q｝,而Vl中任意一点，不会与VI屮其他点联结，而只能与V2屮某些点联结；V2也如此•大家看几个例.一般的图记为G=（V,E）,V是顶点集合，E是边（也可称为线）的集合•大家在哥尼斯堡七桥问题中已领略过这种抽象•现在的二分图是一类特殊的图，只不过顶点集V划分为两部分，而这只能“跨越”于VI中某个点和V2中另一个
4、点•二分图的匹配问题，就是找一个边的集合，这些边之间都没有公共的端点.关于二分图的匹配，要研究的是“最大匹配”，即找一个边最多的匹就本讲开始引入的问题看，我们述没有解完，因为还有A、B、C三个代号到底如何归于中、FI、韩三队的问题•一种解题办法，是把已判岀的国籍和名次捆绑在一个顶点内，如仲2）、（韩1）、（日3）,再和A、B、C构造一个新的二分图：显然，推知1^是（R3）,因为B有2条虚线，而必然有1条实线，只能推出B与（日3）Z间为实线•同理，（韩1）只能为C；剩下的唯一的情况留给了A为（中2）•全部问题解决了.再看最初的题目，如果你选择先判断中、FI、
5、韩和A、B、C三个代号之间的匹配关系，将会怎样呢？画一个图看，利用已知条件陆出实、虚线.®®©只能利用B不是韩国队及中国队笫二，B不是第二（因此B不是中国队）这样一些条件，题口屮另二句话：A不是第一•名，第一名不是日本队,这种否定关系之间，没有传递性，你不能判定A是不是R本队•因此根据已知条件所画的图中只有两条虚线，Z后最多只能确定口、BZ间为实线.所以对这样的二分图，无法找出合理的最大匹配•这方法使问题求解走进了死胡同.那么你选择先判A、B、C和第一、第二、第三名之间的匹配关系，又会怎样呢？画一个图看.®®®©现在也只有二条虚线，仍然无法找出最大匹配，或
6、说解不唯一，对求解问题无助.现在冋过头來看，先找国别与名次之间的匹配，似乎有些“碰运气”，因为完全可以把题H改动，使先找国别与名次的匹配无法解决，例如叙述改为：屮、日、韩三足球队比赛，已知结果为：第1名不是A,第2名不是韩国队也不是B,A不是R本队，中国队为B,问A、B、C,和1、2、3名与各国队如何匹配？细心读者发现，这只是把原题屮A、B、C的地位与1、2、3名的地位互换而已•所以现在改动后的题目，再先抓“国别”和“名次”的匹配，就无法求解.但是数学耍求找出一种解一般问题的方法而不是“碰运气”，而且完全可以找一个例子，使得无论取国别与名次；或国别与代号（
7、A,B,C）；或代号与名次这三类二分图的匹配都无法求解，而必须找更广泛意义下的匹配才能解决，为此先介绍一般的三个因素一起考虑的“匹配”方法.先结合前例，将国别用三个不同点表示于上方，三个名次点表示于左下方，三个代号点表示于右下方•用实线的肯定关系和虚线的否定关系把已知条件“翻译”于图上.J我们现在的0的是要寻找一个捆绑三条实线边的一条广义边，使每个国别与一个名次及一个代号捆绑在一起，使问题一次性解决，遵循的原则有以下4条：①肯定关系具有排它性(如中二第2名，则中工第1名，中工第3名,第2名第2名H韩).②肯定关系具有传递性(如己知中二第2名，一旦推知肯定关
8、系第2名二A,那么中二A).③任意两个类别的点之间要建立一种合理的
