本次课主要内容 度极大非哈密尔顿图与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 2 本次课主要内容 (一)、度极大非哈密尔顿图 (二)、TSP问题 度极大非哈密尔顿图与TSP问题
(一)、度极大非哈密尔顿图 1、定义 定义1图G称为度极大非H图，如果它的度不弱 于其它非H图。 2、Cmn图 定义2对于1≤m<n/2,Cmn图定义为： Cmn=KmV(区m+Kn2m〉 例如，作出C1s与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 3 1、定义 (一)、度极大非哈密尔顿图 定义1 图G称为度极大非H图，如果它的度不弱 于其它非H图。 2、C m, n图 定义2 对于1≦ m <n/2 , C m, n 图定义为： , 2 ( ) C K KK mn m m n m 例如，作出C1,5与C2,5
图☒ K C25 3、Cn的性质 引理1对于1≤m<n/2的图cmn是非H图 证明：取S=V(km),则o(G-S)=m+1>S=m,所以， 由H图的性质知，G是非H图。 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 4 3、Cm, n的性质 K1 K1 K3 C1,5 K2 K2 K1 C2,5 引理1 对于1≦m <n/2 的图C m, n是非H图。 证明：取S =V( km),则ω(G-S)=m+1>|S|=m,所以， 由H图的性质知，G是非H图。 4、度极大非H图的特征
定理1(Chyatal,1972 若G是n≥3的非H单图，则G度弱于某个Cmn图。 证明：设G是度序列为(4,4，，dn)的非H单图， 且d1≤d2≤..≤dn,n≥3。 由度序列判定法：存在m<n/2,使得dm≤m,且dnm. 于是，G的度序列必弱于如下序列： n-2m (m,m,m,n-m-1,n-m-1,,n-m-1,n-1,n-l,,n-1 而上面序列正好是图Cm,的度序列。 注：(1)定理1刻画了非H单图的特征：从度序列角度 看，C%n图族中某个图是某个阶非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 定理1 (Chvátal,1972) 若G是n≧3的非H单图，则G度弱于某个C m, 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 nm m mm mn m n m n m n n n 64 7 48 6 4 4 4 44 7 4 4 4 4 48 6 4 447 4 448 而上面序列正好是图Cm,n的度序列。 注： (1) 定理1刻画了非H单图的特征：从度序列角度 看，Cm, n图族中某个图是某个n阶非H单图的极图
(2)定理的条件是充分条件而非必要条件。 例如：当n=5时，其度极大非H图族是：C1s与C25 K2 C1s的度序列是：(1,3,3,3,4)，C25的度序列是(2,2,2,4,4)。 而5阶圈C的度序列是：(2,2,2,2,2)，尽管它度弱于C25) 但是C是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 (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图