(3)至少有两个m大于1:G是偶图(无奇数长度回路)(2分) (3a)m*m2*m*…*mm是偶数:G是哈密顿图,用归纳法构造哈密顿回 路(2分)。 (3b)m*m2*m*,*mn是奇数:G不是哈密顿图,偶哈密顿图两部分顶 点数相等,总顶点数是偶数(2分) 8.证明或推翻下列命题:“任意给定平面上有限个点,则连接这些点的最短 哈密顿回路的长度不超过连接这些点的最小生成树(不添加额外顶点)的 长度的2倍。子图的长度就是这个子图上的边的长度之和 解答与评分标准 命题成立(2分) (课本图论部分最后一章定理)先求最小生成树奇数度顶点之间的“最 小”匹配,加入匹配“边”得到欧拉图(3分) 沿着欧拉回路前进,“抄近路”避开已经访问过的顶点,就得出哈密顿回 路(3分) 由于距离的三角形不等式,这条哈密顿回路长度不超过最小生成树长度的 2倍(2分)。 9.画出所有非同构的5阶根树 解答与评分标准 9种(每种1分,重复画扣0.5分,全画10分)。非同构的5阶树共有3 种,分别选一个顶点做根。 10.证明或推翻下列命题:“设连通简单平面图G的最小度8(G)≥4,则G的 点色数x(G≥3.” 解答与评分标准 假设X(G)<3.(反证法分情况讨论2分) x(G=1当且仅当G为n阶零图,与已知矛盾。(4分) x(G=2当且仅当G为二部图,因为G为平面图,只能为K2,或K2.此时 必有(G)=2,与已知矛盾。(4分)- 3 - (3) 至少有两个 mj大于 1：G 是偶图（无奇数长度回路）（2 分）。 (3a) m1*m2*m3*…*mn是偶数：G 是哈密顿图，用归纳法构造哈密顿回 路（2 分）。 (3b) m1*m2*m3*…*mn是奇数：G 不是哈密顿图，偶哈密顿图两部分顶 点数相等，总顶点数是偶数（2 分）。 8． 证明或推翻下列命题：“任意给定平面上有限个点，则连接这些点的最短 哈密顿回路的长度不超过连接这些点的最小生成树（不添加额外顶点）的 长度的 2 倍。子图的长度就是这个子图上的边的长度之和。” 解答与评分标准： 命题成立（2 分）。 （课本图论部分最后一章定理）先求最小生成树奇数度顶点之间的“最 小”匹配，加入匹配“边”得到欧拉图（3 分）。 沿着欧拉回路前进，“抄近路”避开已经访问过的顶点，就得出哈密顿回 路（3 分）。 由于距离的三角形不等式，这条哈密顿回路长度不超过最小生成树长度的 2 倍（2 分）。 9． 画出所有非同构的 5 阶根树。 解答与评分标准： 9 种（每种 1 分，重复画扣 0.5 分，全画 10 分）。非同构的 5 阶树共有 3 种，分别选一个顶点做根。 10．证明或推翻下列命题：“设连通简单平面图 G 的最小度δ(G)≥4，则 G 的 点色数χ(G)≥3.” 解答与评分标准： 假设χ(G)<3.（反证法分情况讨论 2 分） χ(G)=1 当且仅当 G 为 n 阶零图，与已知矛盾。（4 分） χ(G)=2 当且仅当 G 为二部图，因为 G 为平面图，只能为 K2,s或 Kr,2. 此时 必有δ(G)=2, 与已知矛盾。（4 分）