本次课主要内容 度极大非哈密尔顿图与TSP问题 (一)、度极大非哈密尔顿图 (二)、TSP问题
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 1 本次课主要内容 (一)、度极大非哈密尔顿图 (二)、TSP问题 度极大非哈密尔顿图与TSP问题
(一)、度极大非哈密尔顿图 1、定义 定义1图G称为度极大非H图，如果它的度不弱 于其它非H图。 2、Cm.n图 定义2对于1≤m<n/2,C,n图定义为： Cmn=KnV(区n+K,2m) 例如，作出C1,s与C25
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 1、定义 (一)、度极大非哈密尔顿图 定义1 图G称为度极大非H图，如果它的度不弱 于其它非H图。 2、C m,n图 定义2 对于1≦ m <n/2 ,C m,n图定义为： , 2 ( ) C K K K m n m m n m = + − 例如，作出C1,5与C2,5
C25 3、Cm.n的性质 引理1对于1≤m<n/2的图C。,n是非H图。 证明：取S=V(k),则o(G-S)=m+1>S=m,所以 由H图的性质知，G是非图。 4、度极大非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 3、Cm,n的性质 K1 K1 K3 C1,5 K2 K2 K1 C2,5 引理1 对于1≦m<n/2的图Cm,n是非H图。 证明：取S=V(km),则ω(G-S)=m+1>|S|=m,所以， 由H图的性质知，G是非H图。 4、度极大非H图的特征
定理1(Chvatal,.1972) 若G是n≥3的非H单图，则G度弱于某个C。,n图。 证明：设G是度序列为(4，山2，d)的非H单图， 且d1≤d2≤.≤dn,n≥3。 由度序列判定法：存在m<n/2,使得dm≤m,且dnn血. 于是，G的度序列必弱于如下序列： m n-2m (m,m,.,m,n-m-1,n-m-1,n-m-1,n-1,n-1,n-1 而上面序列正好是图Cm的度序列。 注：(1)定理1刻画了非H单图的特征：从度序列角度 看，Cmn图族中每个图都是某个阶非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 4 定理1 (Chvátal,1972) 若G是n≧3的非H单图，则G度弱于某个Cm,n图。 证明： 设G是度序列为 (d1 ,d2 ,.,dn )的非H单图， 且d1≦d2≦.≦dn , n≧3。 由度序列判定法：存在m<n/2,使得dm≦m,且dn-m<n-m. 于是，G的度序列必弱于如下序列： 2 ( , ,., , 1, 1,., 1, 1, 1,., 1 m n m m m m m n m n m n m n n n − − − − − − − − − − 而上面序列正好是图Cm,n的度序列。 注： (1) 定理1刻画了非H单图的特征：从度序列角度 看，Cm,n图族中每个图都是某个n阶非H单图的极图
(2)定理的条件是充分条件而非必要条件。 例如：当n=5时，其度极大非H图族是：C1,s与 C2,5 C25 C1.s的度序列是：(1,3,3,3,4)，C2s的度序列是 (2,2,2,4,4)。 而5阶圈C5的度序列是：(2,2,2,2,2)，它度弱于C25? 但是Cs是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 5 (2) 定理的条件是充分条件而非必要条件。 例如：当n=5时，其度极大非H图族是：C1,5与 C2,5 K1 K1 K3 C1,5 K2 K2 K1 C2,5 C1,5的度序列是：(1,3,3,3,4), C2,5的度序列是 (2,2,2,4,4)。 而5阶圈C5的度序列是: (2,2,2,2,2),它度弱于C2,5, 但是C5是H图