文档介绍：. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . 10 λ k(k= 2,3)- . . . . . . . . . . . . . . . . . . . 15 § λ 3- . . . . . . . . . . . . . . . . . . . . . . . . 16 § λ 3- . . . . . . . . . . . . . . . . . . . . . . . . 19 § λ′- . . . . . . . . . . . . . . . . . . . 23 λ 3- . . . . . . . . . . . . . . . . . . . . . . . . . . 27 § λ 3- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 § -λ 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 λ k- . . . . . . . . . . . . . . . . . . . . . . . . . . 39 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . 42 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . 47 k- ( 250014) κλ 1983 [1] G= (V, E), p∈(0,1) G ε, C h h G P(G, p) P(G, p) = εX h=1 C hp h(1?p) ε?h, G 1?P(G, p). P(G, p) P(G, p) C h. [2] NP [3] 1998 [4] k- 1 G= (V, E), V(G) G E(G) G n(G) =|V|. X?V(G), G[X] X ˉX=V(G)?X. A, B?V(G),[A, B] A B ?(X) =|[X, V?X]| X k G= (V, E) S G k- (R k- ), G?S G?S k G R k- ( λ k- ) G k- λ k(G) λ k. λ k G λ k- λ 2 λ′. ξ k(G) =min{?(X) :X?V(G),|X|=k, G[X] }. G λ k- λ k(G) =ξ k(G), G λ k- G k- k G -λ k ( -λ k ). λ 3- -λ 3 λ 3- -λ 3 λ′- -λ′ ≥6 G λ 3- G (a) x, y∈V(G), d(x, y) = 3 max{d(x), d(y)} ≥?n/2??2, (b) x, y∈V(G), d(x, y) = 2 max{d(x), d(y)} ≥?n/2?, (c)G K