证明方法一:(假设该图为哈密尔顿图,则其必须满足哈密尔顿图的必要条件。)
-------
哈密尔顿图的必要条件: 若G=(V,E) 是一个哈密尔顿图,则对于V的每一个非空子集S,均有
W(G-S) ≤|S| 其中W(G-S)表示图G擦去属于S中的顶点后,剩下子图的连通分枝的个数。
-------
证明:
1. 设矩阵(1,4)的点(第一行第4列的那个点)为图G的顶点集合V的非空子集S。将其擦去。
2. 剩下的顶点所能构成的连通图W(G-S)有2个,如下图蓝色区域和绿色区域。
3. 因为剩下的子图中,连通分枝有2个,大于S的顶点个数(我们只擦去了1个点),所以不满足哈密尔顿图的必要条件。
所以:该图不是哈密尔顿图。

-------
哈密尔顿图的必要条件: 若G=(V,E) 是一个哈密尔顿图,则对于V的每一个非空子集S,均有
W(G-S) ≤|S| 其中W(G-S)表示图G擦去属于S中的顶点后,剩下子图的连通分枝的个数。
-------
证明:
1. 设矩阵(1,4)的点(第一行第4列的那个点)为图G的顶点集合V的非空子集S。将其擦去。
2. 剩下的顶点所能构成的连通图W(G-S)有2个,如下图蓝色区域和绿色区域。
3. 因为剩下的子图中,连通分枝有2个,大于S的顶点个数(我们只擦去了1个点),所以不满足哈密尔顿图的必要条件。
所以:该图不是哈密尔顿图。


















