举例 《集合论与图论》第18讲
《集合论与图论》第18讲 11 举例
举例(续) 《集合论与图论》第18讲
《集合论与图论》第18讲 12 举例(续)
反例:非充分条件 上述条件只是必要条件而不是充分条件 秦反例: Petersen图 Petersen图满足:V1≠,p(GV1)sV Petersen图不是哈密顿图:穷举 Petersen图是半哈密顿图 《集合论与图论》第18讲 13
《集合论与图论》第18讲 13 反例: 非充分条件 上述条件只是必要条件,而不是充分条件 反例: Petersen图 Petersen图满足: ∀V1≠∅, p(G-V1)≤|V1| Petersen图不是哈密顿图: 穷举 Petersen图是半哈密顿图
无向半哈密顿图的充分条件 定理7:设G是n(2)阶无向简单图,若对G 中任意不相邻顶点u与v有 d(u)+d()≥n-1 则G是半哈密顿图 秦证明:(1)G连通 2)由极大路径得圈 3)由圈得更长路径 路径-极大路径-圈-更长路径 更长极大路径-更长圈-更长路径-.….-哈密顿通路 《集合论与图论》第18讲
《集合论与图论》第18讲 14 无向半哈密顿图的充分条件 定理7: 设G是n(≥2)阶无向简单图,若对G 中任意不相邻顶点u与v有 d(u)+d(v)≥n-1 则G是半哈密顿图. 证明: (1) G连通 (2) 由极大路径得圈 (3) 由圈得更长路径 路径--极大路径--圈--更长路径 ---更长极大路径--更长圈--更长路径--……--哈密顿通路
定理7(证明(1)(3) 证明:(1)G连通:uv(u,)∈E aW(uW)∈EWv∈E)n2 (3)由圈得更长路径:连通 《集合论与图论》第18讲 15
《集合论与图论》第18讲 15 定理7(证明(1)(3)) 证明: (1) G连通: ∀u∀v( (u,v)∉E→ ∃w((u,w)∈E∧(w,v)∈E ) (3) 由圈得更长路径: 连通 n-2