Đồ thị và các thuật toán – Chương 2: Các số cơ bản của đồ thị

Chia sẻ: Lão Lão | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

29
lượt xem 2
download

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

Đồ thị và các thuật toán – Chương 2: Các số cơ bản của đồ thị. Nội dung chính trong chương này gồm có: Chu số, sắc số, số ổn định trong, số ổn định ngoài, nhân của đồ thị, trò chơi Nim,... Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.

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: Các số cơ bản của đồ thị

Chu.o.ng 2 C´ o´ co. ba˙’n cu˙’a d ac sˆ `o thi. ¯ˆ 2.1 o´ Chu sˆ Kh´ai niˆe.m m`a ch´ung ta s˜e d¯`ˆe cˆa.p o˙’. d¯ˆay khˆong phu. thuˆo.c v`ao su.. d¯.inh hu.´o.ng: ta s˜e n´oi vˆ `e ca.nh ch´ . ˙’ - ˙ ’ ˙ ’ ` . . u khˆong phai cung. Dˆe tˆo ng qu´at x´et d¯a d¯ˆo thi. vˆo hu ´o ng G := (V, E) c´o n d¯ınh, m ˙ ’ ca.nh v`a p th`anh phˆ`an liˆen thˆong. D - ˇa.t ρ(G) := n − p, ν(G) := m − ρ(G) = m − n + p. Ta go.i ν(G) l`a chu sˆo´ cu˙’a d¯`oˆ thi. G. - i.nh l´ D y 2.1.1 Cho d¯a d¯`ˆo thi. vˆo hu.´o.ng G = (V, E). Gia˙’ su˙’. G0 l`a d¯`ˆo thi. nhˆa.n d¯u.o..c t` u. G bˇ`a ng c´ach nˆo´i hai d¯ı˙’nh a v`a b cu˙’ a G bo˙’.i mˆo.t ca.nh m´o.i; nˆe´u a v`a b tr` ung nhau hoˇa.c c´o thˆe˙’ . . nˆo´i v´o i nhau bo˙’ i mˆo.t dˆay chuyˆ`en cu˙’ a G th`ı ρ(G0 ) = ρ(G), ν(G0 ) = ν(G) + 1; trong tru.`o.ng ho..p ngu.o..c la.i ρ(G0 ) = ρ(G) + 1, ν(G0 ) = ν(G). Ch´u.ng minh. Theo c´ach xˆay du..ng, d¯a d¯`ˆo thi. G0 c´o n0 = n d¯ı˙’nh, m0 = m + 1 ca.nh v`a gia˙’ su˙’. `an liˆen thˆong. G0 c´o p0 th`anh phˆ Nˆe´u a ≡ b hoˇa.c c´o mˆo.t dˆay chuyˆ `en nˆo´i a v´o.i b. Khi d¯´o ph´ep biˆe´n d¯oˆ˙’i G th`anh G0 khˆong thay d¯ˆo˙’i sˆo´ th`anh phˆ u.c l`a p = p0 . Do d¯´o `an liˆen thˆong, t´ ρ(G0 ) = n0 − p0 = n − p = ρ(G), ν(G0 ) = m0 − ρ(G0 ) = ν(G) + 1. 49 http://www.ebook.edu.vn
Ngu.o..c la.i, nˆe´u a 6= b v`a khˆong tˆ `on ta.i dˆay chuyˆ `en nˆo´i a v`a b, th`ı do c´ach x´ac d¯i.nh G0 0 ta c´o p = p − 1. Suy ra ρ(G0 ) = n0 − p0 = n − (p − 1) = n − p + 1 = ρ(G) + 1, ν(G0 ) = m0 − ρ(G0 ) = (m + 1) − (ρ(G) + 1) = m − ρ(G) = ν(G). / e. qua˙’ 2.1.2 ρ(G) ≥ 0 v`a ν(G) ≥ 0. Hˆ Ch´ u.ng minh. Thˆa.t vˆa.y, xuˆa´t ph´at t` u. d¯`ˆo thi. th`anh lˆa.p bˇ`a ng c´ac d¯ı˙’nh cu˙’a d¯a d¯`oˆ thi. vˆo hu.´o.ng G, d¯ı˙’nh no. cˆo lˆa.p v´o.i d¯ı˙’nh kia, ta xˆay du..ng G0 dˆ `an dˆ`an t`u.ng ca.nh mˆo.t; kho˙’.i d¯`ˆau ta c´o ρ = 0, ν = 0; mˆo˜i khi thˆem mˆo.t ca.nh, th`ı hoˇa.c ρ tˇang v`a l´ uc d¯o´ ν khˆong d¯oˆ˙’i, hoˇa.c ν tˇang v`a l´ . . uc d¯o´ ρ khˆong d¯oˆ˙’i. Nhu vˆa.y, trong qu´a tr`ınh xˆay du. ng d¯`oˆ thi. G0 , c´ac sˆo´ ρ v`a ν chı˙’ c´o thˆe˙’ tˇang. / u.ng kˆe´t qua˙’ phong ph´ - ˆe˙’ c´o thˆe˙’ vˆa.n du.ng nh˜ D u.u, u cu˙’a d¯a.i sˆo´ vector trong viˆe.c nghiˆen c´ ngu.`o.i ta thu.`o.ng d¯aˇ. t tu.o.ng u ´.ng mˆo˜i chu tr`ınh trong G v´o.i mˆo.t vector theo c´ach sau d¯ˆay. Mˆo˜i ca.nh cu˙’a d¯a d¯`oˆ thi. G d¯`ˆeu d¯u.o..c d¯.inh hu.´o.ng mˆo.t c´ach t` ´; nˆe´u chu tr`ınh µ d¯i uy y . . `an thuˆa.n hu ´o ng v`a sk lˆ qua ca.nh ek , rk lˆ . . . . `an ngu o. c hu ´o ng th`ı ta d¯ˇa.t ck := rk − sk (nˆe´u ek l`a . . mˆo.t khuyˆen th`ı ta luˆon qui u ´o c sk = 0). Vector m chiˆ `eu (c1 , c2 , . . . , cm ) go.i l`a vector chu tr`ınh tu.o.ng u ´.ng v´o.i µ v`a k´ y hiˆe.u l`a ~µ (hay l`a µ nˆe´u khˆong thˆe˙’ gˆay ra nhˆ`am lˆa˜n). C´ac chu tr`ınh µ, µ0 , µ00 , . . . go.i l`a d¯ˆo.c lˆa.p nˆe´u c´ac vector chu tr`ınh tu.o.ng u ´.ng d¯ˆo.c lˆa.p tuyˆe´n t´ınh. Ch´ uy ´ rˇa` ng, d¯.inh ngh˜ıa n`ay khˆong phu. thuˆo.c v`ao hu.´o.ng g´an cho c´ac ca.nh. y 2.1.3 Chu sˆo´ ν(G) cu˙’ a G = (V, E) bˇ`a ng sˆo´ cu..c d¯a.i c´ac chu tr`ınh d¯ˆo.c lˆa.p. - .inh l´ D Ch´ u.ng minh. Tiˆe´n h`anh nhu. trong Hˆe. qua˙’ 2.1.2: d¯`ˆau tiˆen ta lˆa´y d¯`ˆo thi. vˆo hu.´o.ng khˆong c´o ca.nh v´o.i tˆa.p c´ac d¯ı˙’nh l`a V. Sau d¯´o ta xˆay du..ng d¯a d¯`ˆo thi. G0 bˇ`a ng c´ach thˆem t`u.ng ca.nh mˆo.t v`ao. Theo D - i.nh l´ . y 2.1.1, chu sˆo´ s˜e tˇang mˆo.t d¯o n vi. nˆe´u ca.nh thˆem v`ao lˆa.p ra c´ac chu tr`ınh m´o i, chu sˆo´ khˆong thay d¯oˆ˙’i trong tru.`o.ng ho..p ngu.o..c la.i. . Gia˙’ su˙’., tru.´o.c khi thˆem ca.nh ek ta d¯a˜ c´o mˆo.t co. so˙’. gˆ `om c´ac chu tr`ınh d¯ˆo.c lˆa.p: µ1 , µ2 , µ3 , . . . ; v`a sau khi thˆem ca.nh ek xuˆa´t hiˆe.n thˆem c´ac chu tr`ınh so. cˆa´p m´o.i γ1 , γ2 , . . . , n`ao d¯o´. Hiˆe˙’n nhiˆen γ1 khˆong thˆe˙’ biˆe˙’u diˆ˜en tuyˆe´n t´ınh qua hˆe. c´ac chu tr`ınh µj (v`ı c´ac vector 50 http://www.ebook.edu.vn
tu.o.ng u ´.ng c´ac chu tr`ınh µj c´o th`anh phˆ `an th´u. k bˇa` ng khˆong, trong khi vector tu.o.ng u ´.ng chu tr`ınh γ1 c´o th`anh phˆ `an th´ . u k kh´ac khˆong). Mˇa.t kh´ac c´ac vector γ2 , γ3 , . . . c´o thˆe˙’ biˆe˙’u diˆ˜en tuyˆe´n t´ınh qua γ1 , µ1 , µ2 , µ3 , . . . . T´om la.i mˆo˜i khi chu sˆo´ tˇang mˆo.t d¯o.n vi. th`ı sˆo´ cu..c d¯a.i c´ac chu tr`ınh d¯ˆo.c lˆa.p tuyˆe´n t´ınh c˜ ung tˇang lˆen mˆo.t d¯o.n vi.. D y d¯u.o..c ch´ - i.nh l´ u.ng minh. / u. kˆe´t qua˙’ n`ay, dˆ˜e d`ang suy ra: T` - a d¯`ˆo thi. vˆo hu.´o.ng G khˆong c´o chu tr`ınh nˆe´u v`a chı˙’ nˆe´u ν(G) = 0. e. qua˙’ 2.1.4 (a) D Hˆ - a d¯`ˆo thi. vˆo hu.´o.ng G c´o d¯u (b) D ´ng mˆo.t chu tr`ınh nˆe´u v`a chı˙’ nˆe´u ν(G) = 1. D- i.nh l´ y 2.1.5 Trong d¯`ˆo thi. c´o hu.´o.ng liˆen thˆong ma.nh, chu sˆo´ bˇa` ng sˆo´ cu..c d¯a.i c´ac ma.ch o.c lˆa.p tuyˆe´n t´ınh. d¯ˆ Ch´ u.ng minh. Thˆa.t vˆa.y, x´et d¯`ˆo thi. vˆo hu.´o.ng lˆa.p bo˙’.i c´ac cung kh´ac nhau cu˙’a G (mˆo˜i cung tu.o.ng u ´.ng mˆo.t cˇa.p ca.nh) v`a mˆo.t chu tr`ınh so. cˆa´p µ; ta phˆan hoa.ch tˆa.p c´ac d¯ı˙’nh trˆen chu tr`ınh n`ay th`anh: tˆa.p S c´ac d¯ı˙’nh c´o mˆo.t cung t´o.i n´o v`a mˆo.t cung ra kho˙’i n´o, tˆa.p S 0 c´ac d¯ı˙’nh c´o hai cung cu˙’a µ ra kho˙’i n´o v`a tˆa.p S 00 c´ac d¯ı˙’nh c´o hai cung cu˙’a µ d¯i t´o.i n´o. V`ı sˆo´ c´ac cung d¯i ra bˇa` ng sˆo´ c´ac cung d¯i t´o.i nˆen #S 0 = #S 00 ; gia˙’ su˙’. v10 , v20 , . . . , vk0 l`a c´ac phˆ `an tu˙’. cu˙’a S 0 v`a `an tu˙’. cu˙’a S 00 . v100 , v200 , . . . , vk00 l`a c´ac phˆ Trˆen chu tr`ınh µ, c´ac phˆ `an tu˙’. cu˙’a S 0 v`a cu˙’a S 00 xen k˜e nhau v`a ta gia˙’ su˙’. rˇ`a ng sau d¯ı˙’nh vi0 th`ı d¯ı˙’nh d¯`aˆu tiˆen bˇa´t gˇa.p (khˆong thuˆo.c S) l`a vi00 ; cuˆo´i c` ung, nˆe´u µ0 l`a mˆo.t d¯u.`o.ng d¯i gˇa.p d¯ı˙’nh x tru.´o.c d¯ı˙’nh y th`ı ta k´ y hiˆe.u µ0 [x, y] l`a d¯u.`o.ng d¯i bˆo. phˆa.n cu˙’a µ0 t` u. x d¯ˆe´n y. V`ı d¯`oˆ thi. liˆen thˆong ma.nh nˆen tˆ `on ta.i ma.ch µ1 d¯i qua vi+1 0 ung c´ac cung cu˙’a µ d¯ˆe˙’ d¯i t` v`a vi00 v`a d` u. 0 00 . vi+1 d¯ˆe´n vi . Chu tr`ınh µ l`a mˆo.t tˆo˙’ ho. p tuyˆe´n t´ınh cu˙’a c´ac ma.ch v`ı ta c´o thˆe˙’ viˆe´t µ = µ[v10 , v100 ] − µ1 [v20 , v100 ] + µ[v20 , v200 ] + · · · = µ[v10 , v100 ] + µ1 [v100 , v20 ] + µ[v20 , v200 ] + µ2 [v200 , v30 ] + · · · − (µ1 + µ2 + · · ·). Vˆa.y mo.i chu tr`ınh so. cˆa´p d¯`ˆeu l`a tˆo˙’ ho..p tuyˆe´n t´ınh cu˙’a c´ac ma.ch, d¯oˆ´i v´o.i c´ac chu tr`ınh bˆa´t k` `eu d¯´o c˜ y d¯iˆ ´ng (v`ı n´o l`a tˆo˙’ ho..p tuyˆe´n t´ınh cu˙’a c´ac chu tr`ınh so. cˆa´p). ung d¯u Trong Rm , c´ac ma.ch lˆa.p th`anh mˆo.t co. so˙’. cu˙’a khˆong gian vector con sinh bo˙’.i c´ac chu tr`ınh, v`a theo D - i.nh l´y 2.1.3 th`ı co. so˙’. n`ay c´o sˆo´ chiˆ `eu l`a ν(G). Vˆa.y sˆo´ cu..c d¯a.i c´ac ma.ch d¯ˆo.c lˆa.p tuyˆe´n t´ınh bˇa` ng ν(G). / 51 http://www.ebook.edu.vn
2.2 ´c sˆ Sˇ a o´ Gia˙’ su˙’. rˇ`a ng ch´ung ta c´o mˆo.t d¯`ˆo thi. vˆo hu.´o.ng G v´o.i n d¯ı˙’nh, v`a cˆ`an tˆo m`au c´ac d¯ı˙’nh sao cho hai d¯ı˙’nh kˆ `e nhau c´o m`au kh´ac nhau. Hiˆe˙’n nhiˆen l`a c´o thˆe˙’ d` ung n m`au d¯ˆe˙’ tˆo c´ac d¯ı˙’nh d¯o´, nhu.ng nhu. thˆe´ vˆa´n d¯`ˆe d¯aˇ. t ra la.i khˆong mang t´ınh thu..c tiˆ˜en. Thˆe´ th`ı sˆo´ m`au tˆo´i thiˆe˙’u d¯o`i ho˙’i l`a bao nhiˆeu? D- ˆay ch´ınh l`a b`ai to´an tˆo m`au. Khi c´ac d¯ı˙’nh d¯u.o..c tˆo, ch´ ung ta c´o thˆe˙’ nh´om ch´ ung v`ao c´ac tˆa.p kh´ac nhau-mˆo.t tˆa.p gˆ . . `om c´ac d¯ı˙’nh d¯u o. c tˆo m`au d¯o˙’, mˆo.t tˆa.p c´ac . . - d¯ı˙’nh d¯u o. c tˆo m`au xanh, vˆan vˆan. Dˆay ch´ınh l`a b`ai to´an phˆan hoa.ch. B`ai to´an tˆo m`au v`a phˆan hoa.ch d˜ı nhiˆen c´o thˆe˙’ x´et trˆen c´ac ca.nh cu˙’a d¯`ˆo thi.. Trong tru.`o.ng ho..p d¯`oˆ thi. phˇa˙’ng thˆa.m ch´ı c´o thˆe˙’ quan tˆam d¯ˆe´n viˆe.c tˆo m`au c´ac diˆe.n. `an n`ay ta chı˙’ x´et c´ac d¯`oˆ thi. vˆo hu.´o.ng liˆen thˆong. Trong phˆ - i.nh ngh˜ıa 2.2.1 Cho tru.´o.c mˆo.t sˆo´ nguyˆen p, ta n´oi rˇ`a ng d¯`oˆ thi. G l`a p−sˇa´c nˆe´u bˇ`a ng p D m`au kh´ac nhau ta c´o thˆe˙’ tˆo m`au c´ac d¯ı˙’nh, sao cho hai d¯ı˙’nh kˆ `e nhau khˆong c` ung mˆo.t m`au. . Sˆo´ p nho˙’ nhˆa´t, m`a d¯oˆ´i v´o i sˆo´ d¯o´ G l`a p−sˇa´c go.i l`a sˇa´c sˆo´ cu˙’a d¯`ˆo thi. G v`a k´ y hiˆe.u l`a γ(G). V´ı du. 2.2.2 H`ınh 2.1 minh ho.a ba c´ach tˆo m`au kh´ac nhau cu˙’a d¯`oˆ thi.. Dˆ˜e d`ang kiˆe˙’m tra rˇa` ng d¯`oˆ thi. n`ay l`a 2−sˇa´c. •....... r •....... r •....... r ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. .. .. .. .. . •b . ............. . ... ... ....... .. .. .. .•b ............. . ... ... ....... . .. .. . . . •b. ............. . ... ... ....... .. . ... ... ...... . ... ... ...... . ... ... ...... .... .... .... .... . . .. .... .... ... .... .... ... .... .... ... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ... .... .... ... .... .... ... .... . ...... . . .... .... . ...... . . .... .... . ...... . . .... .... g•....... ..... . .... .... . . . ... .... •y .... .... .. .... g• ....... .. .... .... . . . ... .... •y .... ... .... ... r• . ....... .... . .... . . . ... .... •r .... ... .... ... .... . . ...... . .... .... . . ...... . .... .... . . ...... . .... .. .... .... .. ... . .... .. .... .... . . ... . .... . . . ... .... . . ... . .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ....... .... .... ....... .... .... ....... .... .. .... .... .. .... .... .. .... .... . .... .... . .... .... . .... .... .. .... .... .. .... .... .. .... • ........ .. • ........ .. • ........ .. p r b (a) (b) (c) H`ınh 2.1: V´ı du. 2.2.3 Ba˙’n d¯`oˆ d¯.ia l´ y. Ta v˜e trˆen mˇa.t phˇa˙’ng mˆo.t ba˙’n d¯`ˆo. Go.i V l`a tˆa.p ho..p c´ac nu ´o c, d¯ˇa.t (i, j) ∈ E nˆe´u c´ac nu.´o.c i v`a j c´o biˆen gi´o.i chung. D . . u.ng - `ˆo thi. G = (V, E) d¯ˆo´i x´ v`a c´o t´ınh chˆa´t rˆa´t d¯aˇ. c biˆe.t l`a: c´o thˆe˙’ v˜e n´o lˆen mˇa.t phˇa˙’ng m`a khˆong c´o hai ca.nh n`ao cˇa´t nhau (tr` u. ta.i c´ac d¯ı˙’nh chung); n´oi c´ach kh´ac, G l`a d¯`ˆo thi. phˇa˙’ng. Ngu.`o.i ta d¯a˜ biˆe´t rˇ`a ng sˇa´c sˆo´ cu˙’a mo.i d¯`oˆ thi. phˇa˙’ng d¯`ˆeu nho˙’ ho.n hoˇa.c bˇ`a ng bˆo´n (D - i.nh l´y 6.4.7). Nhu. vˆa.y bˇ`a ng bˆo´n m`au c˜ ung d¯u˙’ d¯ˆe˙’ tˆo m`au ba˙’n d¯`oˆ phˇa˙’ng sao cho hai nu.´o.c kˆ `e nhau khˆong c` ung mˆo.t m`au. 52 http://www.ebook.edu.vn
u. d¯.inh ngh˜ıa dˆ˜e d`ang suy ra T` 1. Mˆo.t d¯`ˆo thi. chı˙’ c´o c´ac d¯ı˙’nh cˆo lˆa.p l`a 1−sˇa´c. 2. Mˆo.t d¯`oˆ thi. c´o mˆo.t hoˇa.c hai ca.nh (khˆong pha˙’i l`a mˆo.t khuyˆen) c´o sˇa´c sˆo´ ´ıt nhˆa´t bˇa` ng hai. - `ˆo thi. d¯`aˆy d¯u˙’ n d¯ı˙’nh Kn l`a n−sˇa´c. 3. D - `ˆo thi. l`a mˆo.t chu tr`ınh d¯o.n gia˙’n v´o.i n d¯ı˙’nh, n > 3, l`a 2−sˇa´c nˆe´u n chˇa˜n v`a 3−sˇa´c 4. D nˆe´u n le˙’. 5. Hiˆe˙’n nhiˆen, mo.i d¯`oˆ thi. 2−sˇa´c l`a hai phˆ `an do ch´ung ta c´o thˆe˙’ phˆan hoa.ch tˆa.p c´ac d¯ı˙’nh V th`anh hai tˆa.p con theo m`au d¯u o. c tˆo trˆen c´ac d¯ı˙’nh. Tu.o.ng tu.., d¯`ˆo thi. hai phˆ . . `an l`a . . . . 2−sˇa´c, v´o i mˆo.t tru `o ng ho. p ngoa.i lˆe. tˆ . . `am thu `o ng: d¯`oˆ thi. c´o ´ıt nhˆa´t hai d¯ı˙’nh cˆo lˆa.p v`a khˆong c´o ca.nh l`a hai phˆ . `an nhu ng l`a 1−sˇa´c. - i.nh ngh˜ıa 2.2.4 Ta go.i sˇa´c l´o.p cu˙’a d¯`ˆo thi. G l`a sˆo´ nguyˆen q c´o c´ac t´ınh chˆa´t sau: D 1. C´o thˆe˙’ d` ung q m`au kh´ac nhau d¯ˆe˙’ tˆo m`au c´ac ca.nh cu˙’a G sao cho hai ca.nh kˆ `e nhau khˆong c` ung mˆo.t m`au; `eu n`ay khˆong thˆe˙’ l`am d¯u.o..c v´o.i (q − 1) m`au. - iˆ 2. D Nhˆa.n x´et rˇa` ng sˇa´c l´o.p cu˙’a d¯`ˆo thi. G = (V, E) ch´ınh l`a sˇa´c sˆo´ cu˙’a d¯`oˆ thi. G0 = (V 0 , E 0 ) d¯u.o..c x´ac d¯.inh nhu. sau: mˆo˜i d¯ı˙’nh cu˙’a G0 tu.o.ng u ´.ng mˆo.t ca.nh cu˙’a G; ca.nh e0 = (v10 , v20 ) ∈ E 0 . nˆe´u c´ac ca.nh e1 v`a e2 (tu o ng u . . . `e nhau. ´ ng v´o i hai d¯ı˙’nh v10 , v20 ) kˆ Nhu. vˆa.y b`ai to´an sˇa´c l´o.p d¯u.a vˆ `e b`ai to´an sˇa´c sˆo´. Du.´o.i d¯aˆy l`a mˆo.t v`ai kˆe´t qua˙’ co. ba˙’n `e sˇa´c sˆo´. vˆ - i.nh l´ D - `ˆo thi. vˆo hu.´o.ng G l`a 2−sˇa´c nˆe´u v`a chı˙’ nˆe´u n´o khˆong c´o chu tr`ınh y 2.2.5 [K¨onig] D o. d`ai le˙’ . c´o d¯ˆ Ch´ u.ng minh D - iˆ `eu kiˆe.n cˆ `an. Nˆe´u d¯`ˆo thi. G l`a 2−sˇa´c, th`ı tˆa´t nhiˆen G khˆong ch´ u.a chu . tr`ınh c´o d¯oˆ. d`ai le˙’, v`ı c´ac d¯ı˙’nh cu˙’a mˆo.t chu tr`ınh loa.i nhu vˆa.y khˆong thˆe˙’ tˆo bˇ`a ng hai m`au theo nhu. quy tˇa´c d¯a˜ chı˙’ ra o˙’. trˆen. `eu kiˆe.n d¯u˙’. Gia˙’ su˙’. d¯`oˆ thi. G khˆong c´o chu tr`ınh c´o d¯ˆo. d`ai le˙’, ta ch´ - iˆ D u.ng minh n´o l`a 2−sˇa´c. Khˆong gia˙’m tˆo˙’ng qu´at coi G l`a liˆen thˆong. Ta s˜e tˆo m`au dˆ `an c´ac d¯ı˙’nh cu˙’a G theo quy tˇa´c sau: 53 http://www.ebook.edu.vn
• tˆo m`au xanh cho mˆo.t d¯ı˙’nh a n`ao d¯o´; • nˆe´u mˆo.t d¯ı˙’nh x n`ao d¯´o d¯a˜ d¯u.o..c tˆo xanh, th`ı ta tˆo d¯o˙’ tˆa´t ca˙’ c´ac d¯ı˙’nh kˆ `e v´o.i n´o; nˆe´u d¯ı˙’nh y d¯˜a d¯u.o..c tˆo d¯o˙’, th`ı ta tˆo xanh tˆa´t ca˙’ c´ac d¯ı˙’nh kˆ `e v´o.i y. V`ı d¯`oˆ thi. G liˆen thˆong, nˆen s´o.m hay muˆo.n th`ı mo.i d¯ı˙’nh cu˙’a n´o d¯`ˆeu d¯u.o..c tˆo m`au hˆe´t, v`a mˆo.t d¯ı˙’nh x khˆong thˆe˙’ c` ung mˆo.t l´ uc d¯u.o..c tˆo xanh v`a tˆo d¯o˙’, v`ı nhu. vˆa.y th`ı x v`a a s˜e c` ung nˇa` m trˆen mˆo.t chu tr`ınh c´o d¯oˆ. d`ai le˙’. Vˆa.y d¯`ˆo thi. G l`a 2−sˇa´c. / Ch´uy´ rˇa` ng t´ınh chˆa´t d¯`ˆo thi. G khˆong c´o chu tr`ınh v´o.i d¯oˆ. d`ai le˙’ tu.o.ng d¯u.o.ng v´o.i t´ınh chˆa´t G khˆong c´o chu tr`ınh so. cˆa´p v´o.i d¯oˆ. d`ai le˙’. Thˆa.t vˆa.y gia˙’ su˙’. c´o mˆo.t chu tr`ınh µ = {v0 , v1 , . . . , vp = v0 } c´o d¯ˆo. d`ai p le˙’. Mˆo˜i khi gˇa.p hai d¯ı˙’nh vj v`a vk v´o.i j < k < p v`a vj = vk , ta phˆan chia µ th`anh hai chu tr`ınh bˆo. phˆa.n µ1 = {vj , . . . , vk } v`a µ2 = {v0 , . . . , vj , vk , . . . , v0 }; ho.n n˜u.a mˆo.t trong . hai chu tr`ınh c´o d¯oˆ. d`ai le˙’ (v`ı nˆe´u khˆong nhu thˆe´ th`ı µ s˜e c´o d¯ˆo. d`ai chˇa˜n). Ta thˆa´y rˇ`a ng nˆe´u tiˆe´p tu.c phˆan chia chu tr`ınh µ theo c´ach d¯o´ cho d¯ˆe´n khi c`on c´o thˆe˙’ l`am d¯u.o..c, th`ı mˆo˜i lˆ `an ˜ . . ˙’ ´ vˆan c`on d¯u o. c mˆo.t chu tr`ınh c´o d¯oˆ. d`ai le; v`ı cuˆoi c` ` . ´ ung mo.i chu tr`ınh d¯ˆeu l`a so cˆa p, nˆen xa˙’y ra mˆau thuˆa˜n; v`a ta c´o d¯iˆ `eu cˆ `an ch´ . u ng minh. - .inh l´ D y sau d¯aˆy cho ta biˆe´t cˆa.n trˆen cu˙’a sˇa´c sˆo´. y 2.2.6 K´y hiˆe.u dmax l`a bˆa.c cu..c d¯a.i cu˙’ a c´ac d¯ı˙’nh trong G. Khi d¯´o - i.nh l´ D γ(G) ≤ 1 + dmax . u.ng minh. B`ai tˆa.p. Ch´ / u.ng minh rˇ`a ng nˆe´u G l`a d¯`oˆ thi. khˆong d¯`ˆay d¯u˙’, c´o dmax d¯ı˙’nh th`ı Brooks [9] d¯˜a ch´ γ(G) ≤ dmax . 2.2.1 C´ ´c sˆ ach t`ım sˇ a o´ X´et d¯`ˆo thi. G = (V, Γ) c´o n d¯ı˙’nh v`a m ca.nh; muˆo´n t`ım sˇa´c sˆo´ cu˙’a n´o ta c´o thˆe˙’ d` ung mˆo.t . . . ´ . . ´ . . . phu o ng ph´ap thu. c nghiˆe.m rˆa t d¯o n gia˙’n, ´ap du.ng tru. c tiˆep d¯u o. c, nhu ng khˆong pha˙’i l´ uc n`ao ung phu.o.ng ph´ap gia˙’i t´ıch, n´o cho ta mˆo.t l`o.i gia˙’i hˆe. thˆo´ng, ung c´o hiˆe.u qua˙’ hoˇa.c c´o thˆe˙’ d` c˜ nhu.ng n´oi chung cˆ `an m´ay t´ınh d¯iˆe.n tu˙’.. 54 http://www.ebook.edu.vn
Phu.o.ng ph´ ap thu..c nghiˆ e.m Bˇ`a ng c´ach tˆo m`au t` uy y ´ d`ung c´ac m`au 1, 2, . . . , p v`a t`ım c´ach loa.i dˆ `an mˆo.t m`au n`ao d¯o´ (go.i l`a “m`au t´o i ha.n”) trong c´ac m`au ˆa´y. Muˆo´n vˆa.y, ta x´et d¯ı˙’nh v c´o m`au t´o.i ha.n d¯o´ v`a c´ac . th`anh phˆ `an liˆen thˆong C1jk , C2jk , . . . cu˙’a d¯`oˆ thi. con sinh ra bo˙’.i hai m`au khˆong t´o.i ha.n j v`a u.c thay m`au cu˙’a d¯ı˙’nh v nˆe´u c´ac tˆa.p ho..p C1jk ∩ Γ(v), C2jk ∩ Γ(v), . . . khˆong k. Ta c´o thˆe˙’ lˆa.p t´ pha˙’i l`a hai m`au: lˆa´y riˆeng r˜e mˆo˜i th`anh phˆ `an C jk m`a v´o.i th`anh phˆ `an d¯o´ th`ı c´ac d¯ı˙’nh cu˙’a jk C ∩ Γ(v) c´o m`au j, ho´an vi. trong c´ac th`anh phˆ `an d¯´o c´ac m`au j v`a k (khˆong thay d¯oˆ˙’i m`au cu˙’a c´ac d¯ı˙’nh kh´ac), cuˆo´i c` ung tˆo d¯ı˙’nh v m`au j (l´ uc n`ay d¯ı˙’nh v khˆong kˆ `e v´o.i d¯ı˙’nh n`ao c´o m`au j). Phu.o.ng ph´ ap gia˙’ i t´ıch Kiˆe˙’m tra bˇ`a ng c´ach gia˙’i t´ıch xem d¯`oˆ thi. G c´o thˆe˙’ d¯u.o..c tˆo bˇ`a ng p m`au d¯u.o..c khˆong. Phu.o.ng ph´ap d¯o´ nhu. sau: V´o.i mˆo˜i c´ach tˆo bˇa` ng p m`au, ta cho tu.o.ng u ´.ng v´o.i mˆo.t hˆe. thˆo´ng c´ac sˆo´ xij , i = 1, 2, . . . , n; j = 1, 2, . . . , p, d¯u.o..c x´ac d¯.inh nhu. sau: ( 1 nˆe´u d¯ı˙’nh i c´o m`au j, xij = 0 trong tru.`o.ng ho..p ngu.o..c la.i. - ˇa.t D ( 1 nˆe´u ca.nh ej liˆen thuˆo.c d¯ı˙’nh vi , rij = 0 trong tru.`o.ng ho..p ngu.o..c la.i. uc d¯´o b`ai to´an tro˙’. th`anh t`ım c´ac sˆo´ nguyˆen xij sao cho: L´   x  Pijp ≥ 0,  q=1 xiq ≤ 1, i = 1, 2, . . . , n,  Pn k=1 rjk xkq ≤ 1, j = 1, 2, . . . , m; q = 1, 2, . . . , p. u.c tuyˆe´n t´ınh. Dˆ˜e r`ang thˆa´y rˇ`a ng hˆe. d¯´o th´ıch ho..p v´o.i c´ac phu.o.ng Ta c´o hˆe. bˆa´t d¯ˇa˙’ng th´ . . ph´ap thˆong thu `o ng cu˙’a quy hoa.ch nguyˆen v`a do d¯o´ c´o thˆe˙’ d` ung phu.o.ng ph´ap cu˙’a Gomory (du..a trˆen phu.o.ng ph´ap d¯o.n h`ınh cu˙’a Dantzig) d¯ˆe˙’ gia˙’i. 2.3 Sˆ o˙’n d o´ ˆ ¯i.nh trong V´o.i d¯`ˆo thi. G = (V, Γ) cho tru.´o.c ta thu.`o.ng quan tˆam d¯ˆe´n tˆa.p con cu˙’a V c´o nh˜ u.ng t´ınh chˆa´t `an tu˙’. l´o.n nhˆa´t sao cho d¯`ˆo thi. con sinh n`ao d¯o´. Chˇa˙’ng ha.n, t`ım mˆo.t tˆa.p con S ⊂ V c´o sˆo´ phˆ 55 http://www.ebook.edu.vn
bo˙’.i S l`a d¯`ˆay d¯u˙’? Hoˇa.c t`ım tˆa.p con c´ac d¯ı˙’nh cu˙’a d¯`ˆo thi. G c´o sˆo´ phˆ `an tu˙’. nhiˆ `eu nhˆa´t sao cho hai d¯ı˙’nh trong d¯´o khˆong kˆ `e nhau. Mˆo.t b`ai to´an kh´ac l`a t`ım tˆa.p con S cu˙’a V c´o sˆo´ phˆ `an tu˙’. ´ıt nhˆa´t sao cho mo.i d¯ı˙’nh thuˆo.c V \ S kˆ `e v´o.i mˆo.t d¯ı˙’nh trong S. C´ac sˆo´ v`a c´ac tˆa.p con tu.o.ng u ´.ng l`o.i gia˙’i c´ac b`ai to´an trˆen cho nh˜u.ng t´ınh chˆa´t quan trong cu˙’a d¯`ˆo thi. v`a c´o nhiˆ `eu u. . ´ ng du.ng tru. c tiˆe´p trong b`ai to´an lˆa.p li.ch, phˆan t´ıch cluster, . phˆan loa.i sˆo´, xu˙’ l´ y song song trˆen m´ay t´ınh, vi. tr´ı thuˆa.n lo..i v`a thay thˆe´ c´ac th`anh phˆ `an . d¯iˆe.n tu˙’ , v.v. D- i.nh ngh˜ıa 2.3.1 X´et d¯`oˆ thi. vˆo hu.´o.ng G := (V, Γ); tˆa.p ho..p S ⊂ V d¯u.o..c go.i l`a tˆa.p ho..p ˆo˙’n d¯.inh trong nˆe´u hai d¯ı˙’nh bˆa´t k` `e nhau; n´oi c´ach kh´ac, v´o.i mo.i cˇa.p y cu˙’a S d¯`ˆeu khˆong kˆ d¯ı˙’nh a, b ∈ S th`ı b ∈/ Γ(a). y hiˆe.u S l`a ho. c´ac tˆa.p ˆo˙’n d¯.inh trong cu˙’a d¯`oˆ thi. G. Khi d¯´o K´ 1. Tˆa.p trˆo´ng ∅ thuˆo.c S. 2. Nˆe´u S ∈ S v`a A ⊂ S th`ı A ∈ S. N´oi c´ach kh´ac, tˆa.p con cu˙’a mˆo.t tˆa.p ˆo˙’n d¯.inh trong ung l`a mˆo.t tˆa.p ˆo˙’n d¯.inh trong. c˜ Tˆa.p ˆo˙’n d¯.inh trong l`a cu..c d¯a.i nˆe´u thˆem mˆo.t d¯ı˙’nh bˆa´t k` y v`ao n´o th`ı s˜e khˆong c`on ˆo˙’n d¯.inh trong n˜ . u a. D . . - a.i lu o. ng α(G) := max{#S | S ∈ S} d¯u.o..c go.i l`a sˆo´ ˆo˙’n d¯.inh trong cu˙’a G. V´ı du. 2.3.2 X´et d¯`oˆ thi. trong H`ınh 2.2. Tˆa.p c´ac d¯ı˙’nh {v7 , v8 , v2 } l`a ˆo˙’n d¯.inh trong nhu.ng khˆong cu..c d¯a.i; tˆa.p {v7 , v8 , v2 , v5 } l`a ˆo˙’n d¯i.nh trong cu..c d¯a.i. C´ac tˆa.p {v1 , v3 , v7 } v`a {v4 , v6 } ung l`a tˆa.p ˆo˙’n d¯.inh trong cu..c d¯a.i v`a do d¯´o, n´oi chung c´o thˆe˙’ c´o nhiˆ c˜ `eu tˆa.p ˆo˙’n d¯.inh trong . ˙ ’ . cu. c d¯a.i. Ho. c´ac tˆa.p ˆo n d¯.inh trong cu. c d¯a.i cu˙’a d¯`oˆ thi. n`ay l`a {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`ai to´an t´am con hˆa.u. Trˆen b`an c`o. c´o thˆe˙’ bˆo´ tr´ı t´am con hˆa.u, sao cho khˆong c´o con n`ao ch´em d¯u.o..c con n`ao khˆong? B`ai to´an nˆo˙’i tiˆe´ng n`ay d¯u.a vˆ `e t`ım mˆo.t tˆa.p ho. p ˆo n d¯.inh trong cu. c d¯a.i cu˙’a d¯oˆ thi. vˆo hu ´o ng c´o 64 d¯ı˙’nh (l`a c´ac ˆo trˆen b`an c`o.), trong . ˙ ’ . ` . . d¯o´ y ∈ Γ(x) nˆe´u c´ac ˆo x v`a y nˇ`a m trˆen c` ung mˆo.t h`ang, mˆo.t cˆo.t hay mˆo.t d¯u.`o.ng ch´eo. Thu..c tˆe´, kh´o khˇan la.i l´o.n ho.n l`a khi ngu.`o.i ta m´o.i thoa.t nh`ın: l´ uc d¯`aˆu Gauss tu.o˙’.ng c´o 76 l`o.i 56 http://www.ebook.edu.vn
v1 v2 v3 •..............................................................................................................................................•.......................................................................................................................•...................... ..... ......... ..... ... ..... ..... ......... ..... ... ..... ..... ......... ..... ... ..... ..... ......... ..... ..... ..... ......... ..... ... ..... ..... ......... ..... ... ..... ......... ..... ......... . .. ..... . . ..... ..... ......... . ... ..... ..... ........... ...... ... ..... ..... ......... . ..... ... ..... ..... ......... . . ..... ..... .......... . ..... ... ..... ..... ... .. .... .. . ... ..... •................................................................................................................................. .. . .. .. ...... . .. • v6 ... . ... .... • v4. ....... ................. v8 .... ... . ..... . . . ..... .. ..... ..... ... ... ......... . ...... . . .. ... . . . . ..... ......... .... ... ..... ..... .......... ..... ..... ..... ................. .... .... ....... . .. ............ . . ... . . ....... . ... ...... .... ......... ... ..... . .... ......... ..... ... ..... ..... ......... ..... ..... .... ........ ..... ......... ....... ................. ..... .. ..... ...... .. .... . . . ... ..... .......... ............ ............ • .. • v7 v5 H`ınh 2.2: gia˙’i, c`on t`o. b´ao vˆ `e c`o. o˙’. Berlin“Schachzeitung” nˇam 1854 chı˙’ m´o.i d¯u.a ra 40 l`o.i gia˙’i thˆe´ c`o. do c´ac nh`a ham c`o. t`ım ra. Su.. thˆa.t th`ı c´o 92 l`o.i gia˙’i nhu. 12 so. d¯`oˆ du.´o.i d¯ˆay: (72631485) (61528374) (58417263) (35841726) (46152837) (57263148) (16837425) (57263184) (48157263) (51468273) (42751863) (35281746) Mˆo˜i so. d¯`oˆ trˆen tu.o.ng u ´.ng v´o.i mˆo.t ho´an vi., v`a t` u. mˆo.t so. d¯`ˆo ta suy ra t´am l`o.i gia˙’i kh´ac nhau: ba l`o.i gia˙’i bˇ`a ng c´ach quay 900 , 1800 v`a 2700 ; c´ac l`o.i gia˙’i kh´ac suy ra bˇ`a ng c´ach d¯ˆo´i x´u.ng mˆo˜i so. d¯`oˆ nhˆa.n d¯u.o..c qua d¯u.`o.ng ch´eo ch´ınh; ho´an vi. cuˆo´i c` ung (35281746) chı˙’ c´o bˆo´n . . . . l`o i gia˙’i v`ı so d¯`oˆ tu o ng u. . ung v´o i ch´ınh n´o sau khi quay 1800 . ´ ng s˜e tr` V´ı du. 2.3.4 B`e cu˙’a mˆo.t d¯`ˆo thi. G l`a tˆa.p ho..p C ⊂ V sao cho a ∈ C, b ∈ C suy ra b ∈ Γ(a). Nˆe´u V l`a mˆo.t tˆa.p ho..p ngu.`o.i, v`a b ∈ Γ(a) chı˙’ su.. d¯`ˆong t`ınh gi˜ u.a a v`a b, th`ı thu.`o.ng yˆeu cˆ `au . . . t`ım b`e cu. c d¯a.i, ngh˜ıa l`a hˆo.i c´o sˆo´ ngu `o i tham gia nhiˆ `eu nhˆa´t. X´et d¯`oˆ thi. G := (V, Γ ) x´ac 0 0 d¯.inh nhu. sau: b ∈ Γ(a0 ) nˆe´u v`a chı˙’ nˆe´u b ∈ / Γ(a). B`ai to´an quy vˆ `e t`ım mˆo.t tˆa.p ho..p ˆo˙’n d¯.inh trong cu..c d¯a.i cu˙’a d¯`ˆo thi. (V, Γ0 ). V´ı du. 2.3.5 B`ai to´an vˆ `e c´ac cˆo g´ai l`a d¯oˆ´i tu.o..ng cu˙’a nhiˆ `eu cˆong tr`ınh to´an ho.c, c´o thˆe˙’ ph´at . biˆe˙’u nhu sau: mˆo.t k´ y t´ . . uc x´a nuˆoi du ˜o ng 15 cˆo g´ai, k´ y hiˆe.u l`a a, b, c, d, e, f, g, h, i, j, k, l, m, n, o; . h`ang ng`ay c´ac cˆo d¯i da.o cho i th`anh t` u ng bˆo. ba, c´o thˆe˙’ d¯u.a c´ac cˆo d¯i cho.i trong ba˙’y ng`ay . `en sao cho khˆong c´o hai cˆo n`ao c` liˆ ung d¯i trong mˆo.t bˆo. ba qu´a mˆo.t lˆ `an d¯u.o..c khˆong? V´o.i nh˜ u.ng nhˆa.n x´et vˆ u.ng, Cayley d¯a˜ t`ım ra l`o.i gia˙’i nhu. sau: `e d¯ˆo´i x´ 57 http://www.ebook.edu.vn
Chu˙’ Nhˆa.t u. Hai Th´ u. Ba Th´ u. Tu. Th´ u. Nˇam Th´ u. S´au Th´ u. Ba˙’y Th´ 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`ai to´an vˆ ung loa.i v´o.i mˆo.t b`ai to´an th´ `e c´ac cˆo g´ai c` u. hai c˜ung nˆo˙’i tiˆe´ng go.i l`a b`ai . . to´an bˆo˙’ tro. : v´o i 15 cˆo g´ai c´o thˆe˙’ lˆ . . `an lu o. t lˆa.p 35 bˆo. ba kh´ac nhau sao cho khˆong c´o hai cˆo n`ao c`ung trong mˆo.t bˆo. ba qu´a mˆo.t lˆ `an khˆong? D - ˆe˙’ gia˙’i b`ai to´an bˆo˙’ tro.., chı˙’ cˆ `an lˆa.p d¯`oˆ thi. ˙ ’ . . G c´o c´ac d¯ı˙’nh l`a 455 bˆo. ba c´o thˆe c´o, hai bˆo. ba d¯u o. c xem l`a kˆ `e nhau nˆe´u ch´ ung c´o chung hai cˆo g´ai: khi d¯o´ cˆ `an t`ım mˆo.t tˆa.p ho..p ˆo˙’n d¯.inh trong cu..c d¯a.i. Ta c´o α(G) ≤ 35 v`ı mˆo.t cˆo g´ai chı˙’ c´o mˇa.t nhiˆ`eu nhˆa´t l`a trong 7 bˆo. ba kh´ac nhau, nˆen tˆa´t ca˙’ c´o 15 × 7 × 31 = 35 bˆo. l`a nhiˆ`eu nhˆa´t; v`ı vˆa.y mo.i tˆa.p ho..p ˆo˙’n d¯.inh trong c´o 35 bˆo. ba d¯`ˆeu l`a cu..c d¯a.i. D- ˆe˙’ x´et xem mˆo.t l`o.i gia˙’i n`ao d¯´o cu˙’a b`ai to´an bˆo˙’ tro.. c´o cho l`o.i gia˙’i cu˙’a b`ai to´an vˆ `e c´ac cˆo g´ai khˆong, ta lˆa.p d¯`oˆ thi. G c´o c´ac d¯ı˙’nh l`a 35 bˆo. ba cho nghiˆe.m cu˙’a b`ai to´an bˆo tro.., hai 0 ˙ ’ bˆo. ba d¯u.o..c xem l`a kˆ `e nhau nˆe´u c´o chung mˆo.t cˆo g´ai; nˆe´u sˇa´c sˆo´ γ(G0 ) > 7 th`ı pha˙’i cho.n tˆa.p ho..p kh´ac gˆ `om c´ac bˆo. ba cho nghiˆe.m cu˙’a b`ai to´an bˆo˙’ tro... Dˆ˜e d`ang kiˆe˙’m tra rˇa` ng tˆ `on ta.i nh˜ . . ˙’ ˙’ ˙ ’ . ˜ ´ . ˙ ’ ˙ ’ ` u ng l`o i giai cua b`ai to´an bˆo tro. khˆong dˆan d¯ˆen l`o i giai cua b`ai to´an vˆe c´ac cˆo g´ai. Nhˆ et 2.3.6 (a) Sˇa´c sˆo´ γ(G) v`a sˆo´ ˆo˙’n d¯i.nh trong α(G) liˆen hˆe. v´o.i nhau bˇa` ng bˆa´t d¯ˇa˙’ng a.n x´ u.c th´ γ(G) × α(G) ≥ n. Thˆa.t vˆa.y, c´o thˆe˙’ phˆan hoa.ch V th`anh γ := γ(G) tˆa.p ho..p ˆo˙’n d¯.inh trong, lˆa.p bo˙’.i c´ac ung m`au v`a tu.o.ng u d¯ı˙’nh c` ´.ng ch´ u.a n1 , n2 , . . . , nγ d¯ı˙’nh. Vˆa.y ta c´o n = n1 + n2 + · · · + nγ ≤ α(G) + α(G) + · · · + α(G) = γ(G).α(G). (b) Ta c´o thˆe˙’ ho˙’i: pha˙’i chˇang mˆo´i liˆen hˆe. gi˜ u.a hai kh´ai niˆe.m l`a chu.a chˇa.t ch˜e. Pha˙’i chˇang c´o thˆe˙’ t`ım sˇa´c sˆo´ bˇ`a ng c´ach: tru.´o.c hˆe´t d`ung m`au (1) d¯ˆe˙’ tˆo tˆa.p ˆo˙’n d¯i.nh trong cu..c d¯a.i S1 . Rˆ`oi d`ung m`au (2) d¯ˆe˙’ tˆo tˆa.p ˆo˙’n d¯.inh trong cu..c d¯a.i S2 cu˙’a d¯`oˆ thi. con sinh ra bo˙’.i c´ac d¯ı˙’nh cu˙’a V \ S1 , sau d´o d` ung m`au (3) d¯ˆe˙’ tˆo tˆa.p ho..p ˆo˙’n d¯.inh trong cu..c d¯a.i cu˙’a d¯`ˆo thi. con c`on la.i, v.v. Thu..c ra khˆong pha˙’i nhu. vˆa.y. D - `ˆo thi. trˆen H`ınh 2.3 (c´o sˇa´c sˆo´ bˇa` ng 4) ch´ u.ng to˙’ d¯iˆ `eu 58 http://www.ebook.edu.vn
`e v´o.i c´ac d¯ı˙’nh a, b, c v`a d lˆa.p th`anh tˆa.p ˆo˙’n d¯.inh trong cu..c d¯a.i duy nhˆa´t, nˆe´u d¯o´: c´ac d¯ı˙’nh kˆ ta tˆo ch´ ung c` ung mˆo.t m`au th`ı ta pha˙’i d` ung ba m`au chı˙’ d¯ˆe˙’ tˆo c´ac d¯ı˙’nh a, b, c, d, nhu.ng r˜o `eu d¯´o khˆong thˆe˙’ l`am d¯u.o..c. r`ang d¯iˆ ..... .. .... ..... .. ..... ..... .. ..... • ........................................... . ... .......... ...... ........ ... .............. . .. . ... .. ... . ... . b . . . ... .... ..... ... ... ... ... ... ... ... ... ... ... . . . ... . ... . . . ... . ... . . . ... ... ... . .. . . ... ... . . ... . ... .. . . . . . ... ... ... ..... .. ..... . . .. . ..... .. ..... .. ... ... . ... . . ... . . . . ... . . • .. . . . .......................................... ....... ... .............. ........... ... ................ ... ... ... . . .. .. . ...... ... .. .... . .... . ... . . .. ... . ........... . .. ... c ... ...... .. ....... . .. ... ... ... ... ... ........ . ...... . .. ... .. ..... ...... . ..... .. .................. .. .. .. ........ ....... . . ..... .. ............. .. .................. ... ......... ..... ............... .............. .... .. • .. ... . . .... ..... .... ......... . . • . .. .......................................................................................................................................................................................................................... . . ..... .. ..... ..... .. ..... ..... .. ..... ..... .. ..... a d H`ınh 2.3: V´ı du. 2.3.7 [Shannon] B`ai to´an vˆ `e dung lu.o..ng thˆong tin cu˙’a mˆo.t tˆa.p ho..p t´ın hiˆe.u. X´et tru.`o.ng ho..p rˆa´t d¯o.n gia˙’n l`a m´ay ph´at c´o thˆe˙’ truyˆ `en d¯i nˇam t´ın hiˆe.u: a, b, c, d, e; o˙’. m´ay thu, mˆo˜i t´ın hiˆe.u c´o thˆe˙’ cho hai c´ach hiˆe˙’u kh´ac nhau: t´ın hiˆe.u a c´o thˆe˙’ hiˆe˙’u l`a p hay q, t´ın hiˆe.u b c´o thˆe˙’ hiˆe˙’u l`a q hay r, . . . (H`ınh 2.4 (a)). Sˆo´ cu..c d¯a.i c´ac t´ın hiˆe.u m`a ta c´o thˆe˙’ su˙’. du.ng l`a bao nhiˆeu d¯ˆe˙’ cho o˙’. m´ay thu khˆong xa˙’y ra nhˆ `am lˆa˜n gi˜ u.a c´ac t´ın hiˆe.u d¯u.o..c su˙’. du.ng. B`ai to´an quy vˆ `e t`ım mˆo.t tˆa.p ˆo˙’n d¯.inh trong . cu. c d¯a.i S cu˙’a d¯`ˆo thi. G (H`ınh 2.4(b)), trong d¯´o hai d¯ı˙’nh l`a kˆ `e nhau nˆe´u ch´ ung biˆe˙’u thi. hai . . t´ın hiˆe.u c´o thˆe˙’ lˆa˜n lˆo.n v´o i nhau o˙’ m´ay thu, ta s˜e lˆa´y S = {a, c}, v`a r˜o r`ang α(G) = 2. Thay cho c´ac t´ın hiˆe.u mˆo.t ch˜ u. c´ai, ta c´o thˆe˙’ d` ung c´ac “t` u.” gˆ `om hai ch˜ u. c´ai v´o.i d¯iˆ`eu kiˆe.n l`a c´ac t` . u n`ay khˆong gˆay ra lˆ ˜ . . `am lˆan o˙’ m´ay thu. V´o i c´ac ch˜ . u c´ai a v`a c (c´ac ch˜ . u c´ai n`ay khˆong thˆe˙’ lˆa˜n lˆo.n nhau) ta lˆa.p m˜a: aa, ac, ca, cc; nhu. vˆa.y ta d¯u.o..c [α(G)]2 = 4 t` u.. Nhu.ng ta c`on c´o thˆe˙’ lˆa.p m˜a phong ph´ u ho.n: aa, bc, ce, db, ed. (Dˆ˜e d`ang kiˆe˙’m tra rˇ`a ng hai t` u. bˆa´t k` y trong c´ac t` . ˙ ’ ˜ . ˙’ u n`ay khˆong thˆe lˆan lˆo.n v´o i nhau o m´ay thu).. a´t ca˙’ c´ T`ım tˆ ac tˆ a.p ˆ ¯i.nh trong cu..c d o˙’n d ¯a.i Phu.o.ng ph´ap suy luˆa.n sau (khˆong hiˆe.u qua˙’ d¯ˆo´i v´o.i c´ac d¯`oˆ thi. l´o.n) t`ım tˆa´t ca˙’ c´ac tˆa.p ˆo˙’n d¯.inh trong cu..c d¯a.i du..a trˆen d¯a.i sˆo´ Boole. Ta xem mˆo˜i d¯ı˙’nh cu˙’a d¯`oˆ thi. tu.o.ng u ´.ng v´o.i mˆo.t biˆe´n Boole. K´ y hiˆe.u x + y, xy v`a x0 l`a c´ac ph´ep to´an tuyˆe˙’n, hˆo.i v`a phu˙’ d¯.inh cu˙’a c´ac biˆe´n Boole x, y. V´o.i d¯`ˆo thi. G cho tru.´o.c, ta cˆ `an t`ım mˆo.t tˆa.p con cu..c d¯a.i c´ac d¯ı˙’nh khˆong kˆ `e nhau trong ˙’ ˙’ G. Biˆeu diˆ˜en mˆo˜i ca.nh (x, y) bˇ`a ng mˆo.t t´ıch Boole xy v`a sau d¯o´ lˆa´y tˆo ng cu˙’a tˆa´t ca˙’ c´ac t´ıch 59 http://www.ebook.edu.vn
a a •.....................................................................................................................................................•..... p • .. ................. ...... ...... .......... ... ...... ...... .............. ..... .. ......... ...... ................ . ..... ...... ...... .......... .......... ....... .. ......... ...... ...... ...... .... ...... ..... .......... . •q ... b• ..... ...... ................................................................................................................................... .... . ...... .......... .. ...... ...... .......... ..... e ... •b .......... .. . . . ... .... ...... ...... ............. .... .... ........................... .. ................ ..... .......... • ..... ... .. ... ... ...... . ... ... ............ .......... ... ... c• .......... .......... .......... ..... .. •r ................................................................................................................................ ... ... .... .. ... ... ... .... .................. .. ... .. .................... ... . ... ... ... .......... ... ... ..... .......... ........ ... ... d• ........... . . . .. .......... •s ................................................................................................................................. .......... .. ... ... ... . ... ... .. .. .............. ... ... ... ... ... ................ .......... ... ... ... .......... ... .. ..... .......... ... . .. ..... ................................................................................................................ e• . .......................................................................................................................... • t • • d c H`ınh 2.4: n`ay ta d¯u.o..c biˆe˙’u th´ u.c Boole X ϕ= xy. (x,y)∈E Kˆe´ tiˆe´p biˆe˙’u diˆ˜en phu˙’ d¯.inh ϕ0 da.ng tˆo˙’ng cu˙’a c´ac t´ıch Boole ϕ0 = f1 + f2 + · · · + fk . Mˆo.t tˆa.p c´ac d¯ı˙’nh l`a ˆo˙’n d¯.inh trong cu..c d¯a.i nˆe´u v`a chı˙’ nˆe´u ϕ = 0, ngh˜ıa l`a ϕ0 = 1; hay tu.o.ng d¯u.o.ng c´o ´ıt nhˆa´t mˆo.t fi = 1; t´ u.c l`a nˆe´u mˆo˜i d¯ı˙’nh xuˆa´t hiˆe.n trong fi (o˙’. da.ng phu˙’ d¯.inh) d¯u.o..c loa.i ra kho˙’i tˆa.p d¯ı˙’nh cu˙’a G. Do d¯´o mˆo˜i fi s˜e cho tu.o.ng u ´.ng mˆo.t tˆa.p ˆo˙’n d¯i.nh trong cu. c d¯a.i v`a do d¯o´ phu o ng ph´ap n`ay cho ta tˆa´t ca˙’ c´ac tˆa.p ˆo˙’n d¯.inh trong cu..c d¯a.i. Chˇa˙’ng ha.n . . . x´et d¯`ˆo thi. trong H`ınh 2.5 ta c´o ϕ = ab + bc + bd + be + ce + de + ef + eg + f g. ϕ0 = (a0 + b0 )(b0 + c0 )(b0 + d0 )(b0 + e0 )(c0 + e0 )(d0 + e0 )(e0 + f 0 )(e0 + g 0 )(f 0 + g 0 ). ut go.n v`a d¯u.a vˆ R´ `e da.ng tˆo˙’ng cu˙’a c´ac t´ıch ta d¯u.o..c ϕ0 = b0 e0 f 0 + b0 e0 g 0 + a0 c0 d0 e0 f 0 + a0 c0 d0 e0 g 0 + b0 c0 d0 f 0 g 0 . Bˆay gi`o. nˆe´u loa.i bo˙’ kho˙’i tˆa.p d¯ı˙’nh cu˙’a G c´ac d¯ı˙’nh xuˆa´t hiˆe.n trong bˆa´t k` y mˆo.t trong nˇam sˆo´ ha.ng cua tˆo ng, ta s˜e thu d¯u o. c mˆo.t tˆa.p ˆo n d¯.inh trong cu. c d¯a.i. C´ac tˆa.p ˆo˙’n d¯.inh trong cu..c ˙ ’ ˙ ’ . . ˙ ’ . d¯a.i tu.o.ng u´.ng l`a {a, c, d, g}, {a, c, d, f }, {b, g}, {b, f }, v`a {a, e}. V`a do d¯o´ sˆo´ ˆo˙’n d¯.inh trong cu˙’a d¯`ˆo thi. n`ay bˇ`a ng 4. 60 http://www.ebook.edu.vn
c ... ... ... ..... • ..... f ... ... ... . .. ... ... ... ... ....... .......... ....... .... • .... ... ....... ... . . . .. ... . ... .......... ... ... ... .. ... ....... ..... ... .. . ... ......... ... ... ... ... ........ a• . • ... ... . . . . . • . ........................................................................................................................................................... .. ............. ... ... ... b ... ... ... ... .. . .. .... . .. e ....... . ......... ... ........ .. . ... ... ... ... ........ . ... ... .. .. . . ......... .... . ... ... ... ..... . .. . .......... • ... ... ...... .. • . . g d H`ınh 2.5: 2.4 Sˆ o˙’n d o´ ˆ ¯i.nh ngo` ai - i.nh ngh˜ıa 2.4.1 Cho d¯`oˆ thi. G := (V, Γ). Tˆa.p ho..p con T c´ac d¯ı˙’nh cu˙’a V l`a tˆa.p ˆo˙’n d¯.inh D `e v´o.i ´ıt nhˆa´t mˆo.t d¯ı˙’nh trong T ; t´ ngo`ai nˆe´u mo.i d¯ı˙’nh khˆong thuˆo.c T kˆ u.c l`a T ∩ Γ(v) 6= ∅ v´o.i mo.i d¯ı˙’nh v ∈ / T. y hiˆe.u T l`a ho. c´ac tˆa.p ho..p ˆo˙’n d¯.inh ngo`ai cu˙’a d¯`oˆ thi. G th`ı: K´ 1. V ∈ T . 2. T ∈ T v`a T ⊂ A th`ı A ∈ T . Ta d¯.inh ngh˜ıa sˆo´ ˆo˙’n d¯.inh ngo`ai cu˙’a d¯`ˆo thi. G l`a sˆo´ β(G) := min{#T | T ∈ T }. Tˆa.p ˆo˙’n d¯.inh ngo`ai cu..c tiˆe˙’u l`a tˆa.p ˆo˙’n d¯.inh ngo`ai sao cho bo˙’ d¯i mˆo.t d¯ı˙’nh th`ı khˆong c`on ˆo˙’n d¯.inh ngo`ai n˜ u.a. V´ı du. 2.4.2 X´et d¯`ˆo thi. G trong H`ınh 2.5. C´ac tˆa.p {b, g} v`a {a, b, c, d, f } l`a ˆo˙’n d¯.inh ngo`ai. C´ac tˆa.p {b, e} v`a {a, c, d, f } l`a ˆo˙’n d¯.inh ngo`ai cu..c tiˆe˙’u. Dˆ˜e thˆa´y β(G) = 2. V´ı du. 2.4.3 V´o.i d¯`oˆ thi. trong H`ınh 2.6, tˆa.p ˆo˙’n d¯.inh ngo`ai cu..c tiˆe˙’u ch´ u.a sˆo´ nho˙’ nhˆa´t c´ac `an tu˙’. l`a {v1 , v4 } v`a do d¯´o β(G) = 2. phˆ B`ai to´an ta x´et o˙’. d¯ˆay l`a xˆay du..ng mˆo.t tˆa.p ho..p ˆo˙’n d¯.inh ngo`ai v´o.i sˆo´ phˆ `an tu˙’. ´ıt nhˆa´t. 61 http://www.ebook.edu.vn
v1 .....• ......... .......... ......... ............... .. . ....... ..... ... ...... ... . ... ....... ...... ... ... ........ ...... ..... ... ......... .. .. ....... . . .. . ... ...... .... . .... .... ... ... ...... ...... ........ .. .. ... ...... .. .. .... ... . ... ...... ... ...... ..... ...... v6 • ....... . . ... .. . ... ... ... . ... .. . . . . .... . .... .............. . ..... .. .. . ...... ...... ............ • v2 ... . ... ... . . ... ... . . ... .. . ....... .... .... ... ... ......... ... ... ...... ......... ... ... ... ............... .. ...... ...... ............ ... ..... .... ..... . . ... . . .......... . ... ... ... ... ............. ... ... . .. . . ... .............. .... . ... ... ........... v5 • .......... ... ..... ....... ... ... . .. ....... .... . . ........ ... .... . • v3 ... .... . . ...... ... ... ..... ... . ... ... .. ....... ... ... .......... ... ... ...... ... ... ...... ... .... .......... . ... . .. ... ............... ... ......... .... • v4 H`ınh 2.6: V´ı du. 2.4.4 B`ai to´an vˆ `e nh˜u.ng ngu.`o.i d¯u ´.ng g´ac. Trong mˆo.t tra.i giam o˙’. th`anh phˆo´ N, mˆo˜i nh`a giam c´o mˆo.t tra.m g´ac d¯ˆo.c lˆa.p, nhu.ng ngu.`o.i d¯u ´.ng g´ac, chˇa˙’ng ha.n o˙’. nh`a giam v1 , c˜ ung c´o thˆe˙’ nh`ın thˆa´y nh˜ . . u ng g`ı xa˙’y ra o˙’ c´ac nh`a giam v2 , v6 , v8 , v9 , nh˜ u.ng nh`a giam n`ay thˆong v´o.i nh`a giam v1 bo˙’.i mˆo.t h`anh lang thˇa˙’ng nhu. ta thˆa´y trˆen H`ınh 2.7. Ho˙’i sˆo´ ngu.`o.i d¯u ´.ng g´ac cˆ `an thiˆe´t ´ıt nhˆa´t l`a bao nhiˆeu d¯ˆe˙’ quan s´at d¯u.o..c mo.i nh`a giam? Ta pha˙’i t`ım sˆo´ ˆo˙’n d¯.inh ngo`ai cu˙’a d¯`oˆ thi. vˆo hu.´o.ng trong H`ınh 2.7, d¯ˆo´i v´o.i so. d¯`oˆ rˆa´t d¯o.n gia˙’n n`ay th`ı sˆo´ ˆo˙’n d¯.inh ngo`ai l`a 2. v..7 .........• .... .......... ...... .......... ... . .......... ...... .......... ...... .......... ... ... ...... ............. ... ... . . . . .. . . . ....... ... ... ... .. .. ........ ... ... ....... . ... .... v6 ........ ... . .. . ......... . .... .. . ... ... ... ... • . .................... ................ . .. ........ .......... ... ... ... ... ... ... ... ... ......... ........ ... ..... ........ . . ... ... ... ..... . ........ ... .... ... ..... . .... ........ ... ... ... ...... ........ ... ... ... ..... ........ ... ... ... ..... ......... ........ ... ... ... ..... ........ . . . ... ... ...... ........ ... ... ... ..... ........ ... ... ... ..... ........ ... ... ..... ..... v4 .......... .... ......... .. . ... ... ... ... ... ... ... ... . ..... ..... ..... ..... ................ .... ...• .. ..... ............. . . ... . ......... .. ........... . . . . . ........ ... ... . ... ... ... ... ... ... • ....... . .. . . . ... . . .• . . .. .. .. . . ....... ... ... ... ... ... ... v5 ... ... ... . .. . . . . ... . ... .. ... ... .... ................. . . . . . . ...... ........ . . . . ... . . . ................ v8 ... ... ... ... ... . . ............... . .... . ... . . .. ... ... ... . ... .... . ....... • .. . .......... . . . ....... . .... ... ... ... ... ... ... .. ..... . ... .. ...... ... .. ...... . .. . .. v3 .. .. . .... ............ ... ... ... ... . ....... ... ... . . . . . • ... .......... ... ... . .... ....... ... ... v2 ... .. ... ... ... . ...... ... ................. ... ... ... ... ...... ...... .. • ............ ................................................................................................................................................................. • v1 v9 H`ınh 2.7: V´ı du. 2.4.5 Vi. tr´ı cu˙’a c´ac “tˆam” d¯ˆe˙’ phu˙’ mˆo.t v` `eu l˜ınh vu..c liˆen quan d¯ˆe´n b`ai ung. C´o nhiˆ to´an n`ay: `en d¯ˆe´n mˆo.t sˆo´ vi. tr´ı cho tru.´o.c. 1. Vi. tr´ı cu˙’a c´ac m´ay ph´at T.V. hay radio truyˆ 62 http://www.ebook.edu.vn
2. Vi. tr´ı cu˙’a c´ac tra.m g´ac d¯ˆe˙’ gi´am s´at mˆo.t v` ung. 3. Tra.m l`am viˆe.c cu˙’a ngu.`o.i b´an h`ang d¯ˆe˙’ phu.c vu. mˆo.t v` ung. Gia˙’ su˙’. rˇ`a ng mˆo.t v` ung-cho bo˙’.i h`ınh vuˆong l´o.n trong H`ınh 2.8-d¯u.o..c phˆan hoa.ch th`anh 16 v` ung nho˙’ ho n. Gia˙’ su˙’. mˆo.t tra.m g´ac d¯u.o..c d¯aˇ. t trong mˆo.t v` . ung nho˙’ c´o thˆe˙’ gi´am s´at khˆong chı˙’ h`ınh vuˆong n´o d¯aˇ. t m`a c`on nh˜ u ng h`ınh vuˆong c´o chung biˆen v´o.i n´o. Cˆau ho˙’i d¯aˇ. t ra l`a . sˆo´ tˆo´i thiˆe˙’u c´ac tra.m g´ac v`a vi. tr´ı cu˙’a ch´ ung sao cho c´o thˆe˙’ d¯iˆ `eu khiˆe˙’n to`an bˆo. v` ung. Nˆe´u .................................................................................................................................................... .... .... .... .... .... ... ... ... ... ... ... ... ... 1 2... ... ... ... ... ... 3 ... ... ... 4 ... ... .. ............................................................................................................................................................. .. .. ... .. ... ... ... ... ... ... ... ... ... ... ... ... ...5 ... 6 ... ... ... ... ... ... 7 ... ... ... 8 ... ... .. ............................................................................................................................................................. .. .. ... .. ... ... ... ... ... ... ... ... ... ... ... 9 ... ... ... 10 ... ... ... 11 ... ... ... ... ... ... 12 ... ... ... ... ... ... ... .. .......................................................................................................................................................... ... ... ... ... ... ... ... ... ... ... 13 ... ... ... 14 ... ... ... 15 ... ... ... 16... ... ... ... ... ... ... ... ... ... .. ................................................................................................................................................ H`ınh 2.8: ta biˆe˙’u diˆ˜en mˆo˜i v` ung nho˙’ bo˙’.i mˆo.t d¯ı˙’nh v`a mˆo.t ca.nh liˆen thuˆo.c hai d¯ı˙’nh nˆe´u hai v` ung . . tu o ng u . ´ ng c´o chung mˆo.t biˆen (h˜ay v˜e h`ınh!). B`ai to´an d¯u a vˆ . ˙ ’ `e t`ım tˆa.p ˆo n d¯.inh ngo`ai c´o sˆo´ phˆ`an tu˙’. nho˙’ nhˆa´t-l`a β(G). Trong v´ı du. n`ay, β(G) = 4 v`a c´ac tra.m g´ac cˆ `an d¯ˇa.t ta.i c´ac vi. tr´ı {3, 5, 12, 14} hoˇa.c ta.i {2, 9, 15, 8}. V´ı du. 2.4.6 B`ai to´an vˆ `e 5 con hˆa.u. Trˆen b`an c`o. quˆo´c tˆe´ cˆ `an bˆo´ tr´ı bao nhiˆeu con hˆa.u d¯ˆe˙’ cho mo.i ˆo trˆen b`an c`o d¯ˆeu bi. ´ıt nhˆa t mˆo.t con hˆa.u khˆong chˆe. B`ai to´an n`ay d¯u.a vˆ . ` ´ ´ ´ `e t`ım mˆo.t . . . tˆa.p ho. p ˆo˙’n d¯.inh ngo`ai cu. c tiˆe˙’u cho d¯`ˆo thi. c´o 64 d¯ı˙’nh (l`a c´ac ˆo cu˙’a b`an c`o ), trong d¯´o hai `e nhau nˆe´u v`a chı˙’ nˆe´u c´ac ˆo tu.o.ng u d¯ı˙’nh kˆ ´.ng nˇ`a m trˆen c` ung mˆo.t h`ang, mˆo.t cˆo.t hoˇa.c c` ung . . mˆo.t d¯u `o ng ch´eo. Sˆo´ ˆo˙’n d¯.inh l`a +5 d¯ˆo´i v´o.i c´ac con hˆa.u, chˇa˙’ng ha.n v´o.i hai c´ach sˇa´p xˆe´p: (3, 3), (4, 6), (5, 4), (6, 2), (7, 5) v`a (5, 1), (8, 3), (4, 4), (3, 6), (7, 8), trong d¯´o (i, j) l`a vi. tr´ı cu˙’a con hˆa.u o˙’. h`ang i v`a cˆo.t j. C˜ ung dˆ˜e thˆa´y sˆo´ ˆo˙’n d¯.inh l`a: +8 d¯ˆo´i . . . v´o i c´ac con th´ap; +12 d¯oˆ´i v´o i c´ac con m˜a; +8 d¯oˆ´i v´o i c´ac con d¯iˆen. 63 http://www.ebook.edu.vn
V´ı du. 2.4.7 B`ai to´an vˆ `e s´au c´ai d¯˜ıa d¯o˙’ . Tr`o cho.i sau d¯ˆay rˆa´t quen thuˆo.c d¯ˆo´i v´o.i nh˜u.ng . . . . . ngu `o i u a th´ıch hˆo.i cho. Ph´ap: Trˆen b`an d¯aˇ. t mˆo.t c´ai d¯˜ıa l´o n m`au trˇa´ng (b´an k´ınh 1), h˜ay t`ım c´ach phu˙’ ho`an to`an d¯˜ıa d¯o´ bo˙’.i s´au d¯˜ıa con d¯o˙’ (b´an k´ınh r < 1) lˆ `an lu.o..t d¯ˇa.t trˆen b`an, v`a khi d¯˜a d¯ˇa.t rˆ `oi th`ı khˆong d¯u.o..c xˆe di.ch n˜ u.a. Ho˙’i b´an k´ınh r nho˙’ nhˆa´t bˇ`a ng bao nhiˆeu d¯ˆe˙’ . . c´o thˆe˙’ gia˙’i d¯u o. c? B`ai to´an d¯u.a vˆ`e t`ım mˆo.t tˆa.p ˆo˙’n d¯.inh ngo`ai cu..c tiˆe˙’u T cho “d¯`ˆo thi. vˆo ha.n” (V, E), trong d¯o´ V l`a tˆa.p ho..p c´ac d¯iˆe˙’m cu˙’a d¯˜ıa trˇa´ng, v`a hai d¯ı˙’nh kˆ u.a `e nhau nˆe´u khoa˙’ng c´ach gi˜ hai d¯iˆe˙’m tu.o.ng u ´.ng nho˙’ ho.n hoˇa.c bˇ`a ng r. u. d¯.inh ngh˜ıa dˆ˜e d`ang suy ra T` 1. Tˆa.p gˆ `om d¯u ´ng mˆo.t d¯ı˙’nh trong d¯`oˆ thi. d¯`aˆy d¯u˙’ Kn l`a tˆa.p ˆo˙’n d¯.inh ngo`ai cu..c tiˆe˙’u. 2. Mo.i tˆa.p ˆo˙’n d¯.inh ngo`ai ch´ u.a ´ıt nhˆa´t mˆo.t tˆa.p ˆo˙’n d¯.inh ngo`ai cu..c tiˆe˙’u. `eu tˆa.p ˆo˙’n d¯.inh ngo`ai cu..c tiˆe˙’u v´o.i k´ıch thu.´o.c kh´ac nhau. 3. Mˆo.t d¯`ˆo thi. c´o thˆe˙’ c´o nhiˆ 4. Tˆa.p ˆo˙’n d¯.inh ngo`ai cu..c tiˆe˙’u c´o thˆe˙’ hoˇa.c khˆong l`a ˆo˙’n d¯.inh trong. 5. Mo.i tˆa.p ˆo˙’n d¯.inh trong cu..c d¯a.i l`a tˆa.p ˆo˙’n d¯i.nh ngo`ai. Thˆa.t vˆa.y, nˆe´u tr´ai la.i th`ı c´o ´ıt nhˆa´t mˆo.t d¯ı˙’nh khˆong nˇa` m trong tˆa.p n`ay v`a c˜ ung khˆong kˆ `e v´o.i mˆo.t d¯ı˙’nh bˆa´t k` y trong . . d¯´o. Mˆo.t d¯ı˙’nh nhu thˆe´ c´o thˆe˙’ thˆem v`ao m`a khˆong ph´a v˜o t´ınh ˆo˙’n d¯i.nh trong v`a do d¯´o mˆau thuˆa˜n v´o.i t´ınh cu..c d¯a.i cu˙’a n´o. 6. Mˆo.t tˆa.p ˆo˙’n d¯.inh trong c´o t´ınh ˆo˙’n d¯.inh ngo`ai chı˙’ nˆe´u n´o l`a tˆa.p ˆo˙’n d¯.inh trong cu..c d¯a.i. 7. V´o.i mo.i d¯`oˆ thi. G bˆa´t d¯aˇ˙’ ng th´ u.c sau luˆon thoa˙’ β(G) ≤ α(G). T`ım c´ ac tˆ o˙’n d a.p ˆ ai cu..c tiˆ ¯i.nh ngo` e˙’u Tu.o.ng tu.. c´ach x´ac d¯.inh tˆa.p ˆo˙’n d¯i.nh trong cu..c d¯a.i, ta c´o thˆe˙’ d` ung d¯a.i sˆo´ Boole d¯ˆe˙’ x´ac d¯i.nh . c´ac tˆa.p ˆo˙’n d¯.inh ngo`ai cu. c tiˆe˙’u cu˙’a d¯`ˆo thi. G. - ˆe˙’ kiˆe˙’m tra d¯ı˙’nh vi ta cˆ D `e v´o.i n´o. Tˆa.p nho˙’ nhˆa´t `an lˆa´y hoˇa.c d¯ı˙’nh vi hoˇa.c mˆo.t d¯ı˙’nh kˆ c´ac d¯ı˙’nh thoa˙’ m˜an d¯iˆ `eu kiˆe.n n`ay l`a tˆa.p cˆ . `an t`ım. Do d¯´o, v´o i mˆo˜i d¯ı˙’nh vi trong G ch´ ung ta x´et t´ıch Boole cu˙’a c´ac tˆo˙’ng (vi1 + vi2 + · · · + vid ) trong d¯´o vi1 , vi2 , . . . , vid l`a c´ac d¯ı˙’nh kˆ `e v´o.i d¯ı˙’nh vi v`a d l`a bˆa.c cu˙’a n´o: Y θ= (vi1 + vi2 + · · · + vid ). vi ∈V 64 http://www.ebook.edu.vn
Khi θ viˆe´t du.´o.i da.ng tˆo˙’ng cu˙’a c´ac t´ıch, mˆo˜i sˆo´ ha.ng trong d¯´o s˜e tu.o.ng u ´.ng v´o.i mˆo.t tˆa.p ˆo˙’n . d¯.inh ngo`ai cu. c tiˆe˙’u. Ch´ . ung ta minh ho.a thuˆa.t to´an n`ay su˙’ du.ng d¯`ˆo thi. trong H`ınh 2.5. Ta 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ˆa.t hˆa´p thu. (x + y)x = x ta suy ra θ = (a + b)(c + b + e)(d + b + e)(f + e + g) = ae + be + bf + bg + acdf + acdg. u.c n`ay tu.o.ng u Mˆo˜i sˆo´ ha.ng trong s´au biˆe˙’u th´ ´.ng mˆo.t tˆa.p ˆo˙’n d¯.inh ngo`ai tˆo´i thiˆe˙’u. Hiˆe˙’n nhiˆen β(G) = 2. - ˆe˙’ x´ac d¯i.nh mˆo.t tˆa.p ho..p ˆo˙’n d¯.inh trong cu..c d¯a.i, hay mˆo.t tˆa.p ho..p ˆo˙’n d¯.inh ngo`ai cu..c D `an lu.o..t mˆo˜i tˆa.p ho..p con T cu˙’a V v`a kiˆe˙’m tra xem n´o c´o thoa˙’ m˜an c´ac tiˆe˙’u, ta c´o thˆe˙’ x´et lˆ d¯iˆ`eu kiˆe.n d¯a˜ d¯`ˆe ra hay khˆong. Tˆa´t nhiˆen phu.o.ng ph´ap loa.i dˆ `an n`ay n´oi chung khˆong d` ung . . . . ` ˙ ’ . ˙ ’ ˙ ’ ´ d¯u o. c. Ngu `o i ta cˆan phai d¯u a ra c´ac thuˆa.t to´an. Chˇang ha.n, khi giai quyˆet b`ai to´an vˆe t´am ` con hˆa.u, nˆe´u d` ung phu.o.ng ph´ap loa.i dˆ `an khoa˙’ng 10 gi`o. d¯ˆe˙’ t´ınh to´an, trong khi d¯o´ nˆe´u `an cˆ c´o mˆo.t thuˆa.t to´an tˆo´t, ch´ ung ta chı˙’ cˆ `an ba ph´ ut l`a th` u.a d¯u˙’; ngo`ai ra cˆ`an ch´ ´ rˇa` ng: nˆe´u uy . . ´ . ´ . ta d¯a˜ d¯a.t d¯u o. c viˆe.c xˆep 8 con hˆa.u trˆen b`an c`o , th`ı mˆo.t lˆa.p luˆa.n rˆa t d¯o n gian chı˙’ cho ta r˜o ˙ ’ rˇa` ng khˆong thˆe˙’ l`am tˇang sˆo´ con hˆa.u lˆen d¯u.o..c n˜ u.a trong tru.`o.ng ho..p tˆo˙’ng qu´at ho.n, c˜ ung ` ˙’ . ˙ ’ ´ . ˙ ’ . cˆan c´o mˆo.t tiˆeu chuˆa n d¯o n gia˙’n d¯ˆe nhˆa.n biˆet mˆo.t tˆa.p ho. p ˆo n d¯.inh trong cu. c d¯a.i hay khˆong, v`a chı˙’ c´o thuˆa.t to´an d¯˜a d¯u.o..c suy ngh˜ı k˜ y m´o.i c´o thˆe˙’ gi´ up ta biˆe´t d¯iˆ`eu d¯´o (xem [4]). 2.5 Phu˙’ Tˆa.p g c´ac ca.nh d¯u.o..c go.i l`a phu˙’ cu˙’a d¯`ˆo thi. G = (V, Γ) nˆe´u mˆo˜i d¯ı˙’nh bˆa´t k` y thuˆo.c V liˆen . ´ thuˆo.c v´o i ´ıt nhˆa t mˆo.t ca.nh trong g. um trong d¯`oˆ thi. vˆo hu.´o.ng liˆen thˆong l`a mˆo.t phu˙’. V´ı du. 2.5.1 (a) Cˆay bao tr` (b) Chu tr`ınh Hamilton (nˆe´u n´o tˆ `on ta.i) trong d¯`oˆ thi. l`a mˆo.t phu˙’. V´ı du. 2.5.2 Trong tra.i giam cu˙’a th`anh phˆo´ N, so. d¯`oˆ v˜e k`em theo d¯ˆay, mˆo˜i ngu.`o.i g´ac o˙’. h`anh lang (a, b) pha˙’i gi´am s´at hai gian a v`a b l`a hai d¯`ˆau cu˙’a h`anh lang; ho˙’i sˆo´ ngu.`o.i g´ac ´ıt nhˆa´t l`a bao nhiˆeu d¯ˆe˙’ mˆo˜i gian ´ıt nhˆa´t c´o mˆo.t ngu.`o.i gi´am s´at? B`ai to´an n`ay d¯u.a vˆ `e t`ım . phu˙’ cu. c tiˆe˙’u cu˙’a mˆo.t d¯`oˆ thi.. Trˆen d¯`oˆ thi. H`ınh 2.11, phu˙’ nho˙’ nhˆa´t c´o nˇam d¯ı˙’nh, vˆa.y nˇam ngu.`o.i g´ac l`a d¯u˙’. 65 http://www.ebook.edu.vn
....... • ....... ............................................ ........ ............. ....... .. ....... ....... ....... .......................... . . ... . ........ ............. .... . ...... ....... ....... ............. ............. . .. .. . ..... ....... ............. ............. ..... ....... • . . .. ....................................................................................................................................................................... . . . ..... .......... • . .. ....... ........ ....... • ............. ....... . ..... ............ ..... .......... • . .... ............... . .. ........... ......... .. ..... .... ......... ..... ..... ..... ..... • .......... ....... ........ ..... ..... ..... ........ • ....... .......... ..... . ........ . ..... . .... ...... ....... ... ....... ... ......... ..... ..... ....... ..... ..... ..... ....... ..... ..... ..... ..... • ..... . .... . .... ..... ....... . ....... ....... . .............. ..... ... ..... ....... ..... .. ..... ....... ..... ..... ... ... ...... .............. ..... .. ...... .......... ..... .. ............. • ................... .. H`ınh 2.9: Trong mˆo.t d¯`oˆ thi., c´o thˆe˙’ c´o nhiˆ `eu phu˙’, vˆa´n d¯`ˆe o˙’. d¯aˆy l`a cˆ u.u phu˙’ m`a c´o `an nghiˆen c´ mˆo.t v`ai t´ınh chˆa´t d¯aˇ. c biˆe.t n`ao d¯´o nhu. cˆay bao tr` um hay chu tr`ınh Hamnilton. Ta s˜e nghiˆen u.u phu˙’ tˆo´i thiˆe˙’u: l`a phu˙’ m`a nˆe´u bo˙’ d¯i mˆo.t ca.nh th`ı s˜e ph´a hu˙’y thuˆo.c t´ınh phu˙’ cu˙’a n´o. c´ u. d¯.inh ngh˜ıa dˆ˜e d`ang suy ra T` `on ta.i phu˙’ trong mˆo.t d¯`oˆ thi. nˆe´u v`a chı˙’ nˆe´u d¯`oˆ thi. khˆong c´o d¯ı˙’nh cˆo lˆa.p. 1. Tˆ y hiˆe.u [x] l`a sˆo´ nguyˆen l´o.n nhˆa´t 2. Mˆo.t phu˙’ cu˙’a d¯`oˆ thi. n d¯ı˙’nh c´o ´ıt nhˆa´t [n/2] ca.nh (k´ . . khˆong vu o. t qu´a x). 3. Mo.i ca.nh treo trong d¯`ˆo thi. nˇ`a m trong phu˙’ cu˙’a d¯`ˆo thi.. u.a phu˙’ tˆo´i thiˆe˙’u. 4. Mo.i phu˙’ d¯`ˆeu ch´ 5. Tˆa.p c´ac ca.nh g l`a mˆo.t phu˙’ nˆe´u v`a chı˙’ nˆe´u, v´o.i mo.i d¯ı˙’nh v ∈ V ta c´o dG\g (v) ≤ dG (v)−1, trong d¯o´ G \ g l`a d¯`ˆo thi. G xo´a d¯i c´ac ca.nh thuˆo.c g. u.a chu tr`ınh. Do vˆa.y mo.i phu˙’ tˆo´i thiˆe˙’u cu˙’a d¯`oˆ thi. n d¯ı˙’nh khˆong 6. Phu˙’ tˆo´i thiˆe˙’u khˆong ch´ u.a ho.n (n − 1) ca.nh. ch´ 7. Mˆo.t d¯`ˆo thi., n´oi chung, c´o nhiˆ ung c´o thˆe˙’ c´o k´ıch thu.´o.c kh´ac `eu phu˙’ tˆo´i thiˆe˙’u, v`a ch´ nhau (gˆ `om sˆo´ c´ac ca.nh kh´ac nhau). Sˆo´ c´ac ca.nh trong mˆo.t phu˙’ tˆo´i thiˆe˙’u c´o c˜o. nho˙’ nhˆa´t d¯u.o..c go.i l`a sˆo´ phu˙’ cu˙’a d¯`ˆo thi.. - i.nh l´ D u.a c´ac dˆay y 2.5.3 Phu˙’ g cu˙’ a mˆo.t d¯`ˆo thi. l`a tˆo´i thiˆe˙’u nˆe´u v`a chı˙’ nˆe´u g khˆong ch´ chuyˆ`en c´o d¯ˆo. d`ai l´o.n ho.n hoˇa.c bˇ`a ng ba. Ch´ u.ng minh. D- iˆ `an. Gia˙’ su˙’. g l`a phu˙’ tˆo´i thiˆe˙’u cu˙’a G m`a ch´ `eu kiˆe.n cˆ u.a mˆo.t dˆay chuyˆ `en c´o d¯oˆ. d`ai ba l`a µ := {v1 , e1 , v2 , e2 , v3 , e3 , v4 }. Trong g bo˙’ ca.nh e2 th`ı ta vˆa˜n thu d¯u.o..c mˆo.t phu˙’ cu˙’a G, d¯iˆ `eu n`ay mˆau thuˆa˜n v´o.i t´ınh tˆo´i thiˆe˙’u cu˙’a g. 66 http://www.ebook.edu.vn
•....... •......... .. ... ... • •....... .... ... ... .... ... ... ... . .... ... .. ... .. .. ... ... ... ... ..... ... ... ... ... •...................................................•.....................................................•... ...... ... ... • • • . • .............................................................................................................. .... ... .... .. ... .. .... ... ... ... ... ... ... .... .... • • • ... (a) (b) (c) (d) H`ınh 2.10: C´ac d¯`ˆo thi. h`ınh sao. - iˆ D `eu kiˆe.n d¯u˙’. Ngu.o..c la.i, nˆe´u g khˆong ch´ u.a mˆo.t dˆay chuyˆ `en n`ao c´o d¯oˆ. d`ai l´o.n ho.n hoˇa.c bˇa` ng ba th`ı c´ac th`anh phˆ `an cu˙’a n´o pha˙’i c´o mˆo.t trong c´ac da.ng “h`ınh sao” nhu. trong H`ınh 2.10. Hiˆe˙’n nhiˆen nˆe´u xo´a bˆa´t k` y mˆo.t ca.nh cu˙’a d¯`ˆo thi. h`ınh sao th`ı s˜e c´o ´ıt nhˆa´t mˆo.t d¯ı˙’nh . khˆong liˆen thuˆo.c v´o i ca.nh c`on la.i cu˙’a g. Vˆa.y g l`a phu˙’ tˆo´i thiˆe˙’u. / V´ı du. 2.5.4 Gia˙’ su˙’. d¯`ˆo thi. trong H`ınh 2.11 biˆe˙’u diˆ˜en ba˙’n d¯`oˆ giao thˆong cu˙’a mˆo.t th`anh phˆo´. Mˆo˜i d¯ı˙’nh l`a mˆo.t n´ut giao thˆong thu.`o.ng xa˙’y ra tˇa´c ngh˜en v`a mˆo˜i ca.nh tu.o.ng u ´.ng mˆo.t d¯a.i lˆo. nˆo´i hai n´ ut giao thˆong. Cˆ `an tra trˆen c´ac d¯a.i lˆo. sao cho c´o thˆe˙’ gi´am `an d¯aˇ. t c´ac d¯ˆo.i tuˆ ut giao thˆong. Vˆa´n d¯`ˆe d¯ˇa.t ra l`a sˆo´ tˆo´i thiˆe˙’u c´ac d¯ˆo.i tuˆ s´at tˆa´t ca˙’ c´ac n´ `an tra l`a bao nhiˆeu? . . Cˆau tra˙’ l`o i ch´ınh l`a t`ım phu˙’ tˆo´i thiˆe˙’u v´o i sˆo´ phˆ . `an tu˙’ ´ıt nhˆa´t cu˙’a d¯`oˆ thi.. Dˆ˜e kiˆe˙’m tra hai ˙’ tˆa.p sau l`a phu˙’ tˆo´i thiˆeu: {(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)}. `eu nhˆa´t hai d¯ı˙’nh nˆen khˆong thˆe˙’ phu˙’ d¯`oˆ thi. ´ıt ho.n s´au Do c´o 11 d¯ı˙’nh v`a mˆo˜i ca.nh phu˙’ nhiˆ ca.nh. e h b •....................................................................................•......................................................................................•......................................................................................•........... l ..... ..... ... ..... ... .... ..... ..... .... ..... ..... ... ..... ..... ... ... ..... ... ..... ... ..... ... .. ..... ... ..... ... ..... ... ... ..... ..... . . . ..... ..... . ... .. ...... ... ... ..... . . ..... . ... . . ..... ... ... ..... .. . ....... ... .. ..... ... ... ..... . . . .. . . ... ..... .. ..... . ..... ... ..... .. ..... .... ..... .... ... ..... .. ..... .. ..... .. a• • .. • ..................................................................................................................................................................................................................... ..... ..... ........... .... .. . ..... •k ..... ..... ..... ..... d ... ....... ... . . ..... ..... ..... g ... ... . . . ...... . ..... ..... ..... .... ..... . .... ..... ..... ..... ..... ..... ... ..... ... ..... ..... ... ..... ... ..... ..... . . ..... . . ....... ..... . .. ..... ..... ... ..... .. ..... ..... .... ..... .... ......... ..... .. ..... .. ..... ..... .. .. . .. ................................................................................................................................................. • ... ... • . ... ... • i c ... .... .... ..... ........ ... f ...... ..... ......... ...... ......................... H`ınh 2.11: 67 http://www.ebook.edu.vn
Cu..c tiˆ e˙’u ho´ a h` am Boole Mˆo.t phˆ `an quan tro.ng trong viˆe.c thiˆe´t kˆe´ c´ac ma.ch sˆo´ l`a cu..c tiˆe˙’u ho´a h`am Boole tru.´o.c khi thiˆe´t kˆe´ n´o. Gia˙’ su˙’. ta muˆo´n xˆay du..ng ma.ch logic cho bo˙’.i h`am Boole bˆo´n biˆe´n f (x, y, z, w) = w0 x0 y 0 z 0 + w0 x0 yz 0 + w0 x0 yz + w0 xyz 0 + w0 xyz + wxyz. Ch´ ung ta h˜ay biˆe˙’u diˆ˜en mˆo˜i mˆo.t trong ba˙’y th`anh phˆ`an cu˙’a f bo˙’.i mˆo.t d¯ı˙’nh v`a mˆo.t ca.nh liˆen thuˆo.c hai d¯ı˙’nh nˆe´u v`a chı˙’ nˆe´u hai th`anh phˆ`an chı˙’ kh´ac nhau d¯u´ng mˆo.t biˆe´n. D - `ˆo thi. . . tu o ng u . ´ ng h`am f cho trong H`ınh 2.12. w0 xyz 0 ...• ......... ..... .......... ..... .... ..... ..... ..... e.3...................... ..... ..... e4 ..... w 0 x0 y 0 z 0 e2 . ...... . . . . ... ..... ..... ..... ..... ..... e7 wxyz • ... • . ..................................................................................................................... ..... ..... • ..... • ............................................................................................................... ..... w0 x0 yz 0 w0 xyz ... ..... .. .. ... ..... ........ ..... ..... ... ... ... e5 ..... ..... ..... ..... ..... ..... ..... e6 ..... .. ...... ... ..... .. ..... ......... e1 ... ... ... • ........ ... ... ... w0 x0 yz ... ... ... ... • . wx0 y 0 z 0 H`ınh 2.12: Mˆo.t ca.nh liˆen thuˆo.c hai d¯ı˙’nh tu.o.ng u ´.ng mˆo.t th`anh phˆ `an v´o.i ba biˆe´n. Mˆo.t phu˙’ tˆo´i thiˆe˙’u cu˙’a d¯`oˆ thi. cho ta mˆo.t d¯o.n gia˙’n ho´a h`am Boole f, v´o.i c` u.c ung ch´ nˇang nhu. f nhu.ng thiˆe´t kˆe´ su˙’. du.ng ´ıt cˆo˙’ng logic ho.n. C´ac ca.nh treo e1 v`a e7 cˆ `an thuˆo.c mo.i phu˙’ cu˙’a d¯`oˆ thi.. Bo˙’.i vˆa.y c´ac th`anh phˆ `an x0 y 0 z 0 v`a xyz l`a khˆong thˆe˙’ khu˙’. d¯u.o..c. Hai ca.nh e3 v`a e6 (hoˇa.c e4 v`a e5 , hoˇa.c e3 v`a e5 ) s˜e phu˙’ c´ac d¯ı˙’nh c`on la.i. Do d¯o´ ta c´o thˆe˙’ viˆe´t la.i f = x0 y 0 z 0 + xyz + w0 yz 0 + w0 yz. w0 yz •....... .... ... .. ... xyz • ... ... ... • x0 y 0 z 0 ... ... ... ... • ... w0 yz 0 H`ınh 2.13: 68 http://www.ebook.edu.vn