第六节哈密尔顿图(2) 子集看W 顿图,则对V的任 其中GS 美示在G中删除S中的点以及少S为端点 的边后所构成的图;WG)表示G的 连通分支数 (2设G=E是n阶无向简单凰,若对G中 任意不相邻的顶点u都有d)+d 2n-1则G存在哈密尔顿路,因此G是半 哈密尔顿图; 3)设G是n阶简单图,则是哈密尔顿图当 且仅当其閉包是哈密尔顿图 返回本章首页 2021/2/202021/2/20 10 第六节 哈密尔顿图(2) (1)设G=(V,E)是哈密尔顿图，则对V的任 意非空子集S均有W(G-S) ≦|S|,其中G-S 表示在G中删除S中的点以及以S为端点 的边后所构成的图；W(G-S)表示G-S的 连通分支数; (2)设G=(V,E)是n阶无向简单图，若对G中 任意不相邻的顶点u,v都有d(u)+d(v) ≧n-1,则G存在哈密尔顿路，因此G是半 哈密尔顿图； (3)设G是n阶简单图，则是哈密尔顿图当 且仅当其闭包是哈密尔顿图. 返回本章首页