离散数学第七章图论范例.ppt

第七章 图 论 在下图中，G1，G2，G3均是G的真子图，其中G2、G是G的生成子图。 例8、 画出K4的所有非同构的生成子图。 解： K4的所有非同构的生成子图如下图所示。 【例8.1.4】 证明在n（n≥2）个人的团体中，总有两个人在此团体中恰好有相同个数的朋友。 解 以结点代表人，二人如果是朋友，则在代表他们的结点间连上一条边，这样可得无向简单图G，每个人的朋友数即图中代表它的结点的度数，于是问题转化为：n阶无向简单图G中必有两个结点的度数相同。 用反证法，设G中各顶点的结数均不相同，则度数列为0，1，2，…，n-1，说明图中有孤立结点，这与有n-1度结点相矛盾（因为是简单图），所以必有两个结点的度数相同。 【例8.2.1】 一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？ 解 这是通路问题的一个典型实例。用f表示人，w表示狼，s表示羊，h表示草。 集合{f，w，s，h}中能平安在一起的子集有：{f，w，s，h}，{f，w，s}，{f，s，h}，{f，w，h}，{f，w}，{f，s}，{f，h}，{w，h}，{f}，{w}，{s}，{h}。用顶点表示渡河过程中的状态，状态是二元组：第一元素是集合{f，w，s，h}在渡河过程中留在原岸的子集，第二元素是在彼岸的子集，将一次渡河后代表状态变化的顶点间连边，得图8.2.1。容易看出，一条路径就是一种渡河方案。 【例8.2.4】 在一次国际会议中，由七人组成的小组{a,b,c,d,e,f,g}中，a会英语、阿拉伯语；b会英语、西班牙语；c会汉语、俄语；d会日语、西班牙语；e会德语、汉语和法语；f会日语、俄语；g会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可通过别人翻译）？ 解 用顶点代表人，如果二人会同一种语言，则在代表二人的顶点间连边，于是得到图8.2.3。问题归结为：在这个图中，任何两个顶点间是否都存在着通路？由于图8.2.3是一个连通图，因此，必要时通过别人翻译，他们中间任何二人均可对话。 在连通图中，如果删去一些顶点或边，则可能会影响图的连通性。所谓从图中删去某个顶点v，就是将顶点v和与v关联的所有的边均删去，我们用G-v记之，并用G-V′表示从G中删去V的子集V′。用G-e表示删去边e，用G-E′表示从G中删去E的子集E′。 【例8.4.1】 判断下列各命题是否是真命题。 （1）任何有相同顶点数和边数的无向图都同构。 （2）图中的初级回路均是简单回路。 （3）任一图G的最大度数Δ（G）必小于G的顶点数。 （4）在n（n≥2）个人中，不认识另外奇数个人的有偶数个人。 解答与分析 （1）假命题。两个图有相同顶点数和边数是二图同构的必要条件，而非充分条件。 （2）真命题。由初级回路和简单回路的定义可知。 （3）假命题。当G非简单图时，Δ（G）可大于顶点数。 （4）真命题。将n个人抽象成n个顶点，若两个人不认识，则在他们的对应顶点之间画一条边，得到无向图G。G中每个顶点的度数就是该顶点所对应的人不认识的其他人的个数，由握手定理的推论可知，G中奇度数的顶点必有偶数个。故在n个人中，不认识另外奇数个人的有偶数个人。 【例8.4.2】 在六个人的团体中，至少有三个人彼此认识或彼此不认识。 分析 将六个人抽象成六个顶点，若两个人认识，则在他们的对应顶点之间画一条边，得到无向图G，则G是6阶无向简单图， 中的边则表示他们关联的两个顶点代表的人彼此不认识，本题即：证明G或它的补图 中存在3个顶点彼此邻接。 解 因为K6是5-正则图，所以v∈V（G）（v∈（ ）），d（v）在G中或在 中大于等于3。不妨设在G中d（v）≥3，则v在G中至少关联三个顶点设为a、b、c（见图8.4.1），若此三顶点在G中彼此不邻接，则必有三边（a，b）、（a，c）、（b，c）均在 中（图中虚线），亦即a、b、c三点在 中彼此邻接，否则三顶点至少有两个在G中邻接，不妨设（a，b）∈E（G），则v、a、b为在G中彼此邻接的三顶点，故在G或 中存在3个顶点彼此邻接。 【例8.4.3】 证明无向图G与其补图 至少有一个是连通图。