...是中国邮递员问题.中国邮递员问题的算法中有一种...

精选知识

中国邮递员问题在证明最优解的充要条件时,我们通常都是把原问题化为在图上添加重边,使得原图变为欧拉图,然后使得添加的重边权数和最小.

在充分性证明时,假设最优图添加的重边集合是E1,对应图为G1.满足前面提到的两个充要条件的某种添加的重边集为E2,对应图为G2.那么我们的目标就是证明w(E1)=w(E2)

考虑边集E=E1∪E2\(E1∩E2).

那么如果E为空集,说明E1=E2,此时充分性成立.

如果E不为空集,则E生成的图G[E]中的各个顶点都为偶数.这是因为在G1和G2中,在某个顶点v上添加的边数的奇偶性和d(v)是相同的.(这条是证明重点,理解这条就能理解充分性的证明)

之后的问题就很简单,E中的顶点都为偶数,所以G[E]是若干个欧拉图的并. 又由于E1和E2中各自都不含圈(由E1,E2的定义可知). 所以G[E]中的圈都同时包含E1和E2中的边,又由充要条件2可以推得在G[E]的任何一个圈C中, E1和E2在其上的权重之和都等于w(C)的一半. 从而w(E1\(E1∩E2))=w(E2\(E1∩E2)),即w(E1)=w(E2).

其他类似问题

问题1：证明：G图中v为偶次顶点,dG(v)ω(G-v)≤dG(v)/2[数学科目]

此题应该是每个顶点的度为偶数.

1)v不是割点,则显然成立

2）若v是割点,则设ω(G-v)=n,取其中一个分支G1,点v与G1连的边数只能是偶数,即在G1中连 的边数至少是2,同理对其余的分支也成立,所以分支数最多是

dG(v)/2

所以命题成立.

问题2：设G是一个有p个顶点q条边的图.试证：如果q=1/2(p-1)(p-2)+2,则G是哈密顿图.注：G的一个包含所有顶点的圈称为G的一个哈密顿圈.具有哈密顿圈的图称为哈密顿图.[数学科目]

很陷阱.实际上1/2(p-1)(p-2)就是p-1个点的完全图的边数（就是1到p-2的求和）,在完全图中当然存在任意两点的H路了,再加上2条边正好连上第p个点.

问题3：一道离散数学 图论的题目,含有5个结点,3条边的不同构的简单图有___个.A 2 B 3 C 4 D 5PS:有什么公式可以套公式直接算出来么?有的话请把公式告知.没有公式的话请详细说下思路,主要是我不知道[数学科目]

简单图：无环、无多重边的图.

同构图：两个同阶图（点数为图的阶）,若定点集合与边集合之间在保持关系性质条件下一一对应,则为同构.

公式不知道,但是思路个人认为是列举法.

一共5点3边,且为简单图故必有一点有两边（及此点次为2）：

一是有一点次为3,故每点有2种可能,共10.（但是若题意是将各点视为同样则为1种）.

二是有一点次为0切无次为3的点,则每点仅有1种可能,共5.（但是若题意是将各点视为同样则为1种）.

三是有一点此为2,其余全是1,则每点仅有1种可能,共5.（但是若题意是将各点视为同样则为1种）.

故答案为B

问题4：图论的Show that a simple graph with at least two vertices there must be two vertices that have the same degree[英语科目]

设G是一个n个顶点的简单图,若G含孤立顶点,则它的最大度不超过n-2,由鸽笼原理,一定存在两个点的度数相同；若G不含孤立顶点,则它的最小度大于等于1,最大度小于等于n-1,由鸽笼原理,也一定存在两个点的度数相同.

问题5：某工厂生产由6种不同颜色的纱织成的双色布.已知在品种中,每种颜色至少分别和其他5种颜色中的3种颜色搭配,证明可以挑出3种双色布,它们恰有6种不同的颜色.“由于要恰好6种颜色的布料所[数学科目]

令每个结点表示一种颜色,每条边表示存在一个双色布品种,该品种由端点代表的两个颜色搭配.

该问题转化成：

已知：某个n(G)=6的图G,其每个点的度至少是3,

证明：该图存在一个完美匹配.

证明过程：

下面证明一个更强更一般化的结论,

定理：如果n(G)≥3,且结点的最小度不小于n(G)的一半,则G是哈密顿图.

关于该定理的证明,请参考《图论导引》（第二版,机械工业出版社）的定理7.2.8