Đồ thị và các thuật toán - Chương 2

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

93
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo giáo trình Đồ thị và các thuật toán - Chương 2 Các số cơ bản của đồ thị

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đồ thị và các thuật toán - Chương 2

Chu.o.ng 2 C´c sˆ co. ban cua d` thi ´ ˙ ’ ˙ ¯ˆ . ’ ao o ´ 2.1 Chu sˆ o Kh´i niˆm m` ch´ng ta s˜ d` cˆp o. d ˆy khˆng phu thuˆc v`o su. d. nh hu.´.ng: ta s˜ n´i vˆ eo` e ¯ˆ a ˙ ¯a e.’ ae au o o a . ¯i o e . . . . khˆng phai cung. Dˆ’ tˆ’ng qu´t x´t d a d` thi vˆ hu.´.ng G := (V, E ) c´ n d ınh, m -e o ˙˙ ˙ ’ ˙ ’ canh ch´ o u a e ¯ ¯ˆ . o o o o¯ . -a ` canh v` p th`nh phˆn liˆn thˆng. Dˇt a a ae o . . ρ(G) := n − p, ν (G) := m − ρ(G) = m − n + p. Ta goi ν (G) l` chu sˆ cua d` thi G. ´’ ˆ o ˙ ¯o . a . Dinh l´ 2.1.1 Cho d a d` thi vˆ hu.´.ng G = (V, E ). Gia su. G l` d` thi nhˆn d u.o.c t`. G -. ˙˙ ’’ y ¯ ¯ˆ . o o o a ¯ˆ . a ¯ . u o . ` ng c´ch nˆi hai d ı’nh a v` b cu a G bo.i mˆt canh m´.i; nˆu a v` b tr`ng nhau hoˇc c´ thˆ’ ˙ ´ ´ ¯˙ ˙ ’ ˙’ bˇ a a o a o. o e a u aoe . . .i nhau bo.i mˆt dˆy chuyˆn cu a G th` ´ ` ˙’ ˙ ’ nˆi v´ oo oa e ı . ρ(G ) = ρ(G), ν (G ) = ν (G) + 1; trong tru.`.ng ho.p ngu.o.c lai o . .. ρ(G ) = ρ(G) + 1, ν (G ) = ν (G). Ch´.ng minh. Theo c´ch xˆy du.ng, d a d` thi G c´ n = n d ınh, m = m + 1 canh v` gia su. ¯˙’ a˙˙ ’’ u a a ¯ ¯ˆ . o o . . ` n liˆn thˆng. G c´ p th`nh phˆ e o a a o Nˆu a ≡ b hoˇc c´ mˆt dˆy chuyˆn nˆi a v´.i b. Khi d ´ ph´p biˆn d o’i G th`nh G ˙ ´ ` ´ ´ e aooa e o o ¯o e e ¯ˆ a . . ˙i sˆ th`nh phˆn liˆn thˆng, t´.c l` p = p . Do d ´ ’o a khˆng thay d ˆ ´ ` o ¯o ae o ua ¯o ρ(G ) = n − p = n − p = ρ(G), ν (G ) = m − ρ(G ) = ν (G) + 1. http://www.ebook.edu.vn 49
Ngu.o.c lai, nˆu a = b v` khˆng tˆn tai dˆy chuyˆn nˆi a v` b, th` do c´ch x´c d inh G ´ `.a ` ´ e ao o eo a ı a a ¯. .. ta c´ p = p − 1. Suy ra o ρ(G ) = n − p = n − (p − 1) = n − p + 1 = ρ(G) + 1, ν (G ) = m − ρ(G ) = (m + 1) − (ρ(G) + 1) = m − ρ(G) = ν (G). ˙ ’ Hˆ qua 2.1.2 ρ(G) ≥ 0 v` ν (G) ≥ 0. e a . Ch´.ng minh. Thˆt vˆy, xuˆ t ph´t t`. d` thi th`nh lˆp bˇ ng c´c d ınh cua d a d` thi vˆ ` ´ a ¯˙’ ˙ ¯ ¯o . o ’ u aa a a u ¯ˆ . a o a a ˆ . . . .´.ng G, d ınh no cˆ lˆp v´.i d ınh kia, ta xˆy du.ng G d` n dˆn t`.ng canh mˆt; kho.i d` u ta ˆ`u ¯˙ ’ . o a o ¯˙ ’ ˙ ¯ˆ ’a hu o a aa o . . . . ˜i khi thˆm mˆt canh, th` hoˇc ρ tˇng v` l´c d o ν khˆng d o’i, hoˇc ν tˇng ˙ c´ ρ = 0, ν = 0; mˆ o o e o. ıa a a u ¯´ o ¯ˆ a a . . . v` l´c d o ρ khˆng d o’i. Nhu. vˆy, trong qu´ tr` xˆy du.ng d` thi G , c´c sˆ ρ v` ν chı c´ ˙ ´ ˙o ’ a u ¯´ o ¯ˆ a a ınh a ¯o . ˆ ao a . . ˙ tˇng. ’a thˆe Dˆ’ c´ thˆ’ vˆn dung nh˜.ng kˆt qua phong ph´ cua d ai sˆ vector trong viˆc nghiˆn c´.u, -e o e a ˙ ˙. ´ ´ ˙ ’ u ˙ ¯. o ’ u e e eu . . .`.i ta thu.`.ng d at tu.o.ng u.ng mˆ i chu tr` trong G v´.i mˆt vector theo c´ch sau d ˆy. ˜ ngu o o ¯ˇ ´ o ınh oo a ¯a . . Mˆi canh cua d a d` thi G d` u d u.o.c d .nh hu.´.ng mˆt c´ch t`y y; nˆu chu tr` µ d i ˜ ´ ˙ ¯ ¯o . ’ o. ˆ ¯ˆ ¯ . ¯i e o oa u´ e ınh ¯ . .´.ng v` s lˆn ngu.o.c hu.´.ng th` ta d ˇt c := r − s (nˆu e l` ` a k` ´ qua canh ek , rk lˆn thuˆn hu o a a a o ı ¯a k e ka . . . . k k .´.c s = 0). Vector m chiˆu ` mˆt khuyˆn th` ta luˆn qui u o k o e ı o e . (c1 , c2 , . . . , cm ) goi l` vector chu tr` tu.o.ng u.ng v´.i µ v` k´ hiˆu l` µ (hay l` µ nˆu khˆng thˆ’ gˆy ra ˙ ´ .a ınh ´ o ay e a a e o ea . ˜ ` nhˆm lˆ n). aa C´c chu tr` µ, µ , µ , . . . goi l` d ˆc lˆp nˆu c´c vector chu tr` tu.o.ng u.ng d ˆc lˆp ´ a ınh . a ¯o a e a ınh ´ ¯o a .. .. ` ng, d .nh ngh˜ n`y khˆng phu thuˆc v`o hu.´.ng g´n cho c´c canh. ´ tuyˆn t´ e ınh. Ch´ y rˇ u´ a ¯i ıa a o oa o a a. . . Dinh l´ 2.1.3 Chu sˆ ν (G) cu a G = (V, E ) bˇ ng sˆ cu.c d ai c´c chu tr`nh d ˆc lˆp. -. ` ´ ´ ˙ ’ y o a o . ¯. a ı ¯o a.. Ch´.ng minh. Tiˆn h`nh nhu. trong Hˆ qua 2.1.2: d` u tiˆn ta lˆ y d` thi vˆ hu.´.ng khˆng ´ ´o ˙ ’ u ea e ¯ˆa e a ¯ˆ . o o o . .i tˆp c´c d ınh l` V. Sau d ´ ta xˆy du.ng d a d` thi G b` ng c´ch thˆm t`.ng canh c´ canh v´ a a ¯˙ ’ o. o. a ¯o a ¯ ¯ˆ . o ˇ a a e u . . - inh l´ 2.1.1, chu sˆ s˜ tˇng mˆt d o.n vi nˆu canh thˆm v`o lˆp ra c´c chu ´ea ´. mˆt v`o. Theo D. oa y o o¯ .e e aa a . . . tr` m´.i, chu sˆ khˆng thay d o’i trong tru.`.ng ho.p ngu.o.c lai. ˙ ´ ınh o oo ¯ˆ o . .. Gia su., tru.´.c khi thˆm canh ek ta d a c´ mˆt co. so. gˆm c´c chu tr` d ˆc lˆp: ˙` ˙˙ ’’ ’o o e ¯˜ o o a ınh ¯o a . . .. µ1 , µ2 , µ3 , . . . ; v` sau khi thˆm canh ek xuˆ t hiˆn thˆm c´c chu tr` so. cˆ p m´.i γ1 , γ2 , . . . , ´e ´ a e a e a ınh a o . . n`o d o. Hiˆ’n nhiˆn γ1 khˆng thˆ’ biˆ’u diˆn tuyˆn t´ qua hˆ c´c chu tr` µj (v` c´c vector ˙ ˙˙ ˜ ´ a ¯´ e e o ee e e ınh ea ınh ıa . http://www.ebook.edu.vn 50
tu.o.ng u.ng c´c chu tr` µj c´ th`nh phˆn th´. k bˇ ng khˆng, trong khi vector tu.o.ng u.ng ` ` ´ a ınh oa a u a o ´ . k kh´c khˆng). Mˇt kh´c c´c vector γ , γ , . . . c´ thˆ’ biˆ’u ˙˙ ` chu tr` γ1 c´ th`nh phˆn th´ ınh oa a u a o a aa oee . 23 diˆn tuyˆn t´ qua γ1 , µ1 , µ2 , µ3 , . . . . T´m lai mˆ i khi chu sˆ tˇng mˆt d o.n vi th` sˆ cu.c ˜ ˜ ´ ´ ´ e e ınh o o oa o¯ . ıo . . . ´n t´ c˜ng tˇng lˆn mˆt d o.n vi. Dinh l´ d u.o.c ch´.ng minh. -. d ai c´c chu tr` d ˆc lˆp tuyˆ ınh u ¯. a ınh ¯o a e a e o¯ y¯ . u .. . . Tu. kˆt qua n`y, dˆ d`ng suy ra: ˜a ´ ˙a ’ `e e Hˆ qua 2.1.4 (a) Da d` thi vˆ hu.´.ng G khˆng c´ chu tr`nh nˆu v` chı’ nˆu ν (G) = 0. - ¯ˆ . o o ´ ´ ˙ ’ e a ˙e e o o o ı . (b) Da d` thi vˆ hu.´.ng G c´ d ung mˆt chu tr`nh nˆu v` chı’ nˆu ν (G) = 1. - ¯ˆ . o o ´ ´ e a ˙e o o ¯´ o ı . Dinh l´ 2.1.5 Trong d` thi c´ hu.´.ng liˆn thˆng manh, chu sˆ bˇ ng sˆ cu.c d ai c´c mach -. ´` ´ y ¯ˆ . o o o e o oa o . ¯. a . . ´ d ˆc lˆp tuyˆn t´nh. ¯o a eı .. Ch´.ng minh. Thˆt vˆy, x´t d` thi vˆ hu.´.ng lˆp bo.i c´c cung kh´c nhau cua G (mˆi cung ˜ ˙a ’ ˙ ’ u aa e ¯ˆ . o o o a a o .. . .o.ng u.ng mˆt cˇp canh) v` mˆt chu tr` so. cˆ p µ; ta phˆn hoach tˆp c´c d ınh trˆn chu ´ a a ¯˙ ’ tu ´ oa. ao ınh a a e .. . . . tr` n`y th`nh: tˆp S c´c d ınh c´ mˆt cung t´.i n´ v` mˆt cung ra khoi n´, tˆp S c´c d ınh a ¯˙ ’ ˙oa ’ a ¯˙ ’ ınh a a a oo o oa o . . . . .i n´. V` sˆ c´c cung ´ ˙ ’ ˙ oaa ’ a ¯˙’ ˙ ’ c´ hai cung cua µ ra khoi n´ v` tˆp S c´c d ınh c´ hai cung cua µ d i t´ o ı o a o o ¯o . ` ng sˆ c´c cung d i t´.i nˆn #S = #S ; gia su. v1 , v2 , . . . , vk l` c´c phˆn tu. cua S v` ´a ` ˙˙ ’’ ˙˙ ’’ d i ra bˇ ¯ a o ¯oe aa a a v1 , v2 , . . . , vk l` c´c phˆn tu. cua S . ` a˙˙ ’’ aa Trˆn chu tr` µ, c´c phˆn tu. cua S v` cua S xen k˜ nhau v` ta gia su. rˇ ng sau d ınh ˙˙` ` ˙˙ a ’’ a˙ ’ ’’a ¯˙’ e ınh a e a vi th` d ınh d` u tiˆn bˇt gˇp (khˆng thuˆc S ) l` vi ; cuˆi c`ng, nˆu µ0 l` mˆt d u.`.ng d i gˇp ´. ´ ´ ı ¯˙ ¯a ’ ˆ eaa o o a ou e a o ¯o ¯a . . . d ınh x tru.´.c d ınh y th` ta k´ hiˆu µ0 [x, y ] l` d u.`.ng d i bˆ phˆn cua µ0 t`. x dˆn y. V` d` ´ ¯˙’ o ¯˙’ ˙’ ı ye a¯ o ¯oa u ¯e ı ¯o ˆ . . . ` n tai mach µ1 d i qua vi+1 v` vi v` d`ng c´c cung cua µ dˆ’ d i t`. ˙¯ u ˙’ thi liˆn thˆng manh nˆn tˆ . .e o eo ¯ a au a ¯e . . vi+1 dˆn vi . Chu tr` µ l` mˆt tˆ’ ho.p tuyˆn t´ cua c´c mach v` ta c´ thˆ’ viˆt ˙ ˙´ ´ ´ e ınh ˙ a ’ ¯e ınh aoo. ı oee . . µ = µ[v1 , v1 ] − µ1 [v2 , v1 ] + µ[v2 , v2 ] + · · · = µ[v1 , v1 ] + µ1 [v1 , v2 ] + µ[v2 , v2 ] + µ2 [v2 , v3 ] + · · · − (µ1 + µ2 + · · ·). Vˆy moi chu tr` so. cˆ p d` u l` tˆ’ ho.p tuyˆn t´ cua c´c mach, d oi v´.i c´c chu tr` ˙ ´e ´ ´ e ınh ˙ a ’ a ınh a ¯ˆ a o . ¯ˆ o a ınh . . . .p tuyˆn t´ cua c´c chu tr` so. cˆ p). bˆ t k` d iˆu d ´ c˜ng d ung (v` n´ l` tˆ’ ho ˙ a y ¯ ` ¯o u ¯ ´ ´ ´ ´ e ınh ˙ a ’ e ı oao . ınh a Trong Rm , c´c mach lˆp th`nh mˆt co. so. cua khˆng gian vector con sinh bo.i c´c chu ˙˙ ’’ ˙a ’ a a a o o . . . ınh, v` theo Dinh l´ 2.1.3 th` co. so. n`y c´ sˆ chiˆu l` ν (G). Vˆy sˆ cu.c d ai c´c mach d ˆc -. ˙ a oo ` a ´e ´ ’ tr` a y ı a o . ¯. a . ¯o . . ` ´ lˆp tuyˆn t´ bˇ ng ν (G). a e ınh a . http://www.ebook.edu.vn 51
´´ 2.2 Sˇc sˆ ao Gia su. rˇ ng ch´ng ta c´ mˆt d` thi vˆ hu.´.ng G v´.i n d ınh, v` cˆn tˆ m`u c´c d ınh sao ˙˙` a ` o a a ¯˙ ’’a ¯˙ ’ ’ u o o ¯ˆ . o o .o o a cho hai d ınh kˆ nhau c´ m`u kh´c nhau. Hiˆ’n nhiˆn l` c´ thˆ’ d`ng n m`u dˆ’ tˆ c´c d ınh ˙ ˙ ˙ ` ¯˙’ a ¯e o a ¯˙ ’ e oa a e e ao eu .ng nhu. thˆ vˆ n d` d at ra lai khˆng mang t´ thu.c tiˆn. Thˆ th` sˆ m`u tˆi thiˆ’u ˙ ˜ ´´ e. ´ ´ ´ d o, nhu ¯´ e a ¯ˆ ¯ˇ o ınh . e e ıo a o e . ˙ i l` bao nhiˆu? Dˆy ch´ l` b`i to´n tˆ m`u. Khi c´c d ınh d u.o.c tˆ, ch´ng ta c´ thˆ’ -a ˙ ’a ˙ ¯. o ’ d oi ho ¯` e ınh a a a o a a¯ u oe .o.c tˆ m`u d o, mˆt tˆp c´c oa` nh´m ch´ng v`o c´c tˆp kh´c nhau-mˆt tˆp gˆm c´c d ınh d u . o a ¯ ˙ a ¯˙ ’ ’ o u aaa a o ¯ oaa . .. .. .o.c tˆ m`u xanh, vˆn vˆn. Dˆy ch´ l` b`i to´n phˆn hoach. B`i to´n tˆ m`u v` -a ¯˙’¯ d ınh d u . o a aa ınh a a a a aaoaa . phˆn hoach d˜ nhiˆn c´ thˆ’ x´t trˆn c´c canh cua d` thi. Trong tru.`.ng ho.p d` thi phˇng ˙ ˙ ’ ˙ ¯ˆ . ’o a ı e o ee ea. o . ¯o . a ˆ . thˆm ch´ c´ thˆ’ quan tˆm dˆn viˆc tˆ m`u c´c diˆn. ˙ ´ a ıo e a ¯e eoaa e . . . Trong phˆn n`y ta chı x´t c´c d` thi vˆ hu.´.ng liˆn thˆng. ` ˙ e a ¯o . o o ’ aa ˆ e o Dinh ngh˜ 2.2.1 Cho tru.´.c mˆt sˆ nguyˆn p, ta n´i rˇ ng d` thi G l` p−sˇc nˆu bˇ ng p -. o` ae` ´´a .´ ıa o oo e a ¯o . ˆ a m`u kh´c nhau ta c´ thˆ’ tˆ m`u c´c d ınh, sao cho hai d ınh kˆ nhau khˆng c`ng mˆt m`u. ˙ ` o e o a a ¯˙ ’ ¯˙’ a a e o u o a . .i sˆ d o G l` p−sˇc goi l` sˇc sˆ cua d` thi G v` k´ hiˆu l` γ (G). ´ ´ ´’ o ´ ´ a ¯ˆ o ´ ´ ˙ ’a a . a a o ˙ ¯ˆ . Sˆ p nho nhˆ t, m` d oi v´ o ¯´ o a ay e a . V´ du 2.2.2 H` 2.1 minh hoa ba c´ch tˆ m`u kh´c nhau cua d` thi. Dˆ d`ng kiˆ’m tra ˙ ˙ ¯o . ˜ a ’ˆ ı. ınh a oa a e e . ` ´ rˇ ng d` thi n`y l` 2−sˇc. a ¯o . a a ˆ a •r •r •r . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •b •b •b . . . . . . . . .. .. .. . .. . .. . ... ... . .. .. . .. . ... .. ..... ... .. ...... ...... .. . ... . . .. .. . . .. . . . .. . ... .. . ... .. . .. .. . ... .. . ... .. . ... .. . .. . . .. . .. .. . .. .. . .. .. . ... .. . ... .. . ... .. . .. .. .. .. . . . . .. .. .. .. .. .. .. . .. .. . . . .. .. .. .. . . . .. .. .. .. .. .. . . . .. .. . .. .. .. .. . .. . . . .. .. .. .. . . . .. .. .. . . . .. .. .. .. .. .. .. .. . . . .. .. .. .. .. .. .. .. .. .. . . . .. .. .. .. . . . .. .. .. .. .. .. .. . . . .. .. .. .. . . . .. .. .. g• •y g• •y .. .. .. . .. . . . .. .. .. .. r• •r .. .. . .. .. .. .. . . . .. .. .. .. . . . .. .. . .. . . . . . .. . . . . . . . . . . .. .. .. .. . .. . . . .. .. .. .. .. .. .. .. .. . .. . . . . .. . . . .. .. .. .. .. .. .. .. .. .. . . . .. .. .. .. . . . .. .. .. .. .. .. . . . .. .. .. .. .. .. . . . .. .. . .. .. . . . . .. .. . . .. .. .. . . . .. .. .. .. .. .. . . . .. .. .. .. .. .. .. . . . . .. . . . . . . . . .. .. .. .. .. .. .. .. .. .. .. .. .. . . . .. .. .. . . . .. .. .. .. . . . .. .. .. .. .. . ... .. .. .. .. .. . ... .. . ... .. .. . . . . .. . . . .. . ... .. . ... .. . ... . .. . ... . .. . .. .. . . .. . .. .. . .. .. . .. .. . . . .. .. . .. .. . .. .. . .. .. . . ... . ... . • • • .. ... .. ... .. ... .... . ... . . ... ... ... .. . . . . p r b (a) (b) (c) H` 2.1: ınh V´ du 2.2.3 Ban d` d. a l´. Ta v˜ trˆn mˇt phˇng mˆt ban d` . Goi V l` tˆp ho.p c´c ˙’ ˙ ¯o ¯i y ’ o ˙ ¯ˆ ’ ı. ˆ ee a a o aa a . . . . . .´.c, d ˇt (i, j ) ∈ E nˆu c´c nu.´.c i v` j c´ biˆn gi´.i chung. D` thi G = (V, E ) d ˆi x´.ng -ˆ . ´a ´u nu o ¯a e o a oe o o ¯o . v` c´ t´ chˆ t rˆ t d ac biˆt l`: c´ thˆ’ v˜ n´ lˆn mˇt phˇng m` khˆng c´ hai canh n`o cˇt ˙ ˙ ’ ´ ´´. a o ınh a a ¯ˇ e a o e e oe a a ao o aa . . . . tai c´c d ınh chung); n´i c´ch kh´c, G l` d` thi phˇng. Ngu.`.i ta d a biˆt rˇ ng sˇc ˙ ’ ´` ´ nhau (tr` . a ¯˙ ’ u oa a a ¯ˆ . a o o ¯˜ e a a sˆ cua moi d` thi phˇng d` u nho ho.n hoˇc bˇ ng bˆn (Dinh l´ 6.4.7). Nhu. vˆy bˇ ng bˆn o -. ˙ ’ a` a` ´’ ´ ´ o˙ ˙ ’ ¯o . a ˆ ¯ˆe a y a o . . . ˙ tˆ m`u ban d` phˇng sao cho hai nu.´.c kˆ nhau khˆng c`ng mˆt m`u. ’o a ˆ˙ ’ o` a u ¯ ˙ ¯e ’ ˙ ¯o a ’ m`u c˜ng d u dˆ e o u o a . http://www.ebook.edu.vn 52
T`. d .nh ngh˜ dˆ d`ng suy ra ıa ˜ a u ¯i e ´ 1. Mˆt d` thi chı c´ c´c d ınh cˆ lˆp l` 1−sˇc. o ¯ˆ . ˙ o a ¯˙ ’ ’ .o oa a a . ´´ ´` 2. Mˆt d` thi c´ mˆt hoˇc hai canh (khˆng phai l` mˆt khuyˆn) c´ sˇc sˆ ´ nhˆ t bˇ ng ˙ao ’ o ¯o . o o .ˆ a o e o a o ıt a a . . . . hai. - ˆ . ¯a ¯ ˙ ¯˙ ´ 3. D` thi d` y d u n d ınh Kn l` n−sˇc. ’ ’ o ˆ a a 4. D` thi l` mˆt chu tr` d o.n gian v´.i n d ınh, n > 3, l` 2−sˇc nˆu n chˇn v` 3−sˇc ˜ -ˆ . a o ´´ ´ ˙ ’o ¯˙’ o ınh ¯ a ae aa a . ´ ˙ ’ nˆu n le. e 5. Hiˆ’n nhiˆn, moi d` thi 2−sˇc l` hai phˆn do ch´ng ta c´ thˆ’ phˆn hoach tˆp c´c d ınh ˙ ˙ ´ ` a a ¯˙ ’ e e . ¯o . ˆ aa a u oea . . .o.c tˆ trˆn c´c d ınh. Tu.o.ng tu., d` thi hai phˆn l` `a V th`nh hai tˆp con theo m`u d u . o e a ¯˙ ’ a a a¯ . ¯ˆ . o a . 2−sˇc, v´.i mˆt tru.`.ng ho.p ngoai lˆ tˆm thu.`.ng: d` thi c´ ´ nhˆ t hai d ınh cˆ lˆp v` ´ e` ´ ¯˙ ’ a oo o a o ¯o . o ıt a ˆ oa a . . .. . khˆng c´ canh l` hai phˆn nhu.ng l` 1−sˇc. ´ ` o o. a a a a Dinh ngh˜ 2.2.4 Ta goi sˇc l´.p cua d` thi G l` sˆ nguyˆn q c´ c´c t´ chˆ t sau: -. ´ ´ ´ ˙ ¯ˆ . ’o ıa .ao ao e o a ınh a 1. C´ thˆ’ d`ng q m`u kh´c nhau dˆ’ tˆ m`u c´c canh cua G sao cho hai canh kˆ nhau ˙ ˙ ` ˙ ’ o eu a a ¯e o a a . e . khˆng c`ng mˆt m`u; o u o a . 2. Diˆu n`y khˆng thˆ’ l`m d u.o.c v´.i (q − 1) m`u. -` ˙ ea o ea ¯. o a Nhˆn x´t rˇ ng sˇc l´.p cua d` thi G = (V, E ) ch´ l` sˇc sˆ cua d` thi G = (V , E ) ` ´ ´ ´’ ˆ ˙ ¯ˆ . ’o ınh a a o ˙ ¯o . aea ao . .o.c x´c d inh nhu. sau: mˆ i d ınh cua G tu.o.ng u.ng mˆt canh cua G; canh e = (v , v ) ∈ E ˜ ¯˙ o’ ˙ ’ ˙ ’ d u . a ¯. ¯ ´ o. . . 12 nˆu c´c canh e1 v` e2 (tu.o.ng u.ng v´.i hai d ınh v1 , v2 ) kˆ nhau. ´ ` ¯˙’ ea. a ´ o e Nhu. vˆy b`i to´n sˇc l´.p d u.a vˆ b`i to´n sˇc sˆ. Du.´.i d ay l` mˆt v`i kˆt qua co. ban ´ ´´ `a aao ´ ˙ ’ ˙ ’ a a aao¯ e o ¯ˆ a o a e . . ´o ` sˇc sˆ. ´ vˆ a e Dinh l´ 2.2.5 [K¨nig] D` thi vˆ hu.´.ng G l` 2−sˇc nˆu v` chı’ nˆu n´ khˆng c´ chu tr`nh -. -ˆ . o o ´´ ´ a e a ˙e o o y o o a o ı o ¯o a ˙ ’ c´ d ˆ d`i le . . Ch´.ng minh Diˆu kiˆn cˆn. Nˆu d` thi G l` 2−sˇc, th` tˆ t nhiˆn G khˆng ch´.a chu -` ´ e` ´o ´ u e a e ¯ˆ . a a ıa e o u . ˙ , v` c´c d ınh cua mˆt chu tr` loai nhu. vˆy khˆng thˆ’ tˆ bˇ ng hai m`u ˙o` ’ ı a ¯˙ ’ ˙ ’ tr` c´ d o d`i le ınh o ¯ˆ a o ınh . a o e a a . . . theo nhu. quy tˇc d a chı ra o. trˆn. ´ a ¯˜ ˙ ’ ˙e ’ Diˆu kiˆn d u. Gia su. d` thi G khˆng c´ chu tr` c´ d ˆ d`i le, ta ch´.ng minh n´ l` 2−sˇc. -` ´ e ¯˙ ’ ˙ ˙ ¯o . ’’ˆ ınh o ¯o a ˙ ’ e o o u oa a . . Khˆng giam tˆ’ng qu´t coi G l` liˆn thˆng. Ta s˜ tˆ m`u dˆn c´c d ınh cua G theo quy tˇc ˙ ´ e o a ` a ¯˙ ˙ ’ ’ ˙ ’ o o a ae o a a sau: http://www.ebook.edu.vn 53
o ¯˙ .’ • tˆ m`u xanh cho mˆt d ınh a n`o d o; oa a ¯´ • nˆu mˆt d ınh x n`o d ´ d a d u.o.c tˆ xanh, th` ta tˆ d o tˆ t ca c´c d ınh kˆ v´.i n´; nˆu ´ ’´ ’ `ooe ´ o ¯˙ .’ o ¯ ˙ a ˙ a ¯˙ ’ e a ¯o ¯˜ ¯ . o ı e .o.c tˆ d o, th` ta tˆ xanh tˆ t ca c´c d ınh kˆ v´.i y. ´’ `o d ınh y d ˜ d u . o ¯ ˙ ¯˙’ ’ a ˙ a ¯˙ ’ ¯a ¯ ı o e V` d` thi G liˆn thˆng, nˆn s´.m hay muˆn th` moi d ınh cua n´ d` u d u.o.c tˆ m`u hˆt, v` ´a ı . ¯˙ ’ ˙ o ¯ˆ ¯ . o a e ’ ı ¯o . ˆ e o eo o e . .o.c tˆ xanh v` tˆ d o, v` nhu. vˆy th` x v` a s˜ c`ng mˆt d ınh x khˆng thˆ’ c`ng mˆt l´c d u . o ˙ o ¯˙ .’ a o ¯˙ ı ’ o eu ou¯ a ı a eu . . ` ´ nˇ m trˆn mˆt chu tr` c´ d o d`i le. Vˆy d` thi G l` 2−sˇc. ınh o ¯ˆ a ˙ ’ a ¯ˆ . a e o o a a . . . Ch´ y rˇ ng t´ chˆ t d` thi G khˆng c´ chu tr` v´.i d o d`i le tu.o.ng d u.o.ng v´.i t´ ` ´o ınh o ¯ˆ a ˙ ’ u´ a ınh a ¯ˆ . o o ¯ o ınh . . cˆ p v´.i d o d`i le. Thˆt vˆy gia su. c´ mˆt chu tr` ´ ´ chˆ t G khˆng c´ chu tr` so a o ¯ˆ a ˙ ’ ˙˙oo ’’ a o o ınh aa ınh . .. . µ = { v0 , v 1 , . . . , v p = v0 } c´ d ˆ d`i p le. Mˆ i khi gˇp hai d ınh vj v` vk v´.i j < k < p v` vj = vk , ta phˆn chia µ th`nh ˜ ˙’ ¯˙ ’ o ¯o a o a a o a a a . . .n n˜.a mˆt trong hai chu tr` bˆ phˆn µ1 = {vj , . . . , vk } v` µ2 = {v0 , . . . , vj , vk , . . . , v0 }; ho ınh o a a u o . . . hai chu tr` c´ d o d`i le (v` nˆu khˆng nhu. thˆ th` µ s˜ c´ d ˆ d`i chˇn). Ta thˆ y rˇ ng nˆu ˜ a` ´ ´ ´a ´ ınh o ¯ˆ a ˙ ı e’ o eı e o ¯o a a e . . .o.c, th` mˆ i lˆn tiˆp tuc phˆn chia chu tr` µ theo c´ch d o cho dˆn khi c`n c´ thˆ’ l`m d u . ˙ ˜a ´ ´ ı o` e. a ınh a ¯´ ¯e o o ea ¯ ˜n c`n d u.o.c mˆt chu tr` c´ d o d`i le; v` cuˆi c`ng moi chu tr` d` u l` so. cˆ p, nˆn xay ´ ´ ˙ıou ’ e˙ ’ vˆ o ¯ . a o ınh o ¯ˆ a ınh ¯ˆ a e a . . . .ng minh. ˜ o ¯` ` ra mˆu thuˆn; v` ta c´ d iˆu cˆn ch´ a a a ea u -. ’´´ ´. e˙ao Dinh l´ sau d ay cho ta biˆt cˆn trˆn cua sˇc sˆ. y ¯ˆ ea Dinh l´ 2.2.6 K´ hiˆu dmax l` bˆc cu.c d ai cu a c´c d ı’nh trong G. Khi d ´ -. a a . ¯ . ˙ a ¯˙ ’ y ye ¯o . . γ (G) ≤ 1 + dmax . Ch´.ng minh. B`i tˆp. u aa . Brooks [9] d ˜ ch´.ng minh rˇ ng nˆu G l` d` thi khˆng d` y d u, c´ dmax d ınh th` ` ´ a ¯o . o ¯ˆ ¯ ˙ o ’ ¯˙’ ¯a u a e ˆ a ı γ (G) ≤ dmax . ´´ 2.2.1 C´ch t` sˇc sˆ a ım a o X´t d` thi G = (V, Γ) c´ n d ınh v` m canh; muˆn t` sˇc sˆ cua n´ ta c´ thˆ’ d`ng mˆt ˙ ´ ´’ o ´ o ¯˙ ’ o ım a o ˙ e ¯ˆ . o a o eu o . . .o.ng ph´p thu.c nghiˆm rˆ t d o.n gian, ´p dung tru.c tiˆp d u.o.c, nhu.ng khˆng phai l´c n`o ´¯ ´¯. ˙a ’ ˙u a ’ phu a ea e o . . . . c˜ng c´ hiˆu qua hoˇc c´ thˆ’ d`ng phu.o.ng ph´p giai t´ n´ cho ta mˆt l`.i giai hˆ thˆng, ˙ ’.´ ˙ a o eu ’ ˙ ıch, o ’ ˙eo u oe a oo . . . .ng n´i chung cˆn m´y t´ d iˆn tu.. ` a ınh ¯ e ˙ ’ nhu o a . http://www.ebook.edu.vn 54
Phu.o.ng ph´p thu.c nghiˆm a e . . ` .` Bˇ ng c´ch tˆ m`u t`y y d`ng c´c m`u 1, 2, . . . , p v` t` c´ch loai dˆn mˆt m`u n`o d o (goi a a o a u´u a a a ım a a o a a ¯´ . . .i han”) trong c´c m`u ˆ y. Muˆn vˆy, ta x´t d ınh v c´ m`u t´.i han d o v` c´c ´ ´. e ¯˙’ l` “m`u t´ . a ao a aa oa o a o . ¯´ a a th`nh phˆn liˆn thˆng C1 , C2 , . . . cua d` thi con sinh ra bo.i hai m`u khˆng t´.i han j v` jk jk ` ˙ ¯o . ’ˆ ˙ ’ a ae o a o o. a .c thay m`u cua d ınh v nˆu c´c tˆp ho.p C jk ∩ Γ(v ), C jk ∩ Γ(v ), . . . khˆng k. Ta c´ thˆ’ lˆp t´ ˙. ´ a ˙ ¯˙ ’’ o ea u eaa o . . 1 2 ´y riˆng r˜ mˆ i th`nh phˆn C jk m` v´.i th`nh phˆn d o th` c´c d ınh cua ˜ ` ` ¯´ ı a ¯˙ ˙a ’ ’ ˙ ’ phai l` hai m`u: lˆ a a e eo a a ao a a C jk ∩ Γ(v ) c´ m`u j, ho´n vi trong c´c th`nh phˆn d ´ c´c m`u j v` k (khˆng thay d o’i m`u ˙ ` ¯o a oa a. a a a a a o ¯ˆ a cua c´c d ınh kh´c), cuˆi c`ng tˆ d ınh v m`u j (l´c n`y d ınh v khˆng kˆ v´.i d ınh n`o c´ ´ ` o ¯˙ ˙ a ¯˙ ’ ’ o ¯˙’ u a ¯˙ ’ ’ a ou a o e ao m`u j ). a Phu.o.ng ph´p gia i t´ ˙ ıch ’ a Kiˆ’m tra bˇ ng c´ch giai t´ xem d` thi G c´ thˆ’ d u.o.c tˆ bˇ ng p m`u d u.o.c khˆng. Phu.o.ng ˙ ˙ ` o e¯ . o ` ˙ ıch ’ e a a ¯o . ˆ a a¯. o . sau: V´.i mˆi c´ch tˆ bˇ ng p m`u, ta cho tu.o.ng u.ng v´.i mˆt hˆ thˆng c´c sˆ ˜ ` ..´ ´ ph´p d o nhu a ¯´ o oa oa a ´ ooeo ao .o.c x´c d inh nhu. sau: xij , i = 1, 2, . . . , n; j = 1, 2, . . . , p, d u . a ¯. ¯ ´’ e ¯˙ 1 nˆu d ınh i c´ m`u j, oa xij = .`.ng ho.p ngu.o.c lai. 0 trong tru o . .. -a Dˇt . ´ o ¯˙ ’ 1 nˆu canh ej liˆn thuˆc d ınh vi , e. e . rij = trong tru.`.ng ho.p ngu.o.c lai. 0 o . .. L´c d ´ b`i to´n tro. th`nh t` c´c sˆ nguyˆn xij sao cho: ´ ˙a ’ u ¯o a a ım a o e   xij ≥ 0,  p q =1 xiq ≤ 1, i = 1, 2, . . . , n,   n k=1 rjk xkq ≤ 1, j = 1, 2, . . . , m; q = 1, 2, . . . , p. Ta c´ hˆ bˆ t d ˇng th´.c tuyˆn t´ e ınh. Dˆ r`ng thˆ y rˇ ng hˆ d ´ th´ ho.p v´.i c´c phu.o.ng .´˙ ’ ˜a a` ´ ´a o e a ¯a u e e ¯o ıch . o a . .`.ng cua quy hoach nguyˆn v` do d o c´ thˆ’ d`ng phu.o.ng ph´p cua Gomory ˙ ˙ ’ a˙ ’ ph´p thˆng thu o a o ea ¯´ o e u . .a trˆn phu.o.ng ph´p d o.n h` cua Dantzig) dˆ’ giai. ˙˙ ınh ˙ ’ ¯e ’ (du e a¯ . Sˆ ˆ’n d .nh trong ´˙ 2.3 o o ¯i V´.i d` thi G = (V, Γ) cho tru.´.c ta thu.`.ng quan tˆm dˆn tˆp con cua V c´ nh˜.ng t´ chˆ t ´. ´ ˙ ’ o ¯ˆ . o o o a ¯e a ou ınh a . l´.n nhˆ t sao cho d` thi con sinh ˙ ’ oo ` ´a˙ ´ ’ n`o d o. Chˇng han, t` mˆt tˆp con S ⊂ V c´ sˆ phˆn tu o a ¯´ a ım o a a ¯ˆ . o . .. http://www.ebook.edu.vn 55
bo.i S l` d` y d u? Hoˇc t` tˆp con c´c d ınh cua d` thi G c´ sˆ phˆn tu. nhiˆu nhˆ t sao cho oo ` ´a˙ ` ´ ˙ ’ a ¯ˆ ¯ ˙ ’ a ¯˙ ’ ˙ ¯ˆ . ’o ’ a a ım a e a . . hai d ınh trong d ´ khˆng kˆ nhau. Mˆt b`i to´n kh´c l` t` tˆp con S cua V c´ sˆ phˆn tu. ` oo ` ´a˙ ¯˙ ’ ˙ ’ ’ ¯o o e oaa a a ım a . . .i mˆt d ınh trong S. ´ `o ´ nhˆ t sao cho moi d ınh thuˆc V \ S kˆ v´ o ¯˙ . ¯˙’ .’ ıt a o e . C´c sˆ v` c´c tˆp con tu.o.ng u.ng l`.i giai c´c b`i to´n trˆn cho nh˜.ng t´ chˆ t quan ´ ´ ˙aa a ’ a oaa a ´ o e u ınh a . .ng dung tru.c tiˆp trong b`i to´n lˆp lich, phˆn t´ cluster, trong cua d` thi v` c´ nhiˆu u `´ ´ ˙ ¯ˆ . a o ’o e e aaa. a ıch . . . . l´ song song trˆn m´y t´ .i v` thay thˆ c´c th`nh phˆn ´’ ´ ` .o˙ phˆn loai sˆ, xu y a e a ınh, vi tr´ thuˆn lo a .ı a. ea a a . d iˆn tu., v.v. ¯e ˙ ’ . Dinh ngh˜ 2.3.1 X´t d` thi vˆ hu.´.ng G := (V, Γ); tˆp ho.p S ⊂ V d u.o.c goi l` tˆp ho.p -. ıa e ¯o . o o ˆ a ¯. . aa . . . . ˙n d. nh trong nˆu hai d ınh bˆ t k` cua S d` u khˆng kˆ nhau; n´i c´ch kh´c, v´.i moi cˇp ’ ¯i ´ ´y˙ ` ˙ ’ ’ ˆ o e ¯ a ¯ˆ e o e oa a o .a. ¯˙’ d ınh a, b ∈ S th` b ∈ Γ(a). ı/ K´ hiˆu S l` ho c´c tˆp ˆ’n d .nh trong cua d` thi G. Khi d ´ .˙ ˙ ¯o . ’ˆ ye a . a a o ¯i ¯o . ´ 1. Tˆp trˆng ∅ thuˆc S . a o o . . 2. Nˆu S ∈ S v` A ⊂ S th` A ∈ S . N´i c´ch kh´c, tˆp con cua mˆt tˆp ˆ’n d .nh trong ..˙ ´ ˙ ’ e a ı oa aa o a o ¯i . ˙n d .nh trong. ’ ¯i c˜ng l` mˆt tˆp ˆ u a oao .. Tˆp ˆ’n d .nh trong l` cu.c d ai nˆu thˆm mˆt d ınh bˆ t k` v`o n´ th` s˜ khˆng c`n ˆ’n d .nh .˙ ˙ ´ ´ o ¯˙ .’ a o ¯i a . ¯. e e a ya o ıe o o o ¯i .a. Dai lu.o.ng trong n˜ - . u . α(G) := max{#S | S ∈ S} d u.o.c goi l` sˆ ˆ’n d. nh trong cua G. ´˙ ˙ ’ ¯. . a o o ¯i V´ du 2.3.2 X´t d` thi trong H` 2.2. Tˆp c´c d ınh {v7 , v8 , v2 } l` ˆ’n d .nh trong nhu.ng ˙ a a ¯˙ ’ ı. e ¯o . ˆ ınh a o ¯i . .c d ai; tˆp {v , v , v , v } l` ˆ’n d inh trong cu.c d ai. C´c tˆp {v , v , v } v` {v , v } ˙ ¯. khˆng cu ¯ . a o ao . ¯. aa a 46 . . . 7825 137 c˜ng l` tˆp ˆ’n d .nh trong cu.c d ai v` do d ´, n´i chung c´ thˆ’ c´ nhiˆu tˆp ˆ’n d .nh trong ˙ ˙ e.˙ ` a o ¯i u a a o ¯i ¯. a ¯o o o eo . . cu.c d ai. Ho c´c tˆp ˆ’n d .nh trong cu.c d ai cua d` thi n`y l` .˙ . ¯ . ˙ ¯o . a a ’ˆ . ¯. . a a o ¯i {v7 , v8 , v2 , v5 }, {v1 , v3 , v7 }, {v4 , v6 }, {v3 , v6 }, {v1 , v5 , v7 }, {v1 , v4 }, {v3 , v7 , v8 }. V´ du 2.3.3 [Gauss] B`i to´n t´m con hˆu. Trˆn b`n c`. c´ thˆ’ bˆ tr´ t´m con hˆu, sao ˙´ ı. a aa a e a oo eo ıa a . . .o.c con n`o khˆng? B`i to´n nˆ’i tiˆng n`y d u.a vˆ t` mˆt ˙´ ` ım o cho khˆng c´ con n`o ch´m d u . o o a e¯ a o aaoe a¯ e . tˆp ho.p ˆ’n d .nh trong cu.c d ai cua d` thi vˆ hu.´.ng c´ 64 d ınh (l` c´c ˆ trˆn b`n c`.), trong ˙ . ¯ . ˙ ¯o . o o ’ˆ ¯˙’ a . o ¯i o aao e a o . d o y ∈ Γ(x) nˆu c´c ˆ x v` y nˇ m trˆn c`ng mˆt h`ng, mˆt cˆt hay mˆt d u.`.ng ch´o. Thu.c ` ´ ¯´ e ao a a eu oa oo o¯o e . .. . . .n ho.n l` khi ngu.`.i ta m´.i thoat nh` l´c d` u Gauss tu.o.ng c´ 76 l`.i ´ ˙ ’ tˆ, kh´ khˇn lai l´ e o a.o a o o ın: u ¯a ˆ o o . http://www.ebook.edu.vn 56
v1 v2 v3 •.........................................................................................................................................•................................................................................................................•.......... .. . . ... ... . ... ... . . . . . . . ..... ... ... . ... ..... ... ... . ... . ..... ..... ... ... ... . ... ... ... . ..... ..... . ... ... ... . ... ... ... ..... . ..... . ... ... ... . ..... ... ... ... ..... . . ..... ... ... ..... ... . ... ... ... . . ..... ..... ... ... ... . ... ... ... . ..... ..... . . ... ... ... ... ... ... ..... . ..... . . ... ... ... ..... ... ... ... ..... . . ..... ..... . ... ..... ..... ... ... ... ... . . ..... . ... ... ... ..... ... ... . ..... .. . . ... ... • v6 • v4 ... ....... ... . • ...... . ........................................................ . ........................................................ .. ... ..... .. . . .. . ...... ...... . . ... .... . ... .... ..... .... ..... .... . v8 . . .. . . ... ..... ... ..... . ... ... .. . . . ..... . .. .... ... ... ... ... ... ... . .. .. .. .. ... ... . ... . ... ... ... ... ... ... ......... . ... . . ... ... ... ... ... . ..... ... . . ..... ... ... . ... ... ......... . ..... .... . ... ... . ... ... ..... ..... . . ... ... . . . . ..... ..... ... . ... ... . ... . ... ..... ..... ... . ... ... ... . .... ... . .... ..... ..... . ... . ..... ... . ... ... ....... . ... . .. ......... ....... ......... ....... . • • ..... . ..... .. .. . v7 v5 H` 2.2: ınh giai, c`n t`. b´o vˆ c`. o. Berlin“Schachzeitung” nˇm 1854 chı m´.i d u.a ra 40 l`.i giai thˆ c`. ˙ o o a ` o˙ ´ ’ ’ ˙ o¯ ’ ˙ ’ e a o eo . t` ra. Su. thˆt th` c´ 92 l`.i giai nhu. 12 so. d` du.´.i d ˆy: ˙ ’ do c´c nh` ham c` ım a a o .a ıo o ¯o o ¯a ˆ . (72631485) (61528374) (58417263) (35841726) (46152837) (57263148) (16837425) (57263184) (48157263) (51468273) (42751863) (35281746) Mˆi so. d` trˆn tu.o.ng u.ng v´.i mˆt ho´n vi, v` t`. mˆt so. d` ta suy ra t´m l`.i giai kh´c ˜ ˙ ’ o ¯o e ˆ ´ o o a . au o ¯ˆo ao a . . .i giai bˇ ng c´ch quay 900 , 1800 v` 2700 ; c´c l`.i giai kh´c suy ra bˇ ng c´ch d ˆi ˙` ` ´ ’a ˙’ nhau: ba l` o a a ao a a a ¯o .ng mˆi so. d` nhˆn d u.o.c qua d u.`.ng ch´o ch´ ˜ ´ ´ ˙oo ’ x´u o ¯o a ¯ . ˆ. ¯o e ınh; ho´n vi cuˆi c`ng (35281746) chı c´ bˆn a .ou .i giai v` so. d` tu.o.ng u.ng s˜ tr`ng v´.i ch´ n´ sau khi quay 1800 . ˙ı ’ l` o ¯o ˆ ´ eu o ınh o V´ du 2.3.4 B` cua mˆt d` thi G l` tˆp ho.p C ⊂ V sao cho e˙ ’ ı. o ¯ˆ . .o aa . . a ∈ C, b ∈ C suy ra b ∈ Γ(a). Nˆu V l` mˆt tˆp ho.p ngu.`.i, v` b ∈ Γ(a) chı su. d` ng t` gi˜.a a v` b, th` thu.`.ng yˆu cˆu ´ e` ˙ . ¯ˆ ’ e aoa oa o ınh u a ı o a .. . .c d ai, ngh˜ l` hˆi c´ sˆ ngu.`.i tham gia nhiˆu nhˆ t. X´t d` thi G := (V, Γ ) x´c ´ ` ´ t` b` cu ¯ . ım e . ıa a o o o o e a e ¯o . ˆ a . d .nh nhu. sau: ¯i ´ ’´ e a ˙e b ∈ Γ(a ) nˆu v` chı nˆu b ∈ Γ(a). / B`i to´n quy vˆ t` mˆt tˆp ho.p ˆ’n d .nh trong cu.c d ai cua d` thi (V, Γ ). ˙ ` ım o a . ¯ . ˙ ¯ˆ . ’o aa e . o ¯i .. V´ du 2.3.5 B`i to´n vˆ c´c cˆ g´i l` d oi tu.o.ng cua nhiˆu cˆng tr` to´n hoc, c´ thˆ’ ph´t ˙ a a ` a o a a ¯ˆ ´ `o ˙ ’ ı. e e ınh a . oea . . sau: mˆt k´ t´c x´ nuˆi du.˜.ng 15 cˆ g´i, k´ hiˆu l` a, b, c, d, e, f, g, h, i, j, k, l, m, n, o; biˆ’u nhu ˙ e o yu a o o oa y e a . . .i th`nh t`.ng bˆ ba, c´ thˆ’ d u.a c´c cˆ d i cho.i trong bay ng`y ˙ ˙ ’ h`ng ng`y c´c cˆ d i dao cho a a a o¯ . a u o o e¯ a o¯ a . liˆn sao cho khˆng c´ hai cˆ n`o c`ng d i trong mˆt bˆ ba qu´ mˆt lˆn d u.o.c khˆng? ` a o` ¯. e o o oa u ¯ oo a o .. . V´.i nh˜.ng nhˆn x´t vˆ d ˆi x´.ng, Cayley d a t` ra l`.i giai nhu. sau: a e ` ¯o u e´ ˙ ’ o u ¯˜ ım o . http://www.ebook.edu.vn 57
Th´. Hai Th´. Ba Th´. Tu. Th´. Nˇm Th´. S´u Th´. Bay ˙ ’ u˙ ’ Chu Nhˆt a u u u ua ua . af k abe alm ado agn ahj aci bgl cno bcf bik bdj bmn bho chm df l deh cjl cek cdg dkm din ghk gio egm f mo f ei eln ejo ijm jkn f hn hil klo f gj B`i to´n vˆ c´c cˆ g´i c`ng loai v´.i mˆt b`i to´n th´. hai c˜ng nˆ’i tiˆng goi l` b`i ˙´ a `a oau a e .o oa a u u oe .aa . .: v´.i 15 cˆ g´i c´ thˆ’ lˆn lu.o.t lˆp 35 bˆ ba kh´c nhau sao cho khˆng c´ hai cˆ ˙ tro o ’. ˙` to´n bˆ ao oa o ea .a o a o o o . . n`o c`ng trong mˆt bˆ ba qu´ mˆt lˆn khˆng? Dˆ’ giai b`i to´n bˆ’ tro., chı cˆn lˆp d` thi -e ˙ a a o . ˙’ ˙ a o` ˙ ` a ¯o . ’a . au oo a o ˆ .. . G c´ c´c d ınh l` 455 bˆ ba c´ thˆ’ c´, hai bˆ ba d u.o.c xem l` kˆ nhau nˆu ch´ng c´ chung ˙ a` ´ o a ¯˙ ’ a o o eo o ¯. e e u o . . hai cˆ g´i: khi d o cˆn t` mˆt tˆp ho.p ˆ’n d .nh trong cu.c d ai. Ta c´ α(G) ≤ 35 v` mˆt cˆ ˙ ¯´ ` ım o a oa a o ¯i ¯. o ıoo .. . . . 1 ` ´ ´’ ˙o a ’ e a ˙o g´i chı c´ mˇt nhiˆu nhˆ t l` trong 7 bˆ ba kh´c nhau, nˆn tˆ t ca c´ 15 × 7 × 3 = 35 bˆ l` a e aa o a oa . . . ` u nhˆ t; v` vˆy moi tˆp ho.p ˆ’n d .nh trong c´ 35 bˆ ba d` u l` cu.c d ai. ˙ ¯i ´ ıa nhiˆ e a .a .o o o ¯ˆ a . ¯ . e . . . Dˆ’ x´t xem mˆt l`.i giai n`o d ´ cua b`i to´n bˆ’ tro. c´ cho l`.i giai cua b`i to´n vˆ c´c -e e ˙ ˙ ˙ ˙ a a `a ˙ a ¯o ˙ a a o . o ’ ’ ’’ oo o e . ˙ tro., hai ’. cˆ g´i khˆng, ta lˆp d` thi G c´ c´c d ınh l` 35 bˆ ba cho nghiˆm cua b`i to´n bˆ o a ¯˙ ’ ˙aao ’ oa o a ¯o . ˆ a o e . . . bˆ ba d u.o.c xem l` kˆ nhau nˆu c´ chung mˆt cˆ g´i; nˆu sˇc sˆ γ (G ) > 7 th` phai chon ´´´ a` ´ ˙ ’ o ¯. e eo o oa e a o ı . . . .p kh´c gˆm c´c bˆ ba cho nghiˆm cua b`i to´n bˆ’ tro.. Dˆ d`ng kiˆ’m tra rˇ ng tˆn ˙ ˙ ˜a ` a` ` ˙a ’ tˆp ho a o ao e ao. e e a o . . . . tai nh˜.ng l`.i giai cua b`i to´n bˆ’ tro. khˆng dˆn dˆn l`.i giai cua b`i to´n vˆ c´c cˆ g´i. ˙ ˜ ´ ˙ ˙ a a `a oa ˙˙aao. ’’ ’’ u o o a ¯e o e . Nhˆn x´t 2.3.6 (a) Sˇc sˆ γ (G) v` sˆ ˆ’n d inh trong α(G) liˆn hˆ v´.i nhau bˇ ng bˆ t d ˇng ´˙ ´´ ` ´˙ ’ a e ao a o o ¯. e eo a a ¯a . . .c th´ u γ (G) × α(G) ≥ n. Thˆt vˆy, c´ thˆ’ phˆn hoach V th`nh γ := γ (G) tˆp ho.p ˆ’n d .nh trong, lˆp bo.i c´c ˙ ˙ ˙a ’ aa oea a a . o ¯i a .. . . . .o.ng u.ng ch´.a n , n , . . . , n d ınh. Vˆy ta c´ ¯˙’ ¯˙ ’ d ınh c`ng m`u v` tu u aa ´ u 12 a o . γ n = n1 + n2 + · · · + nγ ≤ α(G) + α(G) + · · · + α(G) = γ (G).α(G). (b) Ta c´ thˆ’ hoi: phai chˇng mˆi liˆn hˆ gi˜.a hai kh´i niˆm l` chu.a chˇt ch˜. Phai chˇng ˙’ ´ oe˙ ˙ ’ ˙ ’ a oeeu aea a e a . . . .´.c hˆt d`ng m`u (1) dˆ’ tˆ tˆp ˆ’n d inh trong cu.c d ai S . c´ thˆ’ t` sˇc sˆ bˇ ng c´ch: tru o e u ˙ ˙ ˙ o e ım a o ` ´ ´a ´ a a ¯ e o a o ¯. ¯. 1 . . Rˆi d`ng m`u (2) dˆ’ tˆ tˆp ˆ’n d .nh trong cu.c d ai S2 cua d` thi con sinh ra bo.i c´c d ınh ˙ .˙ `u ˙ ¯o . ’ˆ ˙ a ¯˙ ’ ’ o a ¯e o a o ¯i . ¯. cua V \ S1 , sau d´ d`ng m`u (3) dˆ’ tˆ tˆp ho.p ˆ’n d .nh trong cu.c d ai cua d` thi con c`n lai, ˙ ˙ ˙’ ¯ . ˙ ¯ˆ . ’o ou a ¯e o a o ¯i o. . . . v.v. Thu.c ra khˆng phai nhu. vˆy. D` thi trˆn H` 2.3 (c´ sˇc sˆ bˇ ng 4) ch´.ng to d iˆu a -ˆ . e ´ ´` ˙ ¯` ˙ ’ ’e o o ınh oa oa u . . http://www.ebook.edu.vn 58
d o: c´c d ınh kˆ v´.i c´c d ınh a, b, c v` d lˆp th`nh tˆp ˆ’n d .nh trong cu.c d ai duy nhˆ t, nˆu .˙ ` o a ¯˙ ´e ´ ¯´ a ¯˙ ’ ’ e aa a a o ¯i . ¯. a . .ng r˜ ta tˆ ch´ng c`ng mˆt m`u th` ta phai d`ng ba m`u chı dˆ’ tˆ c´c d ınh a, b, c, d, nhu ’˙ ˙u ’ ˙ ¯e o a ¯ ˙ ’ ou u o a ı a o . .o.c. r`ng d iˆu d ´ khˆng thˆ’ l`m d u . ˙ a ¯ ` ¯o o e ea ¯ ... . .. ... . ... ... . ... ... . ... . .... .. . .. • ............... ............... ... ... ...... ....... .. .. ... . .... ... . .... ..... . ...... . ..... . ..... .. . . . b. . .. .. . ... . .. . .. . .. . . .. . .. .. . .. . .. . .. .. . .. . .. . .. . .. . . . .. .. .. . .. . . .. .. .. . .. . . .. .. .. . .. . . .. .. . .. . . . .. .. .. . .. . ... . ... ... . ... .. .. .. .. ... . ... ... . ... .. .. . .. ....... • . . ...... .. .. .. ............... .............. .. .. .... ..... .. .. .. .. . ... ..... . ........ ..... . ....... .. ... .. .. . . .. . ...... . .. .... .. .. ...... . .. ..... . .. .. .. . c ... .. .. ... ... ... .. .. . .. ... ... ... .. .. ... ... .. ... . .. .. ... .. .. ... ... ... .. . .. ... ... ... .. . ... . ... ... ... . ... . .. ..... ... ... ... ...... ... . .... ... ... .. . . .. ... . .. .. .... ... .. . . .. ..... .. . .. ..... . . ... ... . ....... ... . ....... .. . ...... . .. ...... .. . . .. ...... . ..... • • ....... .. . ...... ................................................................................................... .................................................................................................... ... .... ...... ...... .. ... ... .. . ... . ..... ... . ..... ... . ..... ... . ..... . . ... . ... . ... . ... . . . . . a d H` 2.3: ınh V´ du 2.3.7 [Shannon] B`i to´n vˆ dung lu.o.ng thˆng tin cua mˆt tˆp ho.p t´ hiˆu. X´t aa` ˙ ’ ı. e o oa . ın e e . .. . .`.ng ho.p rˆ t d o.n gian l` m´y ph´t c´ thˆ’ truyˆn d i nˇm t´ hiˆu: a, b, c, d, e; o. m´y thu, ˙ ´ `¯a ˙aa ’ ˙a ’ tru o . a¯ aoe e ın e. ˜i t´ hiˆu c´ thˆ’ cho hai c´ch hiˆ’u kh´c nhau: t´ hiˆu a c´ thˆ’ hiˆ’u l` p hay q, t´ hiˆu ˙ ˙ ˙ea˙ mˆ ın e o e o a e a ın e oe ın e . . . b c´ thˆ’ hiˆ’u l` q hay r, . . . (H` 2.4 (a)). ˙˙ oeea ınh Sˆ cu.c d ai c´c t´ hiˆu m` ta c´ thˆ’ su. dung l` bao nhiˆu dˆ’ cho o. m´y thu khˆng xay ˙’ ˙ ´ o e˙ . ˙a ’ ˙ ’ o . ¯ . a ın e a a e ¯e o . .a c´c t´ hiˆu d u.o.c su. dung. B`i to´n quy vˆ t` mˆt tˆp ˆ’n d inh trong ˙ ˜ ` ` ım o a o ¯. ra nhˆm lˆ n gi˜ a ın e ¯ . ˙ . ’ aa u a a e . .. cu.c d ai S cua d` thi G (H` 2.4(b)), trong d ´ hai d ınh l` kˆ nhau nˆu ch´ng biˆ’u thi hai ˙ a` ´ ˙ ¯ˆ . ’o ¯˙ ’ ¯. ınh ¯o e e u e . . .i nhau o. m´y thu, ta s˜ lˆ y S = {a, c}, v` r˜ r`ng α(G) = 2. Thay t´ hiˆu c´ thˆ’ lˆ n lˆn v´ ˙˜ . ´ ˙a ’ ın e o e a o o ea aoa . cho c´c t´ hiˆu mˆt ch˜. c´i, ta c´ thˆ’ d`ng c´c “t`.” gˆm hai ch˜. c´i v´.i d iˆu kiˆn l` c´c ˙ u` u a o ¯` a ın e o ua o eu a o e e aa . . . . n`y khˆng gˆy ra lˆm lˆ n o. m´y thu. V´.i c´c ch˜. c´i a v` c (c´c ch˜. c´i n`y khˆng ˜˙ a `a a’ t` a u o a oa ua a a ua a o thˆ’ lˆn lˆn nhau) ta lˆp m˜: aa, ac, ca, cc; nhu. vˆy ta d u.o.c [α(G)]2 = 4 t`.. Nhu.ng ta c`n ˙˜ . ea o a a a ¯. u o . . .n: aa, bc, ce, db, ed. (Dˆ d`ng kiˆ’m tra rˇ ng hai t`. bˆ t k` trong c´ thˆ’ lˆp m˜ phong ph´ ho ˙. ˙ ˜a ` ´ o ea a u e e a ua y . n`y khˆng thˆ’ lˆn lˆn v´.i nhau o. m´y thu). ˙a o o ˜. ˙a ’ c´c t` a au o e T` tˆ t ca c´c tˆp ˆ’n d .nh trong cu.c d . i .˙ ´’ ım a ˙ a a o ¯i . ¯a Phu.o.ng ph´p suy luˆn sau (khˆng hiˆu qua d ˆi v´.i c´c d` thi l´.n) t` tˆ t ca c´c tˆp ˆ’n .˙ ’´ ´’ ˙ ¯o o a ¯o . o ım a ˙ a a o a a o e ˆ . . .c d ai du.a trˆn d ai sˆ Boole. Ta xem mˆ i d ınh cua d` thi tu.o.ng u.ng v´.i mˆt ˜’ ´ o ¯˙ ˙ ¯o . ’ˆ d .nh trong cu ¯ . . ¯i e ¯. o ´ oo . . biˆn Boole. K´ hiˆu x + y, xy v` x l` c´c ph´p to´n tuyˆ’n, hˆi v` phu d .nh cua c´c biˆn ˙ ´ ´ ˙ ¯i ’ ˙a ’ e ye a aa e a e oa e . . Boole x, y. V´.i d` thi G cho tru.´.c, ta cˆn t` mˆt tˆp con cu.c d ai c´c d ınh khˆng kˆ nhau trong ` ım o a ` . ¯ . a ¯˙ ’ o ¯ˆ . o o a o e .. ˙u diˆn mˆ i canh (x, y ) bˇ ng mˆt t´ Boole xy v` sau d o lˆ y tˆ’ng cua tˆ t ca c´c t´ ’ ˙ ˜ ˜ ` ´ ’´’ ˙ a ˙ a ıch G. Biˆ e e o. a o ıch a ¯´ a o . http://www.ebook.edu.vn 59
a a •..................................................................................................................................................• p • .. .. . .... ... . . ... ...... . ... ..... .. . .... ... ... . .. .... ..... . ..... . ... ... ... .. ....... ... .... . ... . ... ... ......... .. ... . ... . ..... .. ... ... . . .. .... ..... ..... ..... .... ... ..... ... ... ... ... ... ... .. . .. .. . .. ....... ... ... ...... ... ... •q ... b• .. . ........................................................ ... ....................................................... ... .. ... . ... . ... . ... .. ... ..... ... ..... .. . ... ... .. ... ..... e .. ..... ... •b .. ... . ... ..... ... ..... ... ... ... ..... ..... . ... .. ... ... . ... .... ... • ... ...... ..... ... ... .. .......... . . ...... . . . . .. . .. ... .......... . ... .......... . . . . . . ... .. . . ..... ... ... . . ..... . . c• •r .. .. . ... ......................................................... ........................................................ . . . . ... . .. . .. . . . ..... . ..... . . . . . . . . . ..... ..... ..... ... . . ..... ... . . . . . . . ....... . ..... . ...... . . . . . .. .. . .. .. . .......... . . . .. . . ..... . . . .. ..... . . ..... .. . . . ..... ..... . .. . . .. . .... . .... . •s d• .. . ......................................................... .. ....................................................... .. . . . . .. ... . . . .. . . . . . ..... . . ....... . . . . ............ . . . ........ . . . . .. . . ..... . .. . . ....... . ... . . .. . .. . . ......... .. . ... . . . . ..... .. ..... . . .. . . ..... . ..... . . .. . . ..... .. ..... . . . . ... . ...................................................... e• •t • • . . ....................................................... ....................................................... ... .. . . .. . ..................................................... .. . .. . . c d H` 2.4: ınh n`y ta d u.o.c biˆ’u th´.c Boole ˙ a ¯. e u ϕ= xy. (x,y )∈E Kˆ tiˆp biˆ’u diˆn phu d .nh ϕ dang tˆ’ng cua c´c t´ Boole ˙ ˙ ˜ ´´ ˙ ¯i ’ ˙ a ıch ’ ee e e o . ϕ = f1 + f2 + · · · + fk . Mˆt tˆp c´c d ınh l` ˆ’n d .nh trong cu.c d ai nˆu v` chı nˆu ϕ = 0, ngh˜ l` ϕ = 1; hay tu.o.ng ˙ ´ ’´ o a a ¯˙ ’ . ¯. e a ˙ e a o ¯i ıa a .. .o.ng c´ ´ nhˆ t mˆt f = 1; t´.c l` nˆu mˆi d ınh xuˆ t hiˆn trong f (o. dang phu d inh) ˜’ ´ ´ ´ o ¯˙ i˙ ’. ˙ ¯. ’ du ¯ o ıt a oi uae a e . . .o.c loai ra khoi tˆp d ınh cua G. Do d ´ mˆ i f s˜ cho tu.o.ng u.ng mˆt tˆp ˆ’n d inh trong ˙ ¯. ˜ ie ˙ a ¯˙ ’. ’ ˙ ’ du . ¯ ¯o o ´ oao . .. cu.c d ai v` do d o phu.o.ng ph´p n`y cho ta tˆ t ca c´c tˆp ˆ’n d .nh trong cu.c d ai. Chˇng han ˙ ˙ ’ ´’ a ˙ a a o ¯i ¯. a ¯´ aa . ¯. a . . . x´t d` thi trong H` 2.5 ta c´ e ¯ˆ . o ınh o ϕ = ab + bc + bd + be + ce + de + ef + eg + f g. ϕ = (a + b )(b + c )(b + d )(b + e )(c + e )(d + e )(e + f )(e + g )(f + g ). R´t gon v` d u.a vˆ dang tˆ’ng cua c´c t´ ta d u.o.c ˙ `. ˙ a ıch ’ u . a¯ e o ¯. ϕ =bef +beg +acdef +acdeg +bcdf g. Bˆy gi`. nˆu loai bo khoi tˆp d ınh cua G c´c d ınh xuˆ t hiˆn trong bˆ t k` mˆt trong nˇm sˆ ´ ´e ´ ´ .˙ ’ ˙ a ¯˙ ’. ’ ˙’ a ¯˙ ’ a oe a ayo ao . . ˙ a tˆ’ng, ta s˜ thu d u.o.c mˆt tˆp ˆ’n d .nh trong cu.c d ai. C´c tˆp ˆ’n d .nh trong cu.c ˙ ˙ ¯i ˙ ¯i ’o hang cu e ¯. oao . ¯. a ao . .. . . d ai tu.o.ng u.ng l` ¯. ´ a {a, c, d, g }, {a, c, d, f }, {b, g }, {b, f }, v` {a, e}. a V` do d o sˆ ˆ’n d .nh trong cua d` thi n`y bˇ ng 4. ´˙ ˙ ¯ˆ . a ` ’o a ¯´ o o ¯i a http://www.ebook.edu.vn 60
c • . f .. .. .. .. .. .. ... .. ... .. • .. .. .. .. .. . .. ..... .... . .. .. . .. .... . .... . .. .. .. .... . .... .. . .. . .. . .. .... .. . .. . .... .. .... . .. . .. .. . . .. .... .. .... . .. . .. . .. .. . . .... .. .. ....... . .. . .. .. . a• . • ......................................... • . ..... . . ..................................... .................................. ... ..................................... . . .. . . ...... . . . .. .. ....... .. . .. .... . e . .. . .. b .. .... .... .. . . .... .. . .... .. .. . .. . .... .... . .. .. .. . .... .. .... . . .. .... . .. .... .. .. .... . .... . .. ..... .. .. ..... .. • . . .. .. .. . . .. .. .. .. .. g .. . .. .. . ... •... . d H` 2.5: ınh Sˆ ˆ’n d .nh ngo`i ´˙ 2.4 o o ¯i a Dinh ngh˜ 2.4.1 Cho d` thi G := (V, Γ). Tˆp ho.p con T c´c d ınh cua V l` tˆp ˆ’n d. nh -. .˙ a ¯˙ ’ ˙ ’ ıa ¯o . ˆ a a a o ¯i . . ´u moi d ınh khˆng thuˆc T kˆ v´.i ´ nhˆ t mˆt d ınh trong T ; t´.c l` T ∩ Γ(v ) = ∅ v´.i ` o ıt a ´ o ¯˙ ˙ ’ ’ ngo`i nˆ ae .¯ o o e ua o . . ¯˙’ moi d ınh v ∈ T. / . K´ hiˆu T l` ho c´c tˆp ho.p ˆ’n d .nh ngo`i cua d` thi G th` ˙ a ˙ ¯o . ’ˆ ye a.a a . o ¯i ı: . . 1. V ∈ T . 2. T ∈ T v` T ⊂ A th` A ∈ T . a ı Ta d .nh ngh˜ sˆ ˆ’n d. nh ngo`i cua d` thi G l` sˆ ´˙ ´ a ˙ ¯ˆ . ’o ¯i ıa o o ¯i ao β (G) := min{#T | T ∈ T }. Tˆp ˆ’n d. nh ngo`i cu.c tiˆ’u l` tˆp ˆ’n d .nh ngo`i sao cho bo d i mˆt d ınh th` khˆng c`n ˆ’n .˙ ˙ .˙ ˙ ˙ ¯ o ¯˙ ’ .’ a o ¯i a. e a a o ¯i a ıo oo .a. d .nh ngo`i n˜ ¯i au V´ du 2.4.2 X´t d` thi G trong H` 2.5. C´c tˆp {b, g } v` {a, b, c, d, f } l` ˆ’n d .nh ngo`i. ˙ ı. e ¯ˆ . o ınh aa a a o ¯i a . ˙n d .nh ngo`i cu.c tiˆ’u. Dˆ thˆ y β (G) = 2. ’ ¯i ˙ ˜a e´ C´c tˆp {b, e} v` {a, c, d, f } l` ˆ aa a ao a. e . V´ du 2.4.3 V´.i d` thi trong H` 2.6, tˆp ˆ’n d .nh ngo`i cu.c tiˆ’u ch´.a sˆ nho nhˆ t c´c .˙ ˙ ´˙ ´ ’aa ı. o ¯o . ˆ ınh a o ¯i a. e uo ` n tu. l` {v1 , v4 } v` do d ´ β (G) = 2. ˙a ’ phˆ a a ¯o B`i to´n ta x´t o. d ˆy l` xˆy du.ng mˆt tˆp ho.p ˆ’n d .nh ngo`i v´.i sˆ phˆn tu. ´ nhˆ t. ˙ aoo` ´ a ˙ ıt a ´ e ˙ ¯a a a ’ ’ aa oa . o ¯i . .. http://www.ebook.edu.vn 61
v1 • ....... . ... ... .. .... ....... ..... ....... ... . ... .. .. .. .. .. ... .. ... ... .. .... .. ..... .. .. .. .... . ... . ... . .. ..... ... ... ... ... .. ..... .. ..... . ..... .... .. ... ... . .. . . .. . .. . ... ... . ... .. ... .. .. ... . ... . .. ... ... .. ... .. ... .. . .. . ... ... .. ... ... .. . .. . ... . ... ... .. ... v6 • • v2 ... . ... ... ... ... .. . .. .. ... .. .. .. . . ..... .. .... .. .. .. .. ......... ... .. .. ......... ... .. .. .. .. .. .. .... . .... .. . .. .. .. . .. ... .. ..... ..... .. .. ... .. . .. .. .. .. ..... ..... .. .. .... .. .. ..... ..... .. . . . .. . ... . ..... ..... . . . . .... .... .. .. .. .. ..... ..... . .. ... .. ... ..... .. ... ......... .. ... . ........ .. .. .. .. ... .. .. .. ............. . ........... ... .. ... .. .. v5 • • v3 . .... .. . .. ... ..... .. .. . .. . .. . .. . .. .. ... ... ... .. .. .. .. ... .. ... .. .. . .. . ... .. ... .. .. . .. . ... .. ... .. .. .. .. . .. .... ... ... .. .. .. . .. .. ..... ... .. .. .. .... .. ... .. .. .. ..... .. ...... .. .. .. ....... .. ...... .. ..... .. ..... • .. .. v4 H` 2.6: ınh V´ du 2.4.4 B`i to´n vˆ nh˜.ng ngu.`.i d u.ng g´c. Trong mˆt trai giam o. th`nh phˆ N, a` ´ ˙ ’a ı. a eu o ¯´ a o o . . .ng ngu.`.i d u.ng g´c, chˇng han o. nh` giam v , ˜ ˙ ’ .˙ ’ mˆi nh` giam c´ mˆt tram g´c d ˆc lˆp, nhu o a oo a ¯o a o ¯´ a a a . . .. 1 ˙ nh` thˆ y nh˜.ng g` xay ra o. c´c nh` giam v2 , v6 , v8 , v9 , nh˜.ng nh` giam n`y ’ ın a ´ ˙ ’ ˙a ’ c˜ng c´ thˆ u oe u ı a u a a thˆng v´.i nh` giam v1 bo.i mˆt h`nh lang thˇng nhu. ta thˆ y trˆn H` 2.7. Hoi sˆ ngu.`.i ˙ ’ ´ ’´ ˙ ’ ˙o o o a oa a a e ınh o . .ng g´c cˆn thiˆt ´ nhˆ t l` bao nhiˆu dˆ’ quan s´t d u.o.c moi nh` giam? Ta phai t` sˆ ˙ ` ´ ıt a a ´ ´ ˙ ım o ’ du ¯´ aa e e ¯e a¯. a . .´.ng trong H` 2.7, d ˆi v´.i so. d` rˆ t d o.n gian n`y th` sˆ ˆ’n ˆ’n d .nh ngo`i cua d` thi vˆ hu o ˙ ´˙ ´ ˆ´ a ˙ ¯o . o ’ˆ ˙a ’ o ¯i ınh ¯o o ¯o a ¯ ı oo d .nh ngo`i l` 2. ¯i aa v.7 ... • ........ .. .. . .... ...... .. .. ..... ..... .. . ..... .... .. .. ..... .. ..... .. .. ..... ..... .. .. .. ... ...... .. .. ..... .. ..... .. .. ... ... .. ..... ..... .. .. ... ... .. .. ..... ..... .. . .. ... .. . .. ..... ..... v6 . .. ... .. ... .. ..... ..... .. .. ... ... .. ..... ..... • .. .. ..... .. .. . ..... .. .. .. .... ... .. .. . ... .... .. .. .... ..... .. .... .. .. .. .. . .. ..... ........ .... . ..... .. .... . . .. . .. .... ... .... ... . . .. .. . .... .... .. . ... .... .. ... .... . . . .. . . .... . . .... ... . . .. ... . .... . .... .. . . . . . .... .... ... . .. ... . . . .... .. .... . . . ... . .. ... .... . .... . . .. . . .... ... .... . ... . . . .... .. .... . . .. ... . . ... .... . .... . . . .. .... ... . . .... .. v4 ... . . . . .... .... . . .. ... ... . .. . .... .... . . . . ... .... .... .. ... . . • .. . . .... . .... . ... . ... . ... .. .. . .... ... .... . .. ... . ... . . ... ..... .. .... ..... ... . .... ... . . .. . ... . ....... .. .... . ... ....... .... . . . • • . .. ..... . .... .. .. . . . ... .. ... . .. ...... ..... .. . . . .. .. . .. . .. v5 v8 ... ... . .. . .. ......... . ..... .... . .. . . .. . .. ... . .. .. . .. . ..... .... ..... ..... . .. . . .. . ... .. ... . . .. .. . . ..... ..... . . . . .. . . . . . .......... .. . .. . . . ... . ........... . .. . ... . . . • . . . . . .. . . .. .. . . ... . .. ... .. . . . . . . . . . . . . .... v3 .. ... . ..... . ... . . .. . . . . . .. . . . . . .. .. ... ... ... . .. . . . .. . . . . .. . ... .. . ... . . .. .. . . . .. . . . .. . . . ... . . .. .. ... . . .. .. . .. .... • . . . .. ... ... . ... .. . . . . . . .. . ... ... . .. . v2 . . . . . . . ... .. . ... . .. . . . . . . ... .. . ... . . . . . .. . ... ... ..... . . . ... . ... .. . • • . ................................................................................ ... . .................................................................................. ... . v1 v9 H` 2.7: ınh V´ du 2.4.5 Vi tr´ cua c´c “tˆm” dˆ’ phu mˆt v`ng. C´ nhiˆu l˜ vu.c liˆn quan dˆn b`i ˙ ` ınh . e ´ .ı˙ a ’ ˙ou ’. ı. a ¯e o e ¯e a to´n n`y: aa 1. Vi tr´ cua c´c m´y ph´t T.V. hay radio truyˆn dˆn mˆt sˆ vi tr´ cho tru.´.c. ` ¯e´ .´ .ı˙ a ’ a a e oo.ı o http://www.ebook.edu.vn 62
2. Vi tr´ cua c´c tram g´c dˆ’ gi´m s´t mˆt v`ng. ˙ .ı˙ a ’ a ¯e a a ou . . 3. Tram l`m viˆc cua ngu.`.i b´n h`ng dˆ’ phuc vu mˆt v`ng. ˙ e˙ ’ a o a a ¯e .ou . . . . Gia su. rˇ ng mˆt v`ng-cho bo.i h` vuˆng l´.n trong H` 2.8-d u.o.c phˆn hoach th`nh 16 ˙˙` ’’a ˙ ınh o ’ ou o ınh ¯. a a . . v`ng nho ho.n. Gia su. mˆt tram g´c d u.o.c d at trong mˆt v`ng nho c´ thˆ’ gi´m s´t khˆng ˙ ˙ ’ ˙˙ o ’’ . ˙o e a ’ u a ¯ . ¯ˇ ou a o . . . .ng h` vuˆng c´ chung biˆn v´.i n´. Cˆu hoi d at ra l` ˙ ınh o ’ ˙ ¯ˇ ’. chı h` vuˆng n´ d at m` c`n nh˜ o ¯ˇ ao u ınh o o eoo a a . ´ tˆi thiˆ’u c´c tram g´c v` vi tr´ cua ch´ng sao cho c´ thˆ’ d iˆu khiˆ’n to`n bˆ v`ng. Nˆu ˙a ˙ ¯` ˙ ´ ´ ˙ ’ sˆ o o e a a.ı u oee e a ou e . . . ................. ................................... ................. ......................................................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 3 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......................................................................... . . . . . . ................. ................................... ................. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 6 7 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......................................................................... . . . . . . ................. ................................... ................. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 10 11 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ................. ................................... ................. ......................................................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 14 15 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ................. ................................... ................. ......................................................................... . . . . . H` 2.8: ınh ta biˆ’u diˆn mˆi v`ng nho bo.i mˆt d ınh v` mˆt canh liˆn thuˆc hai d ınh nˆu hai v`ng ˙ ˜ ˜ ´ ˙˙ ’’ o ¯˙ ’ ¯˙ ’ e e ou ao. e o e u . . . .o.ng u.ng c´ chung mˆt biˆn (h˜y v˜ h` .a vˆ t` tˆp ˆ’n d inh ngo`i c´ sˆ ˙ ¯. a e ınh!). B`i to´n d u ` ım a o ´ tu ´ o o e a a¯ e a oo . . phˆn tu. nho nhˆ t-l` β (G). Trong v´ du n`y, β (G) = 4 v` c´c tram g´c cˆn d ˇt tai c´c vi tr´ ` ´ a ` ¯a . a . ı a˙ ’ ˙ aa ’ ı.a aa a . . {3, 5, 12, 14} hoˇc tai {2, 9, 15, 8}. a. . V´ du 2.4.6 B`i to´n vˆ 5 con hˆu. Trˆn b`n c`. quˆc tˆ cˆn bˆ tr´ bao nhiˆu con hˆu dˆ’ ˙ aa` e a o o e` ´ ´a o ı ´ ı. e a e a ¯e . . . d` u bi ´ nhˆ t mˆt con hˆu khˆng chˆ. B`i to´n n`y d u.a vˆ t` mˆt ´o ´ ´ a a a¯ ` ım o cho moi ˆ trˆn b`n c` ¯ˆ . ıt a .o e a o e a o e e . . . tˆp ho.p ˆ’n d .nh ngo`i cu.c tiˆ’u cho d` thi c´ 64 d ınh (l` c´c ˆ cua b`n c`.), trong d ´ hai ˙ ˙ ¯˙’ aao˙ a o ’ a o ¯i a. e ¯ˆ . o o ¯o . . d ınh kˆ nhau nˆu v` chı nˆu c´c ˆ tu.o.ng u.ng nˇ m trˆn c`ng mˆt h`ng, mˆt cˆt hoˇc c`ng ` ` ´ ’´ ¯˙’ e a ˙e ao e ´ a eu oa oo au . .. . .`.ng ch´o. mˆt d u o o¯ e . Sˆ ˆ’n d .nh l` +5 d ˆi v´.i c´c con hˆu, chˇng han v´.i hai c´ch sˇp xˆp: ´˙ ˙ ’ ´´ ´ o o ¯i a ¯o o a a a .o a ae . (3, 3), (4, 6), (5, 4), (6, 2), (7, 5) v` a (5, 1), (8, 3), (4, 4), (3, 6), (7, 8), trong d ´ (i, j ) l` vi tr´ cua con hˆu o. h`ng i v` cˆt j. C˜ng dˆ thˆ y sˆ ˆ’n d .nh l`: +8 d ˆi e ´ ´˙ ˜ a o o ¯i ´ a.ı˙ ’ a˙a .’ ¯o ao u a ¯o . .i c´c con th´p; +12 d oi v´.i c´c con m˜; +8 d oi v´.i c´c con d iˆn. ´ ´ v´ a o a ¯ˆ o a a ¯ˆ o a ¯e http://www.ebook.edu.vn 63
V´ du 2.4.7 B`i to´n vˆ s´u c´i d˜a d o . Tr` cho.i sau d ˆy rˆ t quen thuˆc d ˆi v´.i nh˜.ng a a ` a a ¯ı ¯ ˙ ´ ´ ’ ı. e o ¯a a o ¯o o u . .`.i u.a th´ hˆi cho. Ph´p: Trˆn b`n d at mˆt c´i d˜ l´.n m`u trˇng (b´n k´ 1), h˜y ´ ngu o ıch o a e a ¯ˇ o a ¯ıa o a a a ınh a . . . . .i s´u d˜ con d o (b´n k´ r < 1) lˆn lu.o.t d ˇt trˆn b`n, ` ˙a ’ a ¯ıa ¯´ ˙ ’ ¯ ˙ a ınh ’ t` c´ch phu ho`n to`n d˜ d o bo a ¯ıa ım a a . ¯a e a . ` i th` khˆng d u.o.c xˆ dich n˜.a. Hoi b´n k´ r nho nhˆ t bˇ ng bao nhiˆu dˆ’ ˙ ˙a` ´a ˙ a ınh ’ ’ v` khi d ˜ d ˇt rˆ ı o ¯ . e . a ¯a ¯a o u e ¯e . .o.c? c´ thˆ’ giai d u . ˙’ o e ˙¯ B`i to´n d u.a vˆ t` mˆt tˆp ˆ’n d .nh ngo`i cu.c tiˆ’u T cho “d` thi vˆ han” (V, E ), ..˙ ˙ ` ım o a o ¯i a a¯ e a. e ¯ˆ . o . o .p c´c d iˆ’m cua d˜ trˇng, v` hai d ınh kˆ nhau nˆu khoang c´ch gi˜.a ˙ ´ ` ´ ˙ ¯ıa a ’ ¯˙’ ˙ ’ trong d o V l` tˆp ho a ¯ e ¯´ aa a e e a u . . .o.ng u.ng nho ho.n hoˇc bˇ ng r. hai d iˆ’m tu ˙ a` ˙ ’ ¯e ´ .a T`. d .nh ngh˜ dˆ d`ng suy ra ıa ˜ a u ¯i e 1. Tˆp gˆm d ung mˆt d ınh trong d` thi d` y d u Kn l` tˆp ˆ’n d .nh ngo`i cu.c tiˆ’u. .˙ ˙ a ` ¯´ o ¯˙ .’ ¯o . ¯a ¯ ˙ ’ .o ˆ ˆ a a o ¯i a. e 2. Moi tˆp ˆ’n d .nh ngo`i ch´.a ´ nhˆ t mˆt tˆp ˆ’n d .nh ngo`i cu.c tiˆ’u. .˙ ..˙ ˙ ´ o a o ¯i . a o ¯i a u ıt a a. e 3. Mˆt d` thi c´ thˆ’ c´ nhiˆu tˆp ˆ’n d .nh ngo`i cu.c tiˆ’u v´.i k´ thu.´.c kh´c nhau. ˙ e.˙ ˙ ` a o ¯i o ¯ˆ . o e o .o a. e o ıch o a 4. Tˆp ˆ’n d .nh ngo`i cu.c tiˆ’u c´ thˆ’ hoˇc khˆng l` ˆ’n d .nh trong. .˙ ˙ ˙. ˙ a o ¯i a. eoea o a o ¯i 5. Moi tˆp ˆ’n d .nh trong cu.c d ai l` tˆp ˆ’n d inh ngo`i. Thˆt vˆy, nˆu tr´i lai th` c´ ´ .˙ .˙ ´ . a o ¯i . ¯ . a a o ¯. a aa e a. ı o ıt .. ` m trong tˆp n`y v` c˜ng khˆng kˆ v´.i mˆt d ınh bˆ t k` trong ´ o ¯˙ ` o o ¯˙ ´ .’ .’ nhˆ t mˆt d ınh khˆng nˇ a o a a a au o e ay . d ´. Mˆt d ınh nhu. thˆ c´ thˆ’ thˆm v`o m` khˆng ph´ v˜. t´ ˆ’n d inh trong v` do d ´ ˙ ˙ ´ o ¯˙ ’ ¯o eo e e a ao a o ınh o ¯. a ¯o . .i t´ cu.c d ai cua n´. ˜ mˆu thuˆn v´ ınh . ¯ . ˙ o ’ a ao 6. Mˆt tˆp ˆ’n d .nh trong c´ t´ ˆ’n d .nh ngo`i chı nˆu n´ l` tˆp ˆ’n d .nh trong cu.c d ai. ..˙ ˙ .˙ ’´ ˙ e o a a o ¯i o a o ¯i o ınh o ¯i a . ¯. 7. V´.i moi d` thi G bˆ t d ang th´.c sau luˆn thoa ´˙ ’ ˙ ’ o . ¯o . ˆ a ¯ˇ u o β (G) ≤ α(G). T` c´c tˆp ˆ’n d .nh ngo`i cu.c tiˆ’u .˙ ˙ ım a a o ¯i a. e Tu.o.ng tu. c´ch x´c d .nh tˆp ˆ’n d inh trong cu.c d ai, ta c´ thˆ’ d`ng d ai sˆ Boole dˆ’ x´c d inh .˙ ˙ ˙ ´ .a a ¯i a o ¯. . ¯. o e u ¯. o ¯e a ¯. .c tiˆ’u cua d` thi G. c´c tˆp ˆ’n d .nh ngo`i cu e .˙ ˙ ˙ ¯ˆ . ’o a a o ¯i a. Dˆ’ kiˆ’m tra d ınh vi ta cˆn lˆ y hoˇc d ınh vi hoˇc mˆt d ınh kˆ v´.i n´. Tˆp nho nhˆ t -e e ˙˙ `a a´ `oo a ´ ¯˙ ’ a ¯˙ ’ o ¯˙ .’ ˙ ’a a e . . . c´c d ınh thoa m˜n d iˆu kiˆn n`y l` tˆp cˆn t` Do d ´, v´.i mˆi d ınh vi trong G ch´ng ta ˜’ ˙ a ¯` e a a a ` ım. a ¯˙ ’ ’ o ¯˙ e a ¯o o u . . x´t t´ Boole cua c´c tˆ’ng (vi1 + vi2 + · · · + vid ) trong d ´ vi1 , vi2 , . . . , vid l` c´c d ınh kˆ v´.i ˙ `o ˙ao ’ a a ¯˙ ’ e ıch ¯o e ˙nh vi v` d l` bˆc cua n´: ’ ˙o ’ dı ¯ a aa . θ= (vi1 + vi2 + · · · + vid ). vi ∈V http://www.ebook.edu.vn 64
Khi θ viˆt du.´.i dang tˆ’ng cua c´c t´ mˆ i sˆ hang trong d ´ s˜ tu.o.ng u.ng v´.i mˆt tˆp ˆ’n ˙ ..˙ ˜´ ´ ˙ a ıch, o o . ’ e o. o ¯o e ´ o oao .c tiˆ’u. Ch´ng ta minh hoa thuˆt to´n n`y su. dung d` thi trong H` 2.5. Ta ˙ aa˙. ’ d .nh ngo`i cu e ¯i a. u a ¯ˆ . o ınh . . c´ o θ = (a + b)(b + c + d + e + a)(c + b + e)(d + b + e)(e + b + c + d + f + g )(f + e + g )(g + e + f ). .´ Theo luˆt hˆ p thu (x + y )x = x ta suy ra aa . θ = (a + b)(c + b + e)(d + b + e)(f + e + g ) = ae + be + bf + bg + acdf + acdg. Mˆi sˆ hang trong s´u biˆ’u th´.c n`y tu.o.ng u.ng mˆt tˆp ˆ’n d .nh ngo`i tˆi thiˆ’u. Hiˆ’n ˙ ..˙ ˙ ˙ ˜´ ´ oo. a e ua ´ o a o ¯i ao e e nhiˆn β (G) = 2. e Dˆ’ x´c d inh mˆt tˆp ho.p ˆ’n d .nh trong cu.c d ai, hay mˆt tˆp ho.p ˆ’n d .nh ngo`i cu.c - e a ¯. ˙ ˙ ˙ oa . o ¯i . ¯. oa . o ¯i a. .. .. .o.t mˆ i tˆp ho.p con T cua V v` kiˆ’m tra xem n´ c´ thoa m˜n c´c tiˆ’u, ta c´ thˆ’ x´t lˆn lu . ˙ ˙ ˙ ˜. o ee` ˙ ’ ˙aa ’ e a oa ae oo . d iˆu kiˆn d a d` ra hay khˆng. Tˆ t nhiˆn phu.o.ng ph´p loai dˆn n`y n´i chung khˆng d`ng ¯` ´ .` e e ¯˜ ¯ˆ e o a e a aao o u . .o.c. Ngu.`.i ta cˆn phai d u.a ra c´c thuˆt to´n. Chˇng han, khi giai quyˆt b`i to´n vˆ t´m ˙ ’ ` ´ a a `a ˙¯ ’ ˙ ’ du . ¯ o a a a a a e e . . con hˆu, nˆu d`ng phu.o.ng ph´p loai dˆn cˆn khoang 10 gi`. dˆ’ t´ to´n, trong khi d o nˆu ˙ ´ `` ´ ˙ ’ a eu a aa o ¯e ınh a ¯´ e . . .a d u; ngo`i ra cˆn ch´ y rˇ ng: nˆu ` ´ ˙` ` ´ c´ mˆt thuˆt to´n tˆt, ch´ng ta chı cˆn ba ph´t l` th` ¯ ˙ ’a ’ oo a ao u uau a a u´ a e . . .o.c viˆc xˆp 8 con hˆu trˆn b`n c`., th` mˆt lˆp luˆn rˆ t d o.n gian chı cho ta r˜ ´ ´¯ ˙ ’ ˙ ’ ta d a d at d u . ¯˜ ¯ . ¯ ee a eao ıoa aa o . . .. . rˇ ng khˆng thˆ’ l`m tˇng sˆ con hˆu lˆn d u.o.c n˜.a trong tru.`.ng ho.p tˆ’ng qu´t ho.n, c˜ng ˙ ˙ ` ´ a o ea a o a e ¯. u o o a u . . cˆn c´ mˆt tiˆu chuˆ’n d o.n gian dˆ’ nhˆn biˆt mˆt tˆp ho.p ˆ’n d .nh trong cu.c d ai hay khˆng, ˙ ˙. ˙ `ooe ´ oa ˙ ¯e a ’ a a¯ e . o ¯i . ¯. o . .. v` chı c´ thuˆt to´n d ˜ d u.o.c suy ngh˜ k˜ m´.i c´ thˆ’ gi´p ta biˆt d iˆu d ´ (xem [4]). ˙ e ¯ ` ¯o ´e a ˙o ’ a a ¯a ¯ . ıy o o e u . ˙ ’ 2.5 Phu Tˆp g c´c canh d u.o.c goi l` phu cua d` thi G = (V, Γ) nˆu mˆ i d ınh bˆ t k` thuˆc V liˆn ˜’ ´ ´ ˙ ˙ ¯ˆ . ’’ o o ¯˙ a a. ¯. .a e ay o e . . .i ´ nhˆ t mˆt canh trong g. ´o. thuˆc v´ ıt a oo . . V´ du 2.5.1 (a) Cˆy bao tr`m trong d` thi vˆ hu.´.ng liˆn thˆng l` mˆt phu. ˙ ’ ı. a u ¯o . o o ˆ e o ao . (b) Chu tr` Hamilton (nˆu n´ tˆn tai) trong d` thi l` mˆt phu. e o` . ´ ˙ ’ ınh o ¯o . a o ˆ . V´ du 2.5.2 Trong trai giam cua th`nh phˆ N, so. d` v˜ k`m theo d ˆy, mˆ i ngu.`.i g´c o. ˜ ´ ˙ ’ o a˙ ’ ı. a o ¯o e e ˆ ¯a o . .`.i g´c h`nh lang (a, b) phai gi´m s´t hai gian a v` b l` hai d` u cua h`nh lang; hoi sˆ ngu o a ’´ ˙a ’ ˙a ’ ˙o a a aa ¯ˆa ´t l` bao nhiˆu dˆ’ mˆi gian ´ nhˆ t c´ mˆt ngu.`.i gi´m s´t? B`i to´n n`y d u.a vˆ t` ˙o ˜ ´oo ` ım ´ nhˆ a ıt a e ¯e ıt a oa a a a a¯ e . .c tiˆ’u cua mˆt d` thi. Trˆn d` thi H` 2.11, phu nho nhˆ t c´ nˇm d ınh, vˆy nˇm ˙˙ ´ ˙. ’ ’ ˙ ’ ˙ ’ a o a ¯˙ ’ phu cu e o ¯o . ˆ e ¯o . ınh ˆ aa . . ngu.`.i g´c l` d u. o a a ¯˙ ’ http://www.ebook.edu.vn 65
• ... ... . .. .. .... ............... .... ............... .... .... ....... ....... .... ......... .... .... ....... .... ....... .... .... .... ....... .... ....... .... .... .... ....... .... ....... .. .... . .... ....... .... .... ....... .... ....... .. . .... ....... .... .... .... ....... .. . ....... .... . .. ........................................................................ .... .................................................................. • • ....... • ....... ....... ..... .. .... ....... .... .. .. . ..... .. .. ...... .... .. .... ... .... ... . • ... ....... ..... ..... ..... .... ... ...... . .. .... .. .. .. .. ..... ..... ... .... ....... .......... .... .... ....... .......... ... .... .. ..... . ..... • • ......... .. ........ ... . . ... ... .... ... .... ..... . .. . ... ... ... ... .. .. ... .. . . .... ... .... ... ... ... ... ... ... ... .... .... ... .... ... ... .... ... ... ... .... .... ... • ... ... ...... ... . .. ..... .... ... . .... ... ... .... ... . . . .. . ... .... .. . .... ... . ... ... . .... ... .... ... . ... . .... ... . .... ... ... . .... ... ... . .... ... ... . ... ....... ... . .... ....... . ... . ... . ........ . ... . ... ..... .. .... ....... ... . ...... • ..... ..... H` 2.9: ınh Trong mˆt d` thi, c´ thˆ’ c´ nhiˆu phu, vˆ n d` o. d ay l` cˆn nghiˆn c´.u phu m` c´ ˙ ` ˙ a ¯ˆ ˙ ¯ˆ a ` ’ ´ e’ ˙ ao ’ o ¯o . o e o .ˆ e a eu . cˆy bao tr`m hay chu tr` Hamnilton. Ta s˜ nghiˆn ´. mˆt v`i t´ chˆ t d ac biˆt n`o d ´ nhu a o a ınh a ¯ˇ e a ¯o u ınh e e . . c´.u phu tˆi thiˆ’u: l` phu m` nˆu bo d i mˆt canh th` s˜ ph´ huy thuˆc t´ phu cua n´. ˙a ’´ ´ ˙¯ o . ˙o ˙ ae ’ ’ ıe a ˙ ’ ˙˙ o ’’ u e o ınh . . T`. d .nh ngh˜ dˆ d`ng suy ra ıa ˜ a u ¯i e 1. Tˆn tai phu trong mˆt d` thi nˆu v` chı nˆu d` thi khˆng c´ d ınh cˆ lˆp. `. ´ ’´ ˆ ˙ ’ o ¯o . e a ˙ e ¯o . o o ¯˙’ o .ˆ oa . 2. Mˆt phu cua d` thi n d ınh c´ ´ nhˆ t [n/2] canh (k´ hiˆu [x] l` sˆ nguyˆn l´.n nhˆ t ´ ´ ´ ˙ ˙ ¯o . ¯˙ ’’ ˆ ’ o o ıt a ye ao eo a . . . .o.t qu´ x). khˆng vu . o a ¯ˆ . ` 3. Moi canh treo trong d` thi nˇ m trong phu cua d` thi. ˙ ˙ ¯ˆ . ’’ o o a .. 4. Moi phu d` u ch´.a phu tˆi thiˆ’u. ˙ ’´ ˙ ¯ˆ ’e ˙o u e . 5. Tˆp c´c canh g l` mˆt phu nˆu v` chı nˆu, v´.i moi d ınh v ∈ V ta c´ dG\g (v ) ≤ dG (v )−1, ’´ ’´ ˙e a ˙e . ¯˙ ’ aa. ao o o . . ` thi G xo´ d i c´c canh thuˆc g. trong d o G \ g l` d ˆ . ¯´ a ¯o a¯ a . o . 6. Phu tˆi thiˆ’u khˆng ch´.a chu tr` ˙ ınh. Do vˆy moi phu tˆi thiˆ’u cua d` thi n d ınh khˆng ˙’ˆ ’´ ’´ ˙o ˙o e ˙ ¯o . ¯˙ ’ e o u a o . . .a ho.n (n − 1) canh. ch´ u . 7. Mˆt d` thi, n´i chung, c´ nhiˆu phu tˆi thiˆ’u, v` ch´ng c´ thˆ’ c´ k´ thu.´.c kh´c ˙ ˙ ` ’´ ˙o o ¯ˆ . o .o o e e au o e o ıch o a ` m sˆ c´c canh kh´c nhau). Sˆ c´c canh trong mˆt phu tˆi thiˆ’u c´ c˜. nho ˙ oo ´a . ´a . ’´ ˙o ˙ ’ nhau (gˆ o o a o o e . .o.c goi l` sˆ phu cua d` thi. ´ ´ ˙ ˙ ¯ˆ . ’’ o nhˆ t d u . a¯ . ao Dinh l´ 2.5.3 Phu g cu a mˆt d` thi l` tˆi thiˆ’u nˆu v` chı’ nˆu g khˆng ch´.a c´c dˆy -. ˙ e a ˙e ´ ´ ´ ˙ ’ ˙ ’ y o ¯ˆ . a o .o e o uaa .n ho.n hoˇc bˇ ng ba. a` ` o ¯o a o chuyˆn c´ d ˆ d`i l´ e .a . Ch´.ng minh. Diˆu kiˆn cˆn. Gia su. g l` phu tˆi thiˆ’u cua G m` ch´.a mˆt dˆy chuyˆn c´ -` ˙˙ e` ’´ `o ˙˙ ’’ ˙o ’ u e .a a e au oa e . d o d`i ba l` ¯ˆ a a . µ := {v1 , e1 , v2 , e2 , v3 , e3 , v4 }. Trong g bo canh e2 th` ta vˆ n thu d u.o.c mˆt phu cua G, d iˆu n`y mˆu thuˆn v´.i t´ tˆi ˜ ˜ ¯` ´ ˙. ’ ˙˙ ’’ ı a ¯. o ea a a o ınh o . ˙u cua g. ’˙ ’ thiˆe http://www.ebook.edu.vn 66
• •...... • • .. .. . . . .. . . . . .. . . .. . . . . . . .. .. . . .. .. . . . . .. .. . . .. .. . . . . .. . . . .. . . . .. . . .. ... .. . . . . .. ... . . . . •.................................................•................................................• • • • • .. .. . . . . .. . . . ... .. .. . ...................................................... ..................................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • • . . . . . . . . . (a) (b) (c) (d) H` 2.10: C´c d` thi h` sao. ınh a ¯ˆ . ınh o Diˆu kiˆn d u. Ngu.o.c lai, nˆu g khˆng ch´.a mˆt dˆy chuyˆn n`o c´ d o d`i l´.n ho.n hoˇc -` ´ ` e ¯˙ ’ e e o u oa e a o ¯ˆ a o a . .. . . . ` ng ba th` c´c th`nh phˆn cua n´ phai c´ mˆt trong c´c dang “h` sao” nhu. trong H` `a˙o ’ ˙oo ’ bˇ a ıa a a. ınh ınh . 2.10. Hiˆ’n nhiˆn nˆu xo´ bˆ t k` mˆt canh cua d` thi h` sao th` s˜ c´ ´ nhˆ t mˆt d ınh ˙ ´ ´ ´ o ¯˙ ˙ ¯ˆ . ınh ’o .’ e ee aa y o . ı e o ıt a . .i canh c`n lai cua g. Vˆy g l` phu tˆi thiˆ’u. ˙ ’´ o.˙ ’ ˙o khˆng liˆn thuˆc v´ . o e oo a a e . . V´ du 2.5.4 Gia su. d` thi trong H` 2.11 biˆ’u diˆn ban d` giao thˆng cua mˆt th`nh ˙ ˜ ˙ ˙ ¯ˆ . ’’o ˙ ¯o ’ ˙ ’ ı. ınh e e ˆ o o a . .`.ng xay ra tˇc ngh˜n v` mˆ i canh tu.o.ng u.ng mˆt ˜’ ´ ˜ ´ o ¯˙ ˙ ’ phˆ. Mˆ i d ınh l` mˆt n´t giao thˆng thu o o aou o a eao. ´ o . . ˙ gi´m ’a ´ ` ¯ˇ a ¯o ` d ai lˆ nˆi hai n´t giao thˆng. Cˆn d at c´c d ˆi tuˆn tra trˆn c´c d ai lˆ sao cho c´ thˆ ¯. o o u o a a e a ¯. o oe . . . . s´t tˆ t ca c´c n´t giao thˆng. Vˆ n d` d ˇt ra l` sˆ tˆi thiˆ’u c´c d ˆi tuˆn tra l` bao nhiˆu? ˙ ´’ ´ e. ´´ e a ¯o ` aa ˙a u o a ¯ˆ ¯a aoo a a e . Cˆu tra l`.i ch´ l` t` phu tˆi thiˆ’u v´.i sˆ phˆn tu. ´ nhˆ t cua d` thi. Dˆ kiˆ’m tra hai ˙ e˙ ˜e ’´ e oo` ´ a ˙ ıt a ˙ ¯o . ´’ˆ ˙o ’ ˙o ’ a ınh a ım tˆp sau l` phu tˆi thiˆ’u: ˙ ’´ ˙o a a e . {(a, d), (b, e), (c, f ), (f, i), (g, h), (k, l)} v` a {(a, b), (b, d), (b, e), (c, f ), (f, g ), (f, i), (h, l)}. Do c´ 11 d ınh v` mˆi canh phu nhiˆu nhˆ t hai d ınh nˆn khˆng thˆ’ phu d` thi ´ ho.n s´u ˙ ˜ ` ´ ¯˙’ ˙ ’ ¯˙’ ˙ ¯o . ıt ’ˆ o ao. e a e o e a canh. . e h b •.........................................................................•.........................................................................•..........................................................................• l .. .. ... .. .. .. .. .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... ... ... . . ... ... ... . . . . . . . . . . ... ... ... . . ... ... ... . . . . . . . . ... ... ... ... ... ... . . . . . . . . . . . . ... ... ... ... ... ... . . . . . . . . . . ... ... ... ... ... ... . . . . . . . . ... ... ... . . . . ... ... ... . . . . . . . . ... ... ... . . ... ... ... . . . . . . . . . . ... ... ... . . ... ... ... . . . . . . . . ... ... ... . . ... ... ... . . . . ... . ... . . ... . ... . ... . ... . . . ... . ... . ... . . . ... . . ... . . ... . . . . a• .. .. • • •k . . .. ............................... ............................................................. ................................................................................................. . .. .. . . ... .. ... ... .. ... . ... . .... . ... . . .. . . ... g . . ..... ... . ... ... . d .. . ... .. . . ..... . . ... ... ... ... . ... . . . ... ... ... . ... ... . . ... . . ... ... ... . ... ... . ... . . . ... ... ... . ... ... . . ... . . ... . ... . .. ... . ... ... . . .. . . ... ... ... . ... . ... ... . . ... ... . . ... ... ... . ... . . ... . ... ... . ... . ..... ... ... . ..... . . ... . . ... . ... . ... ... . . ... . .... ... . ... . .. . ... . .. . . . • • •i .... .................................................................. ................................... ............................ ..... .. .. .. .. .. .. c . f .. .. .. .. .. .. .. .. .. .. .. .. ... ... ... ... ... .... ...... ......... ................ .... H` 2.11: ınh http://www.ebook.edu.vn 67
Cu.c tiˆ’u ho´ h`m Boole ˙ e aa . Mˆt phˆn quan trong trong viˆc thiˆt kˆ c´c mach sˆ l` cu.c tiˆ’u ho´ h`m Boole tru.´.c khi ˙ ` ´´ ´ o a e e ea oa . e aa o . . . . . ta muˆn xˆy du.ng mach logic cho bo.i h`m Boole bˆn biˆn ´´ ´ ´ ´ ˙˙ ’’ ˙a ’ thiˆt kˆ n´. Gia su e eo oa o e . . f (x, y, z, w) = w x y z + w x y z + w x y z + w xyz + w xyz + wxyz. Ch´ng ta h˜y biˆ’u diˆn mˆi mˆt trong bay th`nh phˆn cua f bo.i mˆt d ınh v` mˆt canh ˙ ˜ ˜ ` ˙ ’ ˙ ’ ˙ ’ o ¯˙ .’ u a e e oo a a ao. . . ´ -ˆ . liˆn thuˆc hai d ınh nˆu v` chı nˆu hai th`nh phˆn chı kh´c nhau d ung mˆt biˆn. D` thi ´ ’´ ` ¯˙ ’ e a ˙e ˙a ’ e o a a ¯´ o e o . . .o.ng u.ng h`m f cho trong H` 2.12. tu ´ a ınh w xyz •. .. .... ... ... ..... ... ..... ... ... ... .. ... . ... ... ... ... e.3................... e4 ... ... ... ... wxyz ... e2 e7 ... wxyz .. . ... ... ... ... ... ... . . ... ... ... ... • • • • . ........................................................ ........................................................ ........................................................ ........................................................ ... .. ... . . ... ... . ... ... . ... . ... ... w x yz w xyz . ... . . . ... . ... ... ... . . . ... e5 e6 . ... ... . ... . ... . ... ... .. . . ... ... ... ... . . ... ... ... . ... . ... ... . ... ... . . ... ... ... ..... ... ..... . e1 . • . . .. .. . . . . . . w x yz . . . . . . . . . . . . . . . . . . . • . . . wx y z H` 2.12: ınh Mˆt canh liˆn thuˆc hai d ınh tu.o.ng u.ng mˆt th`nh phˆn v´.i ba biˆn. ` ´ ¯˙’ o. e o ´ o a ao e . . . Mˆt phu tˆi thiˆ’u cua d` thi cho ta mˆt d o.n gian ho´ h`m Boole f, v´.i c`ng ch´.c ˙ ’´ ˙o ˙ ¯o . ’ ˙ ’ o e ˆ o¯ aa ou u . . . f nhu.ng thiˆt kˆ su. dung ´ cˆ’ng logic ho.n. ˙ ´ e ˙ . ıt o ´’ nˇng nhu a e C´c canh treo e1 v` e7 cˆn thuˆc moi phu cua d` thi. Bo.i vˆy c´c th`nh phˆn x y z ` ` ˙ ˙ ¯o . ’’ ˆ ˙aa ’. a. a a o a a . . ˙ khu. d u.o.c. Hai canh e3 v` e6 (hoˇc e4 v` e5 , hoˇc e3 v` e5 ) s˜ phu c´c ’ ˙¯.’ ˙a ’ v` xyz l` khˆng thˆ a ao e a a a a a e . . . d ınh c`n lai. Do d o ta c´ thˆ’ viˆt lai ˙´ ¯˙’ o. ¯´ oee. f = x y z + xyz + w y z + w y z. w yz •. . . . . . . . . . . xyz . . . . . . . . • • . . . . . . . . xyz . . . . . . . . . . . . . . • . . . w yz H` 2.13: ınh http://www.ebook.edu.vn 68