本次课主要内容 超哈密尔顿图与超可迹图问题 (一)、超H图与超可迹图 (二)、E图和H图的关系
0.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 2 本次课主要内容 (二)、E图和H图的关系 超哈密尔顿图与超可迹图问题 (一)、超H图与超可迹图
(一)、超H图与超H迹 定义1若图G是非H图，但对于G中任意点v,都有G-v是 H图，则称G是超H图。 定理1彼得森图是超H图。 彼得森图 证明：(1)证明彼得森图是非H图
0.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 3 定义1 若图G是非H图，但对于G中任意点v,都有G-v是 H图，则称G是超H图。 (一)、超H图与超H迹 定理1 彼得森图是超H图。 1 7 6 5 4 2 3 彼得森图 10 9 8 证明： (1) 证明彼得森图是非H图
若不然，设C是G的H圈。 对于边12,17,15来说，必然有两条边在C中。不失一般性， 假定17,12在C中，那么，56,54也必然在C中。 彼得森图 又对于边28,23来说，在前面情况下，必有一条在C中 分两种情形讨论
0.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 4 若不然，设C是G的H圈。 1 6 5 4 2 3 7 彼得森图 10 9 8 又对于边28，23来说，在前面情况下，必有一条在C中。 分两种情形讨论。 对于边12, 17,15来说，必然有两条边在C中。不失一般性， 假定17,12在C中，那么，56，54也必然在C中
情形1：假如28在C中，则39,34在C中，从而710)，8(10) 在C中 彼得森图 但这样得到圈：17(10)821。所以该情形不能存在
0.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 5 1 6 5 4 2 3 7 彼得森图 10 9 8 但这样得到圈：17(10)821。所以该情形不能存在。 情形1：假如28在C中，则39，34在C中,从而7(10), 8(10) 在C中
情形2：假如23在C中，则86,810)在C中，从而39,79在C 中. 彼得森图 彼得森图 但这样得到圈：123971。所以该情形也不能存在。 上面推理说明，G中不存在H圈，即彼得森图是非H图。 6
0.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 但这样得到圈：123971。所以该情形也不能存在。 情形2：假如23在C中，则86，8(10)在C中,从而39, 79在C 中. 1 6 5 4 2 3 7 彼得森图 10 9 8 1 6 5 4 2 3 7 彼得森图 10 9 8 上面推理说明，G中不存在H圈，即彼得森图是非H图