第六节哈密尔顿图(2) (1 是题W要:处 姜示在G 中删 除S中的点 以S为端点 的边后所构成的图;WGS表示GS的 连通分支数 (2)设G=(VE)是η阶无向简单图,若对G中 任意丕相邻的顶点uV都有d(u)+d( 2n-1,则G存在哈密尔顿路,因此G是半 哈密尔顿图; (3)设G是n阶简单图,则是哈密尔顿图当 且仅当其闭包是哈密尔顿图. 返回本章首页 2021/1212021/1/21 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阶简单图，则是哈密尔顿图当 且仅当其闭包是哈密尔顿图. 返回本章首页