例2下图G是非H图。 图G 证明：因为在G中，边v是割边，所以它不在G的任 意圈上，于是u与v不能在G的同一个圈上。故G不存在 包括所有顶点的圈，即G是非H图。 定义2如果存在经过G的每个顶点恰好一次的路，称 该路为G的哈密尔顿路，简称H路。 图G0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 例2 下图G是非H图。 证明：因为在G中，边uv是割边，所以它不在G的任 意圈上，于是u与v不能在G的同一个圈上。故G不存在 包括所有顶点的圈，即G是非H图。 图G u v 定义2 如果存在经过G的每个顶点恰好一次的路，称 该路为G的哈密尔顿路，简称H路。 u v 图G