Lí thuyết đồ thị part 3

Chia sẻ: ágffq ằefgsd | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

107
lượt xem 18
download

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

Cấu trúc đồ thị có thể được mở rộng bằng cách gán trọng số cho mỗi cạnh. Có thể sử dụng đồ thị có trọng số để biểu diễn nhiều khái niệm khác nhau. Ví dụ, nếu đồ thị biểu diễn một mạng đường giao thông, các trọng số có thể là độ dài của mỗi con đường. Một cách khác để mở rộng đồ thị cơ bản là qui định hướng cho các cạnh của đồ thị (như đối với các trang web, A liên kết tới B, nhưng B không nhất thiết cũng liên kết tới A). Loại...

Chủ đề:

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

Lưu

Nội dung Text: Lí thuyết đồ thị part 3

x1 x2 x • • • •...................................................................................................................• ......................................................... ......................................................... .. . .. . ... ... .... . .. .... . .... ..... .... .. . . ... .. ..... . . ... .. ... .. ..... ... .. . . . . .. .. .. . .. . . ... ... .. ... .. ... . . ... .. ... .. ... ... . . ... . . ... ... .. .. .. .. ... . . .. ... .. ... . . ... ... . . ... ... .. .. .. . . .. .... .. ... ... . . ... . ... . . ... .. ... .. ... . . ... .. ...... .. .. ... . . ... ... . . . .. . ...... • • ... . . . ... ....... ...... ... . . . ... ... . . . . . . ... ... .. .. . . ... ... . . . . ... .. .. ... ... . . .. .. ... . . ... . . ... ... .. .. ... . . .. .. g1 ¯ . . ... ... . . ... ... .. .. . . .. .. ... . . ... ... . . ... .. .. . . ... ... .. .. . . ... ... . . ... . . ... .. .. ... . . .. .. ... g1 . . ... ... . . ... .. .. ... . . .. .. . . ... ... ... ... . . .. .. . . ... .. .. ... . . ... ... . . .. .. ... . . ... .. .. ... . . ... . . ... ... .. .. . . ... ... .. .. . . ... . . ... ... . . .. .. ... .. .. ... . ... . ... . . ... . ... . ... . .. .. ... . .. .. . . ... . .. . ... . ... . .. .. .. .. . .. • • • • • . . ....................................................... ...................................................... .. .. . ...................................................... . . .................................................... y y1 y2 (a) (b) x1 x2 • •...................................................................................................................• • • . .. . .. . ...................................................... ...................................................... . ... .. .... .. . . . . . . .... . . .. ..... .. . . . . . . ... .. ... . . ... .. .. . . . ... ... . . ... ... .. .. . . . . ... . . ... ... . . ... .. .. . . .. .. ... ... . . ... ... . . ... . . .. .. ... ... . . . . ... g1 . . ... ... . . .. .. ... ... . . . . . . ... ... ... . . .. .. ... . . . . ... . . ... ... .. .. ... . . .. .. . . ... ... . . ... ... . . .. .. ... g1 ¯ . . . . ... ... . . ... . . .. .. ... ... . . . . ... ... . . ... . . .. .. ... ... . . . . ... . . ... ... . . .. .. ... ... . . . . . . ... ... ... ... • ... • . . ... ...... ...... . . ... . . ... ... . . . . ... .. .... .. .... . . .. ... .. ... . . ... ... . . ... .. .... .. .... ... . . .. ... .. ... ... . . ... ... ... . . .. ... .. ... . . .. ... .. ... ... ... ... . . ... . . .. ... .. ... ... . . .. .. . . ... .. ... ... . . . ... . ... . .. ... ... .. ... .. . . ... ... .. .. . ... . . .. ... . ... . ... .. ... ... . . . ... . ... . ... . ... .. ... . ... .. ... .. ............................................................ ... . . . • • • • • ... ...... .. ...................................................... ...... .. ..... .. . ...................................................... .................................................... . . .. y1 y2 (c) (d) H` 1.24: ınh d .nh ngh˜ suy ra c´c d` thi d ang cˆ u c´ tu.o.ng u.ng chu tr` ˙ ’ ´ ¯i ıa a ¯ˆ . ¯ˇ o ao ´ ınh. V` trong d` thi c´ d iˆ’m kh´.p G, mˆi chu tr` thuˆc mˆt khˆi n`o d o, nˆn mˆ i chu ˙ ˜ ˜ ´ ı ¯ˆ . o ¯ e o o o ınh o o o a ¯´ e o . . ˜n tu.o.ng u.ng c´c canh cua n´ khi thu.c hiˆn Ph´p to´n 1 trˆn G. Do d o, c´c ˙o ’ tr` trong G vˆ ınh a ´ a. e e a e ¯´ a . . d` thi 1−d ˇng cˆ u c´ t´ chˆ t tu.o.ng u.ng chu tr` ˙ ’ ´ ´ ¯o . ˆ ¯a a o ınh a ´ ınh. Tu.o.ng tu., x´t chu tr` µ trong d` thi G sau khi thu.c hiˆn Ph´p to´n 2 trˆn G. V´.i .e ınh ¯o . ˆ e e a e o . . .`.ng ho.p xay ra: ˙ ’ chu tr` µ, ta c´ ba tru o ınh o . ` 1. C´c canh thuˆc µ nˇ m ho`n to`n trong g1 ; hoˇc a. o a a a a . . ` 2. C´c canh thuˆc µ nˇ m ho`n to`n trong g1 ; hoˇc a. o a a a ¯ a . . 3. C´c canh thuˆc µ nˇ m trong ca hai d` thi con g1 v` g1 ; v` trong tru.`.ng ho.p n`y µ ` ˙ ’ a. o a ¯o . ˆ a¯ a o a . . .a ca hai d ınh x v` y. phai ch´ ˙ ˙ ’ u’ ¯˙’ a Trong c´c Tru.`.ng ho.p 1 v` 2, chu tr` µ khˆng anh hu.o.ng qua Ph´p to´n 2. Trong Tru.`.ng o˙ ’ ˙ ’ a o a ınh e a o . .p 3, µ vˆn gˆm c´c canh c˜, ngoai tr`. dˆy chuyˆn gi˜.a c´c d ınh x v` y trong g (thuˆc ˜` ` u a ¯˙ ’ ho ao a. u . ua e a o . . 1 chu tr` µ) bi “d ao ngu.o.c lai”. Do d ´, mˆ i chu tr` sau Ph´p to´n 2 vˆ n gˆm ch´ ˜ ˜o a` ¯˙’ ınh ¯o o ınh e a ınh . .. nh˜.ng canh c˜. Suy ra c´c d` thi 2−d ˇng cˆ u c˜ng c´ t´ chˆ t tu.o.ng u.ng chu tr` ˙’ ´ ´ u u a ¯o . ˆ ¯a au o ınh a ´ ınh. . 45
Dinh l´ 1.5.3 Hai d` thi l` 2−d ˇ ng cˆ u nˆu v` chı’ nˆu ch´ng c´ tu.o.ng u.ng chu tr` -. ˙ ’ ´´ ´ a e a ˙e y ¯ˆ . a o ¯a u o ´ ınh. Ch´.ng minh. Diˆu kiˆn d u suy t`. c´c l´ luˆn trˆn. Ch´.ng minh d iˆu kiˆn cˆn kh´ ho.n v` -` ¯` e` e ¯˙ ’ u e uay a e u e .a o a . c´ thˆ’ xem [55]. ˙ oe Nhu. s˜ thˆ y sau, c´c kh´i niˆm 2−d ang cˆ u v` tu.o.ng u.ng chu tr` d ong vai tr` quan ˙ ’ ´ ´ ea a ae ¯ˇ aa ´ ınh ¯´ o . .u d ˆi ngˆu cua c´c d` thi phˇng. ˜ ˙ a ¯ˆ . a ˙ ’ ´ ’ trong khi nghiˆn c´ ¯o eu a o . C´c d` thi d ac biˆt 1.6 a ¯ˆ . ¯ˇ o e . . Phˆn n`y gi´.i thiˆu mˆt sˆ d` thi d ˇc biˆt thu.`.ng gˇp trong c´c mˆ h` thu.c tˆ. C´c d` ` . ´ˆ ´ aa o e o o ¯o . ¯a e o a a o ınh . e a ¯ˆ o . . . . .o.c quan tˆm nhiˆu v` ` thi n`y d u . a¯ a e ı: . • T`. ph´t biˆ’u mˆt sˆ b`i to´n; ˙ .´ ua e ooa a • T`. c´c t´ chˆ t d ac biˆt cua ch´ng; ´. e˙ .’ u a ınh a ¯ˇ u .´ • Phuc vu cho mˆt sˆ thuˆt to´n. oo a a . . . -ˆ . D` thi khˆng c´ mach 1.6.1 o o o. Dˆy l` d` thi thu.`.ng gˇp nhˆ t khi biˆ’u diˆn c´c quan hˆ th´. tu. bˆ phˆn trˆn c´c phˆn tu.: - a a ¯o . ˙ ˜a ´ ` a˙ ’ ˆ o a a e e e u.o a ea . . . . .i mˆt quan hˆ th´. tu. ≤ trˆn tˆp V, x´t d` thi G = (V, E ) trong d ´ v´ o o e u. ea e ¯ˆ . o ¯o . . . (vi , vj ) ∈ E ⇔ i ≤ j. C´c b`i to´n luˆng trˆn mang vˆn tai x´t c´c d` thi n`y (c˜ng xem c´c b`i to´n lˆp lich ` a ˙ e a ¯o . a ’ aa a o e ˆ u aa aa. . . . trong [30]). -ˆ . ˙ ’ D` thi phˇ ng 1.6.2 o a D` thi vˆ hu.´.ng G goi l` phˇng nˆu c´ thˆ’ biˆ’u diˆn trˆn mˆt mˇt phˇng R2 v´.i c´c d ınh -ˆ . o o ˙˙ ˙ ’ ˜ ˙ ’ ´ o a ¯˙ ’ o .a a eoee e e o a a . . .o.ng u.ng c´c d iˆ’m phˆn biˆt trˆn R2 v` c´c d u.`.ng cong khˆng tu. cˇt tu.o.ng u.ng c´c canh ˙ ´ tu ´ a ¯e a ee aa ¯o o .a ´ a. . sao cho hai d u.`.ng cong bˆ t k` khˆng cˇt nhau ngoai tr`. tai c´c d ınh chung. ´ ´ u . a ¯˙ ’ ¯o ayo a . D` thi trong H` 1.25(a) l` phˇng v` ch´ng ta c´ thˆ’ v˜ lai nhu. trong H` 1.25(b). -ˆ . ˙ ˙ ’ o ınh aa ıu o ee. ınh C´c d` thi phˇng s˜ d u.o.c nghiˆn c´.u trong Chu.o.ng 6. ˙ ’ a ¯ˆ . a o e¯ . eu 46
........................... ..................... ...... ..... .... a a .... .... .... .... ... ... ... ... ... ... ... ... ... ... .• • ... ... ... ... ...... ..... ... .. .... ... ... .. .. . ..... ....... . ... .. ........ ... . . .... .. ... .. .. ..... .. .. .. . . .. . . .. . . . ... .. ... . . .. .. ... . . .... .. ... .. . ..... .. .. .. . ... . ... .. .. . .. ... . .. ... .. . .. ... . .. .. ... ... ... ... ... .. . .. .. . . .... .. . .. . ... ... . ... ... .. . . ... . .. ... . .. . .. . . .... . ... ... .. . ... ... . . . .. . . .. . . . . ... ... ... ... .. .. ... ... ... ... . . . . . . . . . ... ... ... ... .. . . ... ... . .. ..... . ... ... .. ...... . . . ... . ... . . . ... . ... . . . . .. . . .. . ... . ... ... .. . . ... ... ... . ........ . ... . . . . . ... ... . . . . ... ... . .. . .... . . . . . ... ..... ... ... ..... . . . e• e• ... .... . •b •b . . . .. .. ... . ... .......................................................................... .. ... .. .............................................. .......................... .. . . . . .... . . . . . . . .. . . . .. . . . . . .. . . . ... . . . . . ... . . .. . . . . . . . . .. . . ... . . . .. . . . ... . . . . . . . . . . . . . . .. . .. . . . . . .. . ... . . . ... . . . .. . . . . . . . . . . . . . . . . . . . . . . ... . . . ... . . . . . . .. . . . . . . . .. . ... . . . . ... . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . . . . ... . . . . . . . .. . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . . . . . . . ... .. . . . . ... . . . . . . . . . . . . . . . . ... . . . ... . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . ... . ... . . . . . . . . . . . . . . . . . . . ... . . . . . ... . . . . . . . . . . . . . . . . . ... . . . . . ... . . . . . . . . . . . . . . . . . . ... . . ... . . . . . . . . . . . . . . . . . ... . . . ... . . . . . . . . . . . . . . . . . . .. . . . . . ... . . . . . . . . . ... . . . . . . . . . . . ... . .. . . . .. . . . .. .. .. .. ... .. .. . .. .. ... . .. .. .. .. . . . ..... .. .. .. .. . .. .. . . ..... .. . . . .. . .. .. . . .. .. . .. .. . . . ... .. .. .. . . .. . .. .. . . . ... .. .. .. .... .. . . .. ....................................................... • • • • .... . ....................................................... .. . . . .. .................................................... ...................................................... . . .. . . ..... . . ...... ...... . . ..... . ..... c c .. .... d d .... . .... .. .. .... .... .. .. ..... ..... ... ... ...... ...... . ... .. ......... ...................... ........... .................. (a) (b) H` 1.25: D` thi (a) d u.o.c biˆ’u diˆn lai trong h` (b) l` phˇng. -ˆ . ˙ ˜. ˙ ’ ınh o ¯. e e ınh aa 47
48
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. 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` d ˆc lˆp. -. ` ´ ´ ˙ ’ y o a o . ¯. a ınh ¯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 . 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` nˆu v` chı’ nˆu ν (G) = 0. - ¯ˆ . o o ´ ´ ˙ ’ ınh e a ˙ e e o o o . (b) Da d` thi vˆ hu.´.ng G c´ d ung mˆt chu tr` nˆu v` chı’ nˆu ν (G) = 1. - ¯o . o o ´ ´ ınh e a ˙ e ˆ 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´ ¯o a e ınh. .. 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 . 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 . 52
Tu. d .nh ngh˜ dˆ d`ng suy ra ıa ˜ a ` ¯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` -. -ˆ . o o ´´ ´ a e a ˙e o o y o o a o ınh 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: 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 . 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 . .. 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 . 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 . 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 . . 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. mˆ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 ˙ ˙ ˙˙ ˜ o ın e o e a e a ın e oeea ı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 . 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 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 . .. 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 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 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 64