华罗庚学校数学教材(六年级下)第08讲图论中的匹配与逻辑推理问题

本系列共14 讲第八讲图论中的匹配与逻辑推理问题.文档贡献者：与你的缘先看一个例题.中、日、韩三个足球队进行比赛，已知 A 不是第一名，B不是韩国队，也不是第二名，第一名不是日本队，中国队第二.问A、B、C各代表哪国队？各是第几名？一般解这类题都归于逻辑推理类问题.我们先来降低难度.先只要求你判断出中、日、韩各是第几名（不必判断 A、B、C）.可以把中、日、韩各用一个点代表，列于上一行.第一、二、三名各用一个点代表，列于下一行，记为：V1=｛中，日，韩｝，V2=｛第1 名，第2 名，第3 名｝.V1 中的点与V2 中某一个点有肯定关系的，就画一条实线，如和②.否定关系的两点之间画一条虚线，如不是②；不是①.把已知条件不加任何推理地表现于图上.虚线 2 条，实线 1 条，共3 条线.现在，有两个明显的事实；第一，V1 中每点有且只有一条实线与V2 中相应点配对，V2 中每点有且只有一条实线与V1 中相应点配对.V1 内部点之间不会有线相联结，V2 内部点之间也不会有线相联结.第二，从 V1（或 V2）中某一个点，例如说 a 点如发出了一条实线向着 V2（或 V1）中某一个点，例如说 x 点，那么 a 点与V2（或 V1）中其他点之间必然只能用虚线联结.（这是逻辑推理中的排它性）由此，我们很容易将中、日、韩的名次判出.这样的问题，抽象起来可归属于图论中称之为“二分图的匹配”问题.图论的名词术语太多，这里不作详细定义，只是描述性介绍一下，大家以前在“一笔画”等讲中已初步接触.所谓二分图，就是顶点集合可以划分成两个部分，V=V1＋V2，如 V1 有 p 个点，记为 V1=｛v1，v2…，vp｝，V2 有q 个点，记为 V2=｛vp+1，vp+2…，vp+q｝，而V1 中任意一点，不会与 V1 中其他点联结，而只能与 V2 中某些点联结；V2 也如此.大家看几个例.一般的图记为 G＝（V，E），V 是顶点集合，E 是边（也可称为线）的集合.大家在哥尼斯堡七桥问题中已领略过这种抽象.现在的二分图是一类特殊的图，只不过顶点集 V 划分为两部分，而这只能“跨越”于 V1 中某个点和 V2 中另一个点.二分图的匹配问题，就是找一个边的集合，这些边之间都没有公共的端点.关于二分图的匹配，要研究的是“最大匹配”，即找一个边最多的匹配.就本讲开始引入的问题看，我们还没有解完，因为还有 A、B、C 三个代号到底如何归于中、日、韩三队的问题.一种解题办法，是把已判出的国籍和名次捆绑在一个顶点内，如（中2）、（韩 1）、（日 3...