Lí thuyết đồ thị part 2

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

Thêm vào BST

Báo xấu

102
lượt xem 15
download

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

Đồ thị biểu diễn được rất nhiều cấu trúc, nhiều bài toán thực tế có thể được biểu diễn bằng đồ thị. Ví dụ, cấu trúc liên kết của một website có thể được biểu diễn bằng một đồ thị có hướng như sau: các đỉnh là các trang web hiện có tại website, tồn tại một cạnh có hướng nối từ trang A tới trang B khi và chỉ khi A có chứa 1 liên kết tới B. Do vậy, sự phát triển của các thuật toán xử lý đồ thị là một trong các mối quan tâm chính...

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 2

1.3 T´ liˆn thˆng ınh e o ` 1.3.1 Dˆy chuyˆn v` chu tr` a e a ınh Gia su. v0 , vk l` c´c d ınh cua d` thi vˆ hu.´.ng G := (V, E ). Dˆy chuyˆn µ t`. v0 dˆn vk d ˆ ` ´ ˙˙ ’’ a a ¯˙ ’ ˙ ¯ˆ . o o ’o a e u ¯e ¯o. . v v` kˆt th´c tai v , ´ˆ d`i k l` mˆt d˜y xen k˜ (k + 1) d ınh v` k canh bˇt d` u t` 0 a e ´ ¯˙ ’ a aoa e a a ¯a u u.k . . µ := {v0 , e1 , v1 , e2 , v2 , . . . , vk−1 , ek , vk }, trong d o canh ei liˆn thuˆc c´c d ınh vi−1 v` vi , i = 1, 2, . . . , k. Dˆ’ gian tiˆn, ta thu.`.ng viˆt -e ˙ ˙’ ´ o a ¯˙ ’ ¯´ . e a e o e . . µ := {e1 , e2 , . . . , ek }. Dˆy chuyˆn d u.o.c goi l` d o.n gian (tu.o.ng u.ng, so. cˆ p) nˆu n´ khˆng d i hai lˆn qua ` ¯. ´ ´oo ` ˙ ’ a e . a¯ ´ a e ¯ a .o.ng u.ng, d ınh). ˙ ’ c`ng mˆt canh (tu u o. ´ ¯ . Chu tr` l` mˆt dˆy chuyˆn trong d o d ınh d` u tr`ng v´.i d ınh cuˆi. Chu tr` qua ` ´ ¯´ ¯˙ ’ ¯a o ¯˙’ ınh a o a e ˆ u o ınh . ˜i canh d ung mˆt lˆn goi l` d o.n gian. Chu tr` l` so. cˆ p nˆu n´ d i qua mˆ i d ınh d ung ˜ ¯˙ o` ´´ ˙ ’ o ’ ¯´ mˆ . o ¯´ . a . a¯ ınh a a e o¯ mˆt lˆn tr`. d ınh d` u tiˆn hai lˆn (mˆt lˆn l´c xuˆ t ph´t v` mˆt l´c tro. vˆ). o` ` o` u ´ ˙` u ¯˙ ¯ˆ ’ ’e a a e a a a aaou . . . -ˆ . D` thi trong H` 1.11 c´ o ınh o (a, e1 , b, e2 , c, e3 , d, e4 , b) l` dˆy chuyˆn t`. d ınh a dˆn d ınh b c´ d o d`i bˆn. C´c chu tr` sau l` so. cˆ p ` u ¯˙ ´’ ´ ´ ’ ¯e ¯˙ aa e o ¯ˆ a o a ınh a a . (b, e2 , c, e3 , d, e4 , b), v` (b, e5 , f, e7 , e, e6 , b). a e1 .b e2 a •..........................................•......................................................................................................................................................................• c .. . .. .. . .. . . .. . . . . .... . .. .... .... .. .... e4 ................ ....e .. .... .... .... .. .. .... .. 3 .. .. .. .... .... .. .. .. .... .... . .. .... .... .... ....... . .... ....... . . • . . . . . .. .. . . . . . . . . . . . . . d . . e5 .......... .......... e6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •g . . f• e • . ......................................................................................... . ......................................................................................... . . e8 7e H` 1.11: ınh Trong tru.`.ng ho.p d` thi khˆng c´ canh song song (t´.c l` hai d ınh c´ nhiˆu nhˆ t mˆt o` ´o ¯˙’ o . ¯o . o ˆ o. ua e a . .n gian dˆy chuyˆn µ d u.o.c viˆt lai canh liˆn thuˆc ch´ng), dˆ’ d o ˙ ` ´ ˙ ’a e o u ¯e ¯ e ¯. e. . . µ = {v0 , v1 , v2 , . . . , vk }. 23
Du.`.ng d v` mach -o 1.3.2 ¯i a . Gia su. v0 , vk l` c´c d ınh cua d` thi c´ hu.´.ng G := (V, E ). Du.`.ng d i µ t`. v0 dˆn vk d ˆ d`i -o ´ ˙˙ ’’ a a ¯˙ ’ ˙ ¯o . o o ’ˆ ¯ u ¯e ¯o a . ´t d` u t`. v0 v` kˆt th´c tai vk , ´ ¯˙’ k l` mˆt d˜y xen k˜ (k + 1) d ınh v` k cung bˇ ¯ˆ u aoa e a aa ae u. . µ := {v0 , e1 , v1 , e2 , v2 , . . . , vk−1 , ek , vk }, -e ˙ trong d ´ cung ei liˆn thuˆc c´c d ınh vi−1 v` vi , i = 1, 2, . . . , k. Dˆ’ gian tiˆn, ta c´ thˆ’ k´ ˙’ ˙ o a ¯˙ ’ ¯o e a e o ey . . .`.ng d i µ l` {e , e , . . . , e }. hiˆu d u o e¯ ¯ a 12 . k Do d o trong H` 1.12 d˜y c´c cung ¯´ ınh aa µ1 := {e6 , e5 , e9 , e8 , e4 } µ2 := {e1 , e6 , e5 , e9 } µ3 := {e1 , e6 , e5 , e9 , e10 , e6 , e4 } l` c´c d u.`.ng d i. aa ¯o ¯ Du.`.ng d i l` d o.n gian nˆu khˆng ch´.a cung n`o qu´ mˆt lˆn. Suy ra c´c d u.`.ng d i -o ´ a o` ˙ ’ ¯ a¯ e o u a .a a ¯o ¯ .n gian, nhu.ng d u.`.ng d i µ khˆng d o.n gian do n´ su. dung cung e hai lˆn. ` ˙ ’ ˙ ’ o˙ .’ µ1 , µ2 l` d o a¯ ¯o ¯3o¯ a 6 Du.`.ng d i l` so. cˆ p nˆu khˆng d i qua d ınh n`o qu´ mˆt lˆn. Khi d o d u.`.ng d i µ2 l` -o ´´ a o` ¯˙’ ¯a ae o¯ a .a ¯´ ¯ o ¯ a . cˆ p nhu.ng c´c d u.`.ng d i µ v` µ l` khˆng so. cˆ p. Hiˆ’n nhiˆn, d u.`.ng d i so. cˆ p l` d o.n ˙ ´ ´ ´ so a a ¯o ¯ 1 a 3a o a e e ¯o ¯ a a¯ gian nhu.ng ngu.o.c lai khˆng nhˆ t thiˆt d ung. Chˇng han, ch´ y rˇ ng d u.`.ng d i µ1 l` d o.n ˙ ’ u´ ` ´ ´ ˙ ’ o a e ¯´ a a ¯o ¯ a¯ .. . ˙ n nhu.ng khˆng so. cˆ p, d u.`.ng d i µ2 v`.a d o.n gian v` v`.a so. cˆ p, d u.`.ng d i µ3 khˆng ´ ¯o ´ ¯o ’ ˙ ’ au gia o a ¯ u¯ a ¯ o d o.n gian c˜ng khˆng so. cˆ p. ´ ˙u ’ ¯ o a Ch´ y rˇ ng, kh´i niˆm dˆy chuyˆn l` ban sao khˆng c´ hu.´.ng cua d u.`.ng d i v` ´p u´ ` `a˙ ’ ˙ ¯o ’ a ae a e o o o ¯ aa . ` thi m` khˆng dˆ’ y dˆn hu.´.ng cua c´c cung. ˙ ´ ¯e ´ ˙a ’ dung cho c´c d ˆ . a o ¯e a ¯o o . Du.`.ng d i c˜ng c´ thˆ’ d u.o.c biˆ’u diˆn bo.i d˜y c´c d ınh m` ch´ng d i qua trong tru.`.ng -o ˙ ˙ ˜ ˙ a a ¯˙ ’ ’ ¯u o e¯ . e e au¯ o .p khˆng c´ cung song song (t´.c hai cung c´ c`ng gˆc v` c`ng ngon). Do d o, d u.`.ng d i ´ au ho o o u ou o ¯´ ¯ o ¯ . . µ1 c´ thˆ’ biˆ’u diˆn bo.i d˜y d ınh {v2 , v5 , v4 , v3 , v5 , v6 }. ˙˙ ˜ ˙ a ¯˙ ’ ’ oee e Mach l` mˆt d u.`.ng d i {e1 , e2 , . . . , ek } trong d o d ınh gˆc cua cung e1 tr`ng v´.i d ınh ´’ ¯´ ¯˙ ’ o˙ o ¯˙ ’ a o ¯o ¯ u . . ˙ a cung ek . Do d ´ d u.`.ng d i {e5 , e9 , e10 , e6 } trong H` 1.12 l` mach. ’ ngon cu ¯o ¯ o ¯ ınh a. . 1.3.3 T´ liˆn thˆng ınh e o D` thi vˆ hu.´.ng goi l` liˆn thˆng nˆu tˆ t ca c´c cˇp d ınh vi v` vj tˆn tai dˆy chuyˆn t`. vi -ˆ . o o ´´’ `.a `u e a ˙ a a ¯˙ ’ o .ae o a o e . ´ ´ ’´ a` . ` ´ e a ˙e ¯˙ ’ dˆn vj . Quan hˆ vi Rvj nˆu v` chı nˆu vi = vj hoˇc tˆn tai mˆt dˆy chuyˆn nˆi hai d ınh vi ¯e e o oa eo . . . .o.ng d u.o.ng (phan xa, d ˆi x´.ng v` bˇc cˆu). ´a ´ aa` ˙ ’ v` vj l` quan hˆ tu a a e ¯ . ¯o u . 24
v2 • ...... . ...... .... . ... . .... . ... .. ... . . ..... ... . . ..... . ... .. . ... ... . ... ... ... ... . . . e10 ... ... ... . . ... .. . ... ... . ... .. e1 ... ... . ... . ... . ... ... . ... ... . . . . .. . ... ... .. ... . .... . . .... .. . ... .... .. .. . . .. .... .. .. . . . . ... ... ... . .. ... . . ... . ... .. . . ... .. ... . ... . ... . .. . . ... .. ... . ... ... . . . . .. ... ... . ... ... .. . . ... . ... . . . ... ... .. . ... ... . ... v1 • • v3 . . . .. ... . ... ... . .. .. . . ... . . .. .... e3 . . .. . . ... .. ..... ... . . . . .. . . ..... .. . ..... ... . . .. . . . . .. . . . .. ..... . ..... .. . . .. . . .. . . .. . ..... . . . ..... .. .. . . .. . . . . .. .. .. . . . ..... . ..... .. .. . . . . . . . . . .. . .. . . ......... ..... . .. .. . . . .. ... . e2 e7 e9 .. . . .. .. .. .. . .... . ....... .. .. .. . . . . .. . . .. .. ...... ...... . .. .. . .. .. . ... .. . . . . ..... ..... . .. .. . . . . . . . .. . . . .. .. ..... ..... . . . .. .. . . . . . . .... ... . .. .. . . . ... .. . . . ... ..... . . . . .. . .. ..... ..... . .. .. . . . . . . . . .. ......... .. . . . .... .. . .... .. . .. . .. . . ... v6 • e6 • v4 .. .. .. . .. . ..... . ... .. . . ... . . . .. . . .. .. ... e8 .. .. ... . . ... ... . . .. . ... .. ... . ... . ... . . . .. ... . ... ... .. ... . . . ... . . ... ... .. ... . . ... . ... ... .. ... . .. . ... ... ... . ... .. . ... .. ... . ... ... . ... .. e4 e5 . ... ... .. ... . ... . .... .. .. . ... . ..... .. . ... . ... . .... .... . ... . .. ... . .. ... ... . ... ... . .. .... ... . . ... ..... ... . ... . ... ..... . ... ... . .. ... ... . ... . .. ..... ... ... . ....... . ... . ..... ... ..... .. • ....... .... . v5 H` 1.12: ınh L´.p tu.o.ng d u.o.ng trˆn V x´c d .nh bo.i quan hˆ tu.o.ng d u.o.ng R phˆn hoach tˆp V ˙ ’ o ¯ e a ¯i e ¯ a a . . . .i nhau V , V , . . . , V . Sˆ p goi l` sˆ th`nh phˆn liˆn thˆng cua d` thi. ´ ´a ` ˙ ¯o . ’ˆ th`nh c´c tˆp con r` a aa o o . ao ae o . 1 2 p ` Theo d inh ngh˜ d` thi liˆn thˆng nˆu v` chı nˆu sˆ th`nh phˆn liˆn thˆng bˇ ng mˆt. C´c ´ ’´ ´ ` e a ˙e o a ¯. ıa, ¯ˆ . e o o ae o a o a . ` thi con G1 , G2 , . . . , Gp sinh bo.i c´c tˆp con V1 , V2 , . . . , Vp goi l` c´c th`nh phˆn liˆn thˆng `e ˙aa ’ do . ¯ˆ . aa a a o . ˜ cua d` thi. Mˆ i th`nh phˆn liˆn thˆng l` mˆt d` thi liˆn thˆng. ` ˙ ¯ˆ . ’o o a ae o a o ¯ˆ . e o o . H` 1.13 minh hoa d` thi c´ ba th`nh phˆn liˆn thˆng. ` ınh . ¯ˆ . o o a ae o v1 v5 v3 •... • •.. .. . .. . .. .. ... . .. .. .. ... . . . . ... . .. . . ... .. . . . . .. .... . .. . .. . .. ..... .. .. . . . . . .. . .... .. .. . . .. . ... . . . . . .. ... . ... .. . . .. . . . . . . . ... . .. ... . . . .. .. . . . . ... . . . ... . .. . . .. .. . . . . ... . ... . . . .. . . . .. ... .. . . . . ... . . . .. . .. . ... . .. . ... .. . . . . . . ... . . . ... .. .. . . . . .. . . . ... . ... . . .. .. . . . . .. . ... . . ... . . . .. . .. . . . ... .. . ... . . . . . .. . . ... .. . . . ... . .. . . .. . . . .. ... . ... . . .. . . . .. . ... . . .. . ... . . . . .. . . . .. ... . ... . . .. . . . . .. . . . ... .. . ... . . .. . . . . . ... . .. . ... . .. . . .. . . . . . ... ... . . . .. .. .. .. . . .. .. .. ... . ... . .. .. .. .. . ... .. ... .. . . .. . . • • • • • . ... . ... ....................................................... . .. . .................................................... . . . . . v2 v4 v7 v8 v6 -ˆ . o H` 1.13: D` thi c´ ba th`nh phˆn liˆn thˆng. ` ınh o a ae o X´c d .nh sˆ th`nh phˆn liˆn thˆng cua d` thi l` mˆt trong nh˜.ng b`i to´n co. ban cua ´ `e ˙ ¯ˆ . a o ’o ˙ ’ ˙ ’ a ¯i oa a o u aa . ´t d` thi v` c´ nhiˆu u.ng dung trong thu.c tiˆn; chˇng han, x´c d .nh t´ liˆn thˆng ˜ ˙ ’ `´ l´ thuyˆ ¯o . a o y eˆ e e a a ¯i ınh e o . . . ˙ ’ cua mach d iˆn, mang d iˆn thoai, v.v. ¯e ¯e . . . . . Ch´ng ta s˜ tr` b`y mˆt sˆ thuˆt to´n c´ th`.i gian O(m) giai b`i to´n n`y v` n´ .´ ˙a ’ u e ınh a oo a aoo a a ıo . 25
cho ph´p t` l`.i giai cua mˆt sˆ b`i to´n kh´c. .´ ˙˙ ’’ e ım o ooa a a Bˇt d` u v´.i d ınh n`o d o cua d` thi, ch´ng ta liˆt kˆ c´c d ınh theo th´. tu. cua thuˆt ´ˆ a ¯a o ¯˙ ’ a ¯´ ˙ ¯o . ’ˆ e e a ¯˙ ’ u.˙ ’ u a . . .c l` ch´ng ta d i, d` u tiˆn, xa nhˆ t c´ thˆ’ d u.o.c trˆn d` thi ˙¯ . ´ `a ´ to´n t` kiˆm theo chiˆu sˆu, t´ a u a ım e e u ¯ ¯ˆa e aoe e ¯o . ˆ ınh, v` sau d ´ tro. vˆ vi tr´ r˜ nh´nh gˆn d ˆy nhˆ t m` ch´ng ta ¯o ˙ ` . ı e a ` ¯a ´au ’e m` khˆng tao th`nh chu tr` ao a a a a . . vˆ d ınh xuˆ t ph´t. Do d ´ tˆp c´c d ınh bˇt gˇp s˜ ´. d a bo qua, v` tiˆp tuc cho dˆn khi tro ` ¯˙ ´ ´ ´ ¯˜ ˙ ’ ˙e’ ’ ¯o a a ¯ ˙ ’ ae . ¯e a a aae . tao th`nh th`nh phˆn liˆn thˆng d` u tiˆn. ` a a ae o ¯ˆ a e . Nˆu tˆ t ca c´c d ınh cua d` thi d u.o.c duyˆt th` d` thi liˆn thˆng; ngu.o.c lai, ch´ng ta ´´’ e a ˙ a ¯˙ ’ ˙ ¯ˆ . ¯ . ’o e ı ¯o . e ˆ o u . .. .i d` u lai thu tuc trˆn v´.i mˆt d ınh m´.i chu.a d u.o.c viˆng thˇm; do d o ta xˆy du.ng d u.o.c ´ ˙a ’ ˙. ’ e o o ¯˙ .’ kho ¯ˆ . o ¯. e a ¯´ a ¯. . ` n liˆn thˆng th´. hai, v` vˆn vˆn. th`nh phˆ e a a o u aa a Thuˆt to´n du.´.i d ay tr` b`y giai d oan d` u tiˆn, t´.c l` t` th`nh phˆn liˆn thˆng ` a a o ¯ˆ ınh a ¯ . ¯a ˆ e u a ım a ae o . .a mˆt d ınh d a cho-nˆu th`nh phˆn n`y ch´.a tˆ t ca c´c d ınh cua d` thi th` d` thi liˆn ´ ` ´’ o ¯˙ . ’ ¯˜ u a ˙ a ¯˙ ’ ˙ ¯o . ı ¯o . e ’ˆ ch´ u e a aa ˆ thˆng. o ´ˆ` K´ hiˆu num(i) l` sˆ hiˆu cua d ınh vi trong qu´ tr` t` kiˆm. Nˆu ta bˇt d` u bˇ ng ´. ´ ´ a o e ˙ ¯˙ ’’ ye a ınh ım e e a ¯a a . ˙nh s th` d at num(s) = 1. K´ hiˆu P (i) l` d ınh d u.ng liˆn tru.´.c d ınh vi trong cˆy c´ gˆc ` ´ ’ ˙ ’ ¯´ ˙ ’ dı ¯ ı ¯ˇ ye a¯ e o¯ a oo . . .o.ng 4) d u.o.c xˆy du.ng trong qu´ tr` thu.c hiˆn thuˆt to´n. (xem Chu ¯. a a ınh . e a a . . . X´t d` thi d u.o.c biˆ’u diˆn bo.i ´nh xa d a tri Γ. Dˇt d+ l` sˆ c´c d ınh kˆ d ınh vi : d+ := - a i a o a ¯˙ ˙ ˜ ´ ` ¯˙ ˙a ’ ’ e’ e ¯o . ¯ . ˆ e e .¯ . . i .i mˆ i k = 1, 2, . . . , n, k´ hiˆu Γ (v ) l` d ınh th´. k trong tˆp Γ(v ). ˜ y e k i a ¯˙ ’ #Γ(vi ). V´ o o u a . . i Dˆ’ thu.c hiˆn t` kiˆm trˆn d` thi, ch´ng ta cˆn mˆi giai d oan cua thuˆt to´n chı sˆ -e . ˙ ˜ ´ ` ’´ ˙ ’ ˙o e ım e e ¯o . ˆ u a o ¯. a a . . ˙ a d ınh d u.o.c viˆng thˇm cuˆi c`ng t`. d ınh vi . Do d ´ ta bˇt d` u v´.i n(i) = 0. ´ ¯a o ´ ´u ’ ¯˙ ¯ . ’ ˙ ’ n(i) cu e a o u¯ ¯o aˆ Du.´.i d ˆy l` thuˆt to´n (dang khˆng dˆ qui) cua Tr´maux d u.a ra nˇ m 1882 v` sau d o ` ˙ ’ o ¯a a a a o ¯e e ¯ a a ¯´ . . . .o.c Tarjan cai tiˆn [53]. ’´ ˙e du . ¯ Thuˆt to´n Tr´maux-Tarjan t` th`nh phˆn liˆn thˆng ch´.a d ˙nh s. ` ’ a a e ım a a e o u ¯ı . 1. [Kho.i tao] Dˇt P (i) = 0, d+ := #Γ(vi ) v` n(i) = 0 v´.i moi d ınh vi , i = 1, 2, . . . , n; ˙ . -a ’ . ¯˙ ’ a o . i k = 0, num(s) = 1, P (s) = s (tu` y, kh´c khˆng), i = s. y´ a o 2. [Bu.´.c lˇp] Trong khi (n(i) = d(i)) hoˇc (i = s) thu.c hiˆn oa a e . . . . • Nˆu n(i) = d(i) d at i = P (i) (lˆn ngu.o.c); ´ ` e ¯ˇ a . . .o.c lai, d ˇt n(i) = n(i) + 1 (viˆng thˇm d ınh kˆ tiˆp trong Γ(v )), v` j = ´ ´´ a ¯˙ ’ • ngu . . ¯a e ee a . i ´u P (j ) = 0 th` g´n P (j ) = i, i = j, k = k + 1, num(i) = k. Γn(i) (vi ). Nˆe ıa Kˆt th´c thuˆt to´n, nˆu k = n th` d` thi liˆn thˆng; ngu.o.c lai th`nh phˆn liˆn thˆng ch´.a ´ ´ ` e u a a e ı ¯o . e ˆ o a ae o u . .. . 1 dˆn k. ` ´ ¯˙’ ¯˙ ’ d ınh s gˆm k d ınh m` num(i) nhˆn c´c gi´ tri t` ¯e o a aa a .u . 26
V´ du 1.3.1 X´t d` thi trong H` 1.14. C´c d ınh s˜ d u.o.c viˆng thˇm theo th´. tu. 1, 4, 2, 3 ´ a ¯˙ ’ ı. e ¯o . ˆ ınh e¯ . e a u. v` 5. Qu´ tr` t` kiˆm c´ thˆ’ biˆ’u diˆn th`nh cˆy c´ gˆc (d ınh gˆc l` v1 ) trong H` ˙˙ ˜ ´ ´ ´ a o o ¯˙ ’ a a ınh ım e oee e a oa ınh v5 • . .. ... ... ... ... ... .. ... ... .. .. ... ... ... ... ... ... ... ... .. .. ... ... ... ... ... ... ... ... v4 . ... ... ... ... v1 • • v2 • ............................................................................................................ ............................................................................................................ .. . . ... ... .. . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... .. ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... .... ... .... • .... .... v3 H` 1.14: ınh 1.15. v5 .• ... .. ... ... .. ... 5 .. ... ... ... ... ... .. . ... ... ... ... ..... ... .. .. . ... ... .. .. ... ... ... ... v4 ... ... ... ... v1 • • v2 .. .. • ............................................................................................................ ............................................................................................................ . . . .. . . .. .. . . ... .. ... ... ... ... . 1 2 3 ... ... ... ... ... ... . ... .. ... ... ... ... . .... .. ... ... ... ... .. . ... .... ... ... . ... .... ... ... ... ... . .. .. ... ... ... ... . ... 4 ... ... ... ... ... . ... ..... ........ • . v3 H` 1.15: ınh ´ ` Thuˆt to´n t` kiˆm theo chiˆu sˆu a a ım e ea . ´ a ¯˙ ’ 1. Thˇm d ınh xuˆ t ph´t s. a a 2. V´.i mˆ i d ınh w kˆ v´.i v (c´ hu.´.ng t`. v dˆn w) l`m c´c bu.´.c sau: ˜’ `o ´ o o ¯˙ e oo u ¯e a a o Nˆu w chu.a d u.o.c thˇm, ´p dung thuˆt to´n t` kiˆm theo chiˆu sˆu v´.i w nhu. l` ´ ´ `ao e ¯. aa a a ım e e a . . ´ ¯˙’ d ınh xuˆ t ph´t. a a Trong c´ch t` kiˆm theo chiˆu sˆu, ta d i theo d u.`.ng t`. d ınh xuˆ t ph´t cho dˆn khi ´ `a ´ ´ u ¯˙ ’ a ım e e ¯ ¯o a a ¯e .o.c viˆng thˇm. Sau d ´ ta quay lai d ınh ´ ´’ ` o ¯˜ ¯ ´ o ¯˙ .’ o a ˙ a ¯˙ ’ . ¯˙’ d at dˆn mˆt d ınh c´ tˆ t ca c´c d ınh kˆ n´ d a d u . ¯ . ¯e e e a ¯o 27
cuˆi c`ng v`.a d u.o.c thˇm doc theo d u.`.ng n`y sao cho c´c d ınh kˆ v´.i n´ (c´ hu.´.ng t`. ´ `ooo a ¯˙ ’ ou u ¯. a ¯o a e o u . .`.ng ho.p d` thi c´ hu.´.ng) c´ thˆ’ thˇm d u.o.c. Dˆ’ c´ thˆ’ quay tro. lai, ta o e a ¯ . -e o e ˙ ˙ ˙ ˙. ’ n´ d i ra trong tru o o¯ ¯o . o o ˆ . lu.u tr˜. c´c d ınh doc theo d u.`.ng n`y trong mˆt ngˇn xˆp. Nˆu thu tuc d u.o.c viˆt dang dˆ ´ ´ ´ u a ¯˙ ’ ˙. ¯. ’ ¯o a o ae e e. ¯e . . . ´p n`y d u.o.c bao tr` mˆt c´ch tu. d ong; trong tru.`.ng ho.p ngu.o.c lai, cˆn mˆt ` ˙ ’ quy th` ngˇn xˆ a ¯ . ıae ıoa . ¯ˆ o ..a o . . . . mang d ´nh dˆ u c´c d ınh d ˜ d u.o.c viˆng thˇm. ´ ´ ˙ ’ a a ¯ ˙ ¯a ¯ . ’ ¯a e a ´ ` Thuˆt to´n t` kiˆm theo chiˆu rˆng a a ım e eo . . Trong thuˆt to´n n`y, ch´ng ta thˇm c´c d ınh theo t`.ng m´.c mˆt, v` khi thˇm mˆt d ınh a ¯˙’ o ¯˙ .’ a aa u a u u o a a . . . m´.c n`o d o, ta phai lu.u tr˜. n´ dˆ’ c´ thˆ’ tro. lai khi d i hˆt mˆt m´.c, v` vˆy c´ thˆ’ thˇm ˙o e ˙. ˙’ ˙ ´o ˙ ’ ˙ ’ o u a ¯´ u o ¯e ¯e u ıa o e a . . .´.i d ay d`ng mˆt h`ng d o.i theo `˙ o ´ `o a ¯˙’ e’ c´c d ınh kˆ cua n´. Thuˆt to´n t` kiˆm theo chiˆu rˆng du o ¯ˆ u a a ım e e. o a ¯. . . c´ch n`y. a a ´ a ¯˙ ’ 1. Thˇm d ınh xuˆ t ph´t. a a 2. Kho.i d ong mˆt h`ng d o.i chı ch´.a d ınh xuˆ t ph´t. ´ ˙ ¯ˆ ’. ˙ u ¯˙ ’ ’ o a ¯. a a . 3. Trong khi h`ng d o.i khˆng rˆ ng l`m c´c bu.´.c sau: ˜ a ¯. o o a a o Lˆ y mˆt d ınh v t`. h`ng d o.i. ´ o ¯˙ .’ a u a ¯. V´.i tˆ t ca c´c d ınh w kˆ v´.i v, l`m c´c bu.´.c sau: ´’ `o o a ˙ a ¯˙ ’ e a a o .a d u.o.c thˇm) th` ´ Nˆu (w chu ¯ . e a ı: Thˇm w. a Thˆm w v`o h`ng d o.i. e a a ¯. C´c thuˆt to´n t` kiˆm theo chiˆu rˆng v` t` kiˆm theo chiˆu sˆu l` rˆ t co. ban cho ´ `o ´ ` a aa ´ ˙ ’ a a a ım e e. a ım e e . . l´ d` thi. V´ du, dˆ’ duyˆt mˆt d` thi, ta c´ thˆ’ ´p dung nhiˆu nhiˆu thuˆt to´n kh´c dˆ’ xu y ¯o . ı . ¯e ˙’ ˙ ˙ ` ` a ¯e ˙ e a a ˆ e o ¯o . .ˆ o ea e . . . ` n mˆt trong c´c c´ch n´i trˆn, chon c´c d ınh xuˆ t ph´t m´.i nˆu cˆn thiˆt, cho dˆn khi ´ ´` ´ ´ ˙ ’ lˆ a o aa oe . a¯ a a oea e ¯e . tˆ t ca c´c d ınh d u.o.c thˇm. ´’ a ˙ a ¯˙ ¯ . ’ a ` 1.3.4 Cˆu, k −liˆn thˆng a e o Diˆ’m kh´.p cua d` thi l` mˆt d ınh m` xo´ n´ s˜ tˇng sˆ th`nh phˆn liˆn thˆng; cˆu l` canh -e ˙ ´ ` ` a. ˙ ¯o . a o ¯˙ ’ˆ .’ o a aoea oa ae o a .o.ng tu.o.ng tu.. D` thi trong H` 1.14 c´ mˆt d iˆ’m kh´.p l` d ınh -ˆ . ˙ m` xo´ n´ c˜ng c´ anh hu ˙ o˙’ ’ o a ¯˙ ’ a aou o ınh o o ¯e . . ` aa . v4 v` hai cˆu l` c´c canh (v1 , v4 ) v` (v4 , v5 ). a a a ınh, c´c d ınh khˆng phai l` d ınh treo, t´.c V´ du 1.3.2 Trong mˆt d` thi khˆng c´ chu tr` a ¯˙ ’ ˙ a ¯˙ ’ ’ ı. o ¯o . o .ˆ o o u .p. Ngu.o.c lai, d` thi c´ chu tr` Hamilton (xem Phˆn 5.3) d ınh c´ bˆc ≥ 2, l` d iˆ’m kh´ ˙ ` ¯˙’ oa a ¯e o ¯ˆ . o o ınh a . .. khˆng c´ d iˆ’m kh´.p. ˙ o o ¯e o 28
V´ du 1.3.3 [Mang thˆng tin] Gia su. V l` tˆp ho.p nh˜.ng ngu.`.i thuˆc mˆt tˆ’ ch´.c n`o ˙ ˙˙ ’’ ı. o aa u o o ooua . . . . . .`.i a v` b c´ thˆ’ b´o tin v´.i nhau. Nh˜.ng ngu.`.i liˆn lac l` ˙ ´ d o; ta d ˇt (a, b) ∈ E nˆu ngu o ¯´ ¯a e a o ea o u oe.a . .ng d iˆ’m kh´.p. Nh˜.ng ngu.`.i d o l` nh˜.ng mˇt x´ quan trong, v` mˆ t ho s˜ ph´ v˜. ˙ ´ ´ nh˜u ¯e o u o ¯´ a u a ıch ı a .e ao . ´ng nhˆ t v` su. liˆn kˆt cua tˆ’ ch´.c. ˙ ´ a.e e ˙ o u ´’ t´ thˆ ınh o a Dinh l´ 1.3.4 Gia su. G = (V, E ) l` d` thi liˆn thˆng. Khi d ´ d ı’nh v ∈ V l` d iˆ’m kh´.p -. ˙ ˙˙ ’’ ¯o ¯ ˙ y a ¯ˆ . e o o a ¯e o ´u v` chı’ nˆu tˆn tai hai d ı’nh a v` b sao cho moi dˆy chuyˆn nˆi a v´.i b d` u d i qua v. ˙e` . ´o ` ´ ˙ nˆ a e ¯ a .a eo o ¯ˆ ¯ e Ch´.ng minh. Diˆu kiˆn cˆn. Nˆu d` thi con sinh bo.i tˆp ho.p V \ {v } khˆng liˆn thˆng th` -` e` ´ˆ ˙a ’. u e .a e ¯o . o e o ı . .a ´ nhˆ t hai th`nh phˆn C v` C ; gia su. a l` mˆt d ınh n`o d o cua C v` b l` mˆt ´ ` ˙˙ ’’ ˙ ’ ˙’ n´ ch´ ıt a ou a a a a o¯ a ¯´ aao . . d ınh n`o d o cua C. Trong d` thi liˆn thˆng ban d` u G moi dˆy chuyˆn bˆ t k` nˆi a v´.i b ` ´ ´ ¯˙’ a ¯´ ˙ ’ ¯ˆ . e o o ¯ˆ a a e a yo o . d` u phai d i qua v. ˙¯ ’ ¯ˆe Diˆu kiˆn d u. Nˆu mˆt dˆy chuyˆn bˆ t k` nˆi a v´.i b d` u d i qua v th` d` thi con sinh ra -` ´ ` ´ ´ e ¯˙ ’ e e oa e a yo o ¯ˆ ¯ e ı ¯ˆ . o . . .i V \ {v } khˆng thˆ’ liˆn thˆng; bo.i vˆy d ınh v l` d iˆ’m kh´.p. ˙ ˙ ˙ ’ ˙ a ¯˙ ’. ’ bo o ee o a ¯e o Ta c´ thˆ’ d .nh ngh˜ d` thi n d ınh (n ≥ 3) l` 2−liˆn thˆng hay d` thi khˆng t´ch ˙ ıa: ¯ˆ . ¯˙ ’ o e ¯i o a e o ¯ˆ . o o a .o.c nˆu v` chı nˆu n´ liˆn thˆng v` khˆng c´ d iˆ’m kh´.p. C´c d` thi con 2−liˆn thˆng cu.c ˙ ´ ’´ du . e a ˙ e o e ¯ o ao o ¯e o a ¯o . ˆ e o . ` ¯. ˙ ’ ˙ ’ ˙ ’ d ai cua G tao th`nh mˆt phˆn hoach cua G, v` goi l` c´c th`nh phˆn 2−liˆn thˆng cua G. a o a a.aa a a e o . . . Dˆ’ t` c´c d iˆ’m kh´.p v` c´c th`nh phˆn 2−liˆn thˆng ta c´ thˆ’ su. dung thuˆt to´n - e ım a ¯ e ˙ ˙ ˙’ ` o e˙ . o aa a a e o a a . ´ `a t` kiˆm theo chiˆu sˆu. ım e e V´.i mˆi d ınh vi , x´t tˆp D(i) c´c d ınh d u.ng liˆn tru.´.c d ınh vi trong cˆy T x´c d .nh ˜’ ` o ¯˙ a ¯˙ ’ ¯´ o ¯˙ ’ o ea e a a ¯i . .i thuˆt to´n t` kiˆm theo chiˆu sˆu. Khi d ´, v´.i moi d ınh v ∈ D(i) ta c´ ´ `a ˙ ’ ¯˙ ’ bo a a ım e e ¯o o o . . j l(j ) = min (num(k )) k∈Γ(vj ) l` sˆ nho nhˆ t d u.o.c g´n cho d ınh kˆ v´.i d ınh vj trong G. Bˆy gi`. ta d .nh ngh˜ mˆt chı sˆ ´ ˙ a¯. a ´ ` o ¯˙ ’´ ’ ¯˙’ ’ ˙o ao e a o ¯i ıa o . .i m´o inf(i) := min l(j ). vj ∈D(i) Do d ´ chı sˆ n`y tu.o.ng u.ng cu.c tiˆ’u cua num(i) v` sˆ nho nhˆ t d u.o.c g´n cho c´c ˙ ’´ ´ ´ ¯o ˙ o a ˙ ’ ˙ ’ ´ e ao a¯. a a . .o.c bˇ ng d ung mˆt canh t`. mˆt trong c´c hˆu duˆ cua v trong cˆy ˙nh m` c´ thˆ’ dˆn d u . ` ˙ ¯e ¯ ´ ’ ˙i ’ dı ¯ ao e a ¯´ o. uo aa e a . . . . T. Do d o, trong V´ du 1.3.1 (H` 1.15), d ınh v2 c´ d ung mˆt d ınh tru.´.c liˆn kˆ l` d ınh o ` ` a ¯˙ ¯˙’ o ¯˙ .’ ’ ¯´ ı. ınh o ¯´ ee v4 , v` do d o inf(2) = num(4) = 2. a ¯´ Ch´ y rˇ ng inf(i) ≤ num(i) v` kho.i d` u t`. tiˆn bˆi cua vi n´ c´ thˆ’ tro. vˆ vi . ˙’e u´ ` ˙ ¯a u ` ´’ oo e ˙` ’ˆ eo˙ a ı 29
Ho.n n˜.a, dˆ d`ng chı ra rˇ ng, nˆu inf(i) = num(i) th` d ınh vi l` d iˆ’m kh´.p cua d` ˙ ˜a ` ´ ˙ ’ ı ¯˙ ’ ˙ ¯o ’ˆ u e a e a ¯e o . lai d ınh v tao th`nh mˆt th`nh phˆn 2−liˆn ´. ` thi. Ngo`i ra, c´c d ınh bˇt gˇp khi duyˆt tro . ¯˙ a ¯˙ ’ ˙’ ’ a aa e a o a a e . . i. . thˆng. o Thuˆt to´n du.´.i d ay tr` b`y phu.o.ng ph´p x´c d inh c´c d iˆ’m kh´.p cua d` thi liˆn ˙ ˙ ¯o . e ’ˆ a a o ¯ˆ ınh a a a ¯. a ¯e o . . d ınh s. ´ thˆng xuˆ t ph´t t` ¯˙ au’ o a Thuˆt to´n Tarjan t` d e’m kh´.p cua d` thi liˆn thˆng xuˆ t ph´t t`. d ˙nh s ˙ ´ ˙ ¯ˆ . e ’ ’ a a ım ¯iˆ o o o a a u ¯ı . 1. [Kho.i tao] Dˇt P (i) = 0, d+ := #Γ(vi ), n(i) = 0 v` inf(i) = ∞ v´.i moi d ınh vi , i = ˙ . -a ’ . ¯˙ ’ a o . i 1, 2, . . . , n; k = 0, num(s) = 1, P (s) = s, i = s. 2. [Bu.´.c lˇp] Trong khi (n(i) = d(i)) hoˇc (i = s) thu.c hiˆn oa a e . . . . ´ • Nˆu n(i) = d(i) d at e ¯ˇ. q = inf(i), i = P (i), inf(i) = min(q, inf(i)). Nˆu inf(i) =num(i) th` vi l` d iˆ’m kh´.p (v` ta c´ thˆ’ x´c d .nh th`nh phˆn 2−liˆn ˙ ˙ ´ ` e ı a ¯e o a o e a ¯i a a e thˆng). o • Ngu.o.c lai, t´.c l` n(i) = d(i) (viˆng thˇm d ınh kˆ tiˆp trong Γ(vi )) ´ ´´ a ¯˙ ’ ..ua e ee ´ Nˆu j = P (i) th` g´n n(i) = n(i) + 1, j = Γn(i) (i). e ıa ´ Nˆu P (j ) = 0 th` g´n e ıa inf(i) = min(inf(i), num(i)), P (j ) = i, i = j, k = k + 1, num(i) = k. Ngu.o.c lai nˆu P (j ) = 0 g´n inf(i) = min(inf(i), num(j )). ´ ..e a Dˆ d`ng kiˆ’m tra v´.i v´ du tru.´.c, d ınh v4 l` d iˆ’m kh´.p. Ch´ y rˇ ng c´ thˆ’ x´c d .nh ˙ ˙ ˙ ˜a u´ ` o ¯˙ ’ e e oı. a ¯e o a o e a ¯i .a d ˆ’i Bu.´.c 2 trong Thuˆt to´n Tarjan. ˙ ` ` ˙ ’ th`nh phˆn 2−liˆn thˆng bˇ ng c´ch su ¯o a a e o a a o a a . Mˆnh d` sau l` hiˆ’n nhiˆn: ˙ e ¯ˆ e ae e . Mˆnh d` 1.3.5 C´c thuˆt to´n Tr´maux-Tarjan v` Tarjan c´ th`.i gian O(m). e ¯ˆ e a a a e a oo . . Thiˆt diˆn A ⊂ V cua d` thi liˆn thˆng G l` tˆp con A c´c d ınh sao cho d` thi con ´e ˙ ¯o . e ’ˆ a ¯˙’ e o aa ¯ˆ . o . . .o.c t`. G bˇ ng c´ch xo´ c´c d ınh trong A (v` c´c canh liˆn thuˆc n´) khˆng ` a a ¯˙ ’ GV \A nhˆn d u . u a¯ a a aa . e oo o . . liˆn thˆng. e o -ˆ . . a D` thi goi l` k −liˆn thˆng nˆu v` chı nˆu n´ liˆn thˆng, c´ sˆ d ınh n ≥ k + 1, v` khˆng ´ ’´ ´’ e a ˙e oe o o ¯˙ o e o o ao .a mˆt thiˆt diˆn c´ lu.c lu.o.ng (k − 1). ´ e o. ch´ u o e . . . 30
C´c d` thi con k −liˆn thˆng cu.c d ai cua G tao th`nh mˆt phˆn hoach cua G v` goi . ¯. ˙ ’ ˙ ’ a ¯o . ˆ e o a o a a. . . . ` l` c´c th`nh phˆn k −liˆn thˆng. aa a a e o C´c th`nh phˆn 3−liˆn thˆng cua d` thi c´ thˆ’ nhˆn d u.o.c trong th`.i gian O(m) bˇ ng ˙. ` ` ˙ ¯o . o e a ¯ . ’ˆ a a a e o o a .o.ng tu. cua Tarjan. ˙ ’ thuˆt to´n tu a a . . - ¯ˆ . e ˜ Da d` thi liˆn thˆng G goi l` k −canh liˆn thˆng nˆu n´ vˆ n c`n liˆn thˆng khi xo´ d i ´ o o .a e o e oa o e o a¯ . .n k canh. ´ ho ıt . Do d o, d a d` thi l` 2−liˆn thˆng nˆu v` chı nˆu n´ liˆn thˆng v` khˆng ch´.a cˆu. ´ ’´ oe u` e a ˙e ¯´ ¯ ¯o . a ˆ e o o ao a .a d o’i lai thuˆt to´n Tarjan, ta c´ thˆ’ x´c d inh c´c cˆu trong th`.i gian O(m). ˙ ˙ ` a` ˙ ’ Bˇ ng c´ch su ¯ˆ . a a a a o e a ¯. a o . ` u u.ng dung trong thu.c tˆ: mang d iˆn, d iˆn thoai, v.v., ´ X´t t´ 2−canh liˆn thˆng c´ nhiˆ ´ e ınh e o o e .e ¯e ¯e . . . . . . ˙ ’ phai 2−canh liˆn thˆng! e o . -ˆ . e D` thi liˆn thˆng manh 1.3.5 o o . D` thi c´ hu.´.ng goi l` liˆn thˆng manh nˆu tˆ t ca c´c cˇp d ınh vi v` vj tˆn tai d u.`.ng d i -ˆ . o o ´´’ ` . ¯o e a ˙ a a ¯˙ ’ o .ae o a o ¯ . . . v d ˆn v . ´ t` i ¯e j u X´t quan hˆ vi Rvj nˆu v` chı nˆu hoˇc vi = vj hoˇc tˆn tai d u.`.ng d i t`. d ınh vi dˆn ´ ’´ a ` . ¯o ´ e a ˙e ¯ u ¯˙ ’ e e a .o ¯e . . .`.ng d i t`. d ınh v dˆn d ınh v . Dˆ thˆ y d ay l` quan hˆ tu.o.ng d u.o.ng (phan ˜ a ¯ˆ a ´ ¯˙ e´ ¯˙’ ¯ u ¯˙ ’ ’ ˙ ’ d ınh vj v` d u o a¯ j ¯e e ¯ . i .ng v` bˇc cˆu). ´a ´ aa` xa, d oi x´ . ¯ˆ u L´.p tu.o.ng d u.o.ng trˆn V x´c d .nh bo.i quan hˆ tu.o.ng d u.o.ng R phˆn hoach tˆp V ˙ ’ o ¯ e a ¯i e ¯ a a . . . .i nhau V , V , . . . , V . Sˆ p goi l` sˆ th`nh phˆn liˆn thˆng manh cua d` ´ ´ ` ˙ ¯ˆ ’o th`nh c´c tˆp con r` a aa o o ao a ae o . . . 1 2 p .i c´c tˆp con V , V , . . . , V goi l` c´c th`nh phˆn thi. C´c d` thi con G1 , G2 , . . . , Gp sinh bo a a ` ˙ ’ . a ¯o .ˆ p.aa a a . 1 2 liˆn thˆng manh cua G. Theo d inh ngh˜ d` thi liˆn thˆng manh nˆu v` chı nˆu sˆ th`nh ´ ’´ ´ ˙’ e a ˙e o a e o ¯. ıa, ¯o . e ˆ o . . ` ` phˆn liˆn thˆng manh bˇ ng mˆt. ae o a o . . Nhˆn x´t rˇ ng, th`nh phˆn liˆn thˆng manh Cl ch´.a d ınh vl d u.o.c cho bo.i ae` ` u ¯˙ ’ ˙ ’ a a ae o ¯. . . ˆ ˆv Cl = Γvl ∩ Γ−1 , l v` t`. d o suy ra mˆt thuˆt to´n rˆ t d o.n gian th`.i gian d a th´.c O(m) du.a trˆn thuˆt to´n ´ ˙ ’ a u ¯´ o a a a¯ o ¯ u e a a . . . . ´m theo chiˆu sˆu m` c´ thˆ’ su. dung n´ dˆ’ t` Cl . ˙˙ . ˙ ım `a ’ t` kiˆ ım e e ao e o ¯e Do d ´ t´ liˆn thˆng manh dˆ d`ng kiˆ’m tra. Chı cˆn x´t khi n`o Cl ≡ V. (H˜y giai ˙ ˜a ˙` ’a e ˙ ’ ¯o ınh e o e e a a . ` ng ma trˆn). b`i to´n n`y bˇ aaaa a . Nˆu mˇt kh´c, ch´ng ta muˆn t` tˆ t ca c´c th`nh phˆn liˆn thˆng manh, ta s˜ su. ´ ´ ´’ ` o ım a ˙ a e˙ ’ e a a u a ae o . . dung Thuˆt to´n Tarjan. a a . . 31
Thˆt vˆy ta s˜ ch´.ng minh rˇ ng, thuˆt to´n Tarjan ´p dung v´.i c´c d` thi c´ hu.´.ng, ` aa eu a a a a o a ¯o . o o ˆ .. . . ` cho ph´p t` c´c th`nh phˆn liˆn thˆng manh. e ım a a ae o . Ch´ng ta kho.i d` u v´.i thuˆt to´n t` kiˆm theo chiˆu sˆu, nhu. trong c´c thuˆt to´n ´ `a ˙ ¯a o ’ˆ u a a ım e e a a a . . ´m theo chiˆu sˆu v` Tarjan. V´.i mˆ i d ınh vi x´t mˆt chı sˆ m´.i l` sˆ nho nhˆ t cua ˜ ¯˙ `aa ’´ ´˙ ´’ ’ ˙o o ao ’a˙ t` kiˆ ım e e oo e o. chı sˆ d ınh m` c´ thˆ’ dˆn n´ bˇ ng chı mˆt cung t`. mˆt hˆu duˆ cua vi trong cˆy gia pha. ˙´ a o e ¯e o ` ’´’ ˙ o ¯˙ ˙o ’. e˙ .’ ˙ ’ a uoa a .. .i n`y d u.o.c k´ hiˆu l` inf(i). ’´ ˙o o Chı sˆ m´ a ¯ . y e a . ae` ˜a ` ˙ ’ Nhˆn x´t rˇ ng ch´ng ta luˆn luˆn c´ inf(i) ≤ num(i). Dˆ d`ng chı ra rˇ ng khi ch´ng a u o oo e a u . . lai trong cˆy gia pha, th` mˆt d ınh m` xay ra d ˇng th´.c inf(i) = num(i) s˜ phˆn ˙ ’ ˙ ’ ˙ ’ ı o ¯˙ ’ a˙ ’ ta tro . a ¯a u ea . ` thi th`nh ´ nhˆ t hai th`nh phˆn liˆn thˆng manh, v` mˆt trong ch´ng tu.o.ng u.ng ´ `e hoach d ˆ . a ıt a . ¯o a a o ao u ´ . . tˆp c´c d ınh m` d a d u.o.c viˆng thˇm tru.´.c khi t´.i d ınh vi . ´ a a ¯˙ ’ o ¯˙ ’ a ¯˜ ¯ . e a o . -ˆ . D` thi trong H` 1.16 c´ ba th`nh phˆn liˆn thˆng manh: ` o ınh o a ae o . C1 = {a, b, c, d, e}, C6 = {g, f }, C8 = {h}. .. . ......................... ........................ . . ... . ..... .... .... .... .... ... a c e ... ... ... ... ... . ... ... ... ... ... . .. .. .. • • • . ... ..................................................................................... ........................ . . . ............................................................................................................... . .. . .. . .. . . .. .. . .. . ... . .. . . .. . . . . ... . .. ... . .. . .. . . . . . .. ... .. . . . . ... .. . . . . .. .. . . . . .. ... . . . ... . . . . . . ... .. ... . . . .. . . . ... . . . ... . . . . . . . . . . ... . . . ... . . . . . . . . . f . . . . ... . ... . . . . . . . . . . . . . ... . ... . .. . . . . .. ... . ... .... . .. . ... . • . ... . . . .. .. . . .. . .. . . . ..... .. . ..... . ... . . ..... . .. .. . ... . . . . .... . .. .... . ... . . . . ... .. . . . . .... .. .... .. . . . . ... . . . . ... . . .... . . .... . . . . . . ... . . .... . ... .. . .... . . . . . . . . . ... .. .. . ... . . .. . .... . .... . . . . . ... . . . . ... ....... .. .. ...... . . . .. .. . . . .. .. . . . . .... .... .. . . .. . ... .. .. ... . . . . .. .... . . . ... . . .. .. .... . . ..... .... .. . . .. . . . .. . .. . .. .. . . ... .... .. . .. . . ..... .... .. . ... . .... .. . ... .... . .. . .. . ... .. . .. . ................................................................................... .................................. ...... ................................ ........................... ....................... ............................... . .... . • • • ..... . . .. . .. .. ......... ...... . . .. . .. ..... .. ........ . ... . . ... ...................... ... ..... ...................... ..... ... ... . . ... ..... g ..... . ... ... ..... ..... b d ... ... ... ... ..... ...... ... ... ... ..... ..... ... .... . .. ..... ..... ... ... .. .... ..... .... ..... ... .... .. . ...... ..... .. .. .. ... . ... .. .... ...... . ... ... ... ..... ..... ... ... ... ..... ..... ... ... ... ..... ... ..... ... ... ... .... .......... ... .......... ... .. . • ..... .... .......... ... . h H` 1.16: ınh Ch´ng ta su. dung thuˆt ng˜. d` thi thu gon dˆ’ biˆ’u diˆn d` thi G qua quan hˆ liˆn ˙˙ ˜ ¯o . ˙. ’ u a u ¯ˆ . o . ¯e e e ˆ ee . . ` ¯o a ¯ ˙ ’ ˙ ’ ˙ ’ thˆng manh Gr := G/R. Do d ´ c´c d ınh cua Gr l` c´c th`nh phˆn liˆn thˆng manh cua G o aa a ae o . . .a hai d ınh C v` C nˆu v` chı nˆu tˆn tai ´ nhˆ t mˆt cung gi˜.a mˆt a` . e a ˙ e ` . ıt a ´ ’´ o ´ ¯˙’ v` tˆn tai cung gi˜ o u iaj o u o . . ˙nh cua Ci v` Cj trong G. Hiˆ’n nhiˆn d` thi Gr khˆng c´ mach. H` 1.17 l` d` thi thu ˙ ’ ˙ ’ dı ¯ a e e ¯ˆ .o o o. ınh a ¯ˆ . o gon cua d` thi c´ hu.´.ng trong H` 1.16. Nghiˆn c´.u c´c th`nh phˆn liˆn thˆng manh v` ` ˙ ¯o . o o ’ˆ ınh eua a ae o a . . ` thi thu gon l` nh˜.ng b`i to´n thu.c tiˆn quan trong; chˇng han trong mˆi liˆn hˆ v´.i ˜ ˙’ ´e eo t` d ˆ . ım ¯o .au aa e a o . . . . ´ ´ ` ´ u˙ ’ x´ Markov, trong phˆn t´ cˆ u tr´c cua mˆt hˆ thˆng (xem [30]). Phˆn tiˆp theo ch´ng ıch a ıch a oeo a e u .. ˙ cˆp thˆm vˆ vˆ n d` n`y. ’a e ` a ¯ˆ a e´ e ta s˜ dˆ . e ¯e 32
C6 • ... ... .. .. .. . .. .. ... . .. .. . .. .. .. . .. .. .. . .. .. .. . .. .. .. .. .. .. .. . .. .. .. . .. .. .. . . ... ... . ... .. .. . .. .. ... .. .. . .. .. .. . .. .. .. . .. .. . .. .. .. . .. .. .. .. .. .. .. . .. .. . .. .. .. • . • ...................................................... . . ...................................................... .. . . . . C1 C8 H` 1.17: ınh 1.4 Pham vi v` liˆn thˆng manh ae o . . Ta biˆt rˇ ng hˆ thˆng truyˆn thˆng cua mˆt tˆ’ ch´.c c´ thˆ’ xem nhu. mˆt d` thi trong d o ˙ ˙ ´` .´ ` ˙’ ea eo e o oouoe o ¯ˆ . .o ¯´ . .`.i tu.o.ng u.ng mˆt d ınh v` c´c kˆnh truyˆn thˆng tu.o.ng u.ng c´c cung. Cˆu hoi ˜i ngu o ` ˙ ’ ˙ ’ mˆ o ´ o¯ aa e e o ´ a a . . v c´ thˆ’ dˆn d u.o.c v khˆng? T´.c l` c´ tˆn tai ˙´ .´ u ao` . d at ra l` trong hˆ thˆng n`y, thˆng tin t` i o e ¯e ¯ . j o ¯ˇ a eo a o u o . .`.ng d i t`. v dˆn v ? Nˆu d u.`.ng d i d o tˆn tai ta n´i v thuˆc pham vi cua v . Ch´ng ta ´j ´ ¯o `. ˙i ’ du o ¯ ¯ u i ¯e e ¯ ¯´ o oj o u . . c˜ng quan tˆm dˆn c´ d u.`.ng d i t`. vi dˆn vj v´.i sˆ cung han chˆ khˆng? Muc d´ cua ´ ´ ´ ´ ¯ıch ˙’ u a ¯e o ¯ o ¯u ¯e oo eo . . . ban liˆn quan dˆn c´c t´ chˆ t pham vi v` ` ´ ´ phˆn n`y l` thao luˆn mˆt v`i kh´i niˆm co ˙ aaa˙ ’ ’ a oa ae e ¯e a ınh a a . . . . ˙ a c´c d` thi v` gi´.i thiˆu mˆt sˆ thuˆt to´n co. so.. ´ ’ a ¯ˆ . a o ˙ ’ liˆn thˆng manh cu e o o e oo a a . . . . Theo thuˆt ng˜. cua d` thi biˆu diˆn cho mˆt tˆ’ ch´.c, phˆn n`y khao s´t mˆt sˆ cˆu .˙ u ˙ ¯o . ˜ ˜ ` .´ ’ˆ ˙a ’ a e e oou aa o oa . ˙ ’ hoi: 1. Sˆ ngu.`.i ´ nhˆ t m` mˆi ngu.`.i trong tˆ’ ch´.c c´ thˆ’ liˆn lac d u.o.c bˇ ng bao nhiˆu? ˙ ˙ ˜ o u o ee .¯. ` ´ ´ao o o ıt a o a e 2. Sˆ ngu.`.i nhiˆu nhˆ t c´ thˆ’ liˆn lac d u.o.c v´.i nhau bˇ ng bao nhiˆu? ˙ ` ´ ` ´ o o e a o ee .¯. o a e 3. Hai b`i to´n trˆn c´ quan hˆ g` v´.i nhau? aa eo eıo . 1.4.1 Ma trˆn pham vi a . . Ma trˆn pham vi R = (rij ) d .nh ngh˜ nhu. sau: a ¯i ıa . . nˆu tˆn tai d u.`.ng d i t`. d ınh vi dˆn d ınh vj , e ` . ¯o ´o ´’ ¯ u ¯˙ ’ ¯e ¯˙ 1 rij := .o.c lai. ´ 0 nˆu ngu . . e Tˆp R(vi ) c´c d ınh cua d` thi G c´ thˆ’ dˆn d u.o.c t`. d ınh vi gˆm c´c d ınh vj sao cho ˙´ ` a ¯˙ ’ ˙ ¯o . ’ˆ o e ¯e ¯ . u ¯ ˙ ’ a ¯˙ ’ a o . . r bˇ ng 1. Theo d inh ngh˜ tˆ t ca c´c phˆn tu. trˆn d u.`.ng ch´o cua ma trˆn pham phˆn tu ij ` `˙ ´’ ` ˙ e ¯o a’ ıa, a ˙ a a’ e˙ ’ a ¯. a. . ` vi bˇ ng 1. a 33
Do Γ(vi ) l` tˆp c´c d ınh c´ thˆ’ dˆn d u.o.c t`. vi theo mˆt d u.`.ng d i c´ d o d`i 1 nˆn ˙´ a a a ¯˙ ’ o e ¯e ¯ . u o ¯o ¯ o ¯ˆ a e . . . .ng d ınh c´ thˆ’ dˆn d u.o.c t`. v theo mˆt d u.`.ng d i c´ d ˆ d`i ˙´ ` 2 ¯˙’ tˆp Γ(Γ(vi )) = Γ (vi ) gˆm nh˜ a o u o e ¯e ¯ . u i o ¯o ¯ o ¯o a . . . 2. Tu.o.ng tu., Γp (vi ) l` tˆp nh˜.ng d ınh c´ thˆ’ dˆn d u.o.c t`. vi theo mˆt d u.`.ng d i c´ d ˆ d`i ˙´ ¯˙ ’ aa u o e ¯e ¯ . u o ¯o ¯ o ¯o a . . . . p. Do vˆy, tˆp c´c d ınh c´ thˆ’ dˆn d u.o.c t`. vi l` ˙´ a a a ¯˙ ’ o e ¯e ¯ . u a . . R(vi ) = {vi } ∪ Γ1 (vi ) ∪ Γ2 (vi ) ∪ · · · . Nhu.ng do d` thi d u.o.c x´t l` h˜.u han v` moi d u.`.ng d i d` u ch´.a mˆt d u.`.ng d i con so. cˆ p ´ ¯o . ¯ . e a u ˆ . a . ¯o ¯ ¯ˆ e u o ¯o ¯ a . ¯´ e ` . trong d o, nˆn tˆn tai p sao cho o R(vi ) = {vi } ∪ Γ1 (vi ) ∪ Γ2 (vi ) ∪ · · · ∪ Γp (vi ). (1.1) Suy ra tˆp pham vi R(vi ) c´ thˆ’ nhˆn d u.o.c t`. Phu.o.ng tr` (1.1) bˇ ng c´ch thu.c hiˆn c´c ˙. ` a o e a¯. u ınh a a ea . . . . .p t`. tr´i sang phai cho dˆn khi tˆp hiˆn h`nh khˆng tˇng k´ thu.´.c trong lˆn ´ ` ˙ ’ ph´p to´n ho u a e a ¯e a ea o a ıch o a . . . lˇp kˆ tiˆp. Sˆ c´c ph´p to´n ho.p phu thuˆc v`o d` thi, mˇc d` hiˆ’n nhiˆn rˇ ng p ≤ n − 1, ˙ ` ´´ ´ a ee oa e a o a ¯o . a u e ˆ ea . . . . . trong d o n l` sˆ d ınh cua d` thi. ´’ a o ¯˙ ˙ ¯ˆ . ’o ¯´ Vˆy ma trˆn pham vi c´ thˆ’ d u.o.c xˆy du.ng nhu. sau. T` tˆp R(vi ) v´.i mˆi d ınh vi ˙ ˜’ o o ¯˙ a a o e¯ . a ım a . . . . . .o.c lai. e -a ´ ´ theo trˆn. Dˇt rij = 1 nˆu vj ∈ R(vi ), v` rij = 0 nˆu ngu . . e a e . Ma trˆn d at d u.o.c Q = (qij ) d .nh ngh˜ nhu. sau: a ¯. ¯ . ¯i ıa . nˆu tˆn tai d u.`.ng d i t`. d ınh vj dˆn d ınh vi , e ` . ¯o ´o ´’ ¯ u ¯˙ ’ ¯e ¯ ˙ 1 qij := .o.c lai. ´ 0 nˆu ngu . . e Tˆp Q(vi ) cua d` thi G l` tˆp c´c d ınh c´ thˆ’ dˆn d u.o.c d ınh vi . Tu.o.ng tu. nhu. trˆn ˙´ ˙ ¯o . ’ˆ a a a ¯˙ ’ o e ¯e ¯ . ¯ ˙ ’ a e . . . ta c˜ng c´ u o Q(vi ) = {vi } ∪ Γ−1 (vi ) ∪ Γ−2 (vi ) ∪ · · · ∪ Γ−p (vi ), (1.2) trong d o Γ−2 (vi ) = Γ−1 (Γ−1 (vi )), . . . . ¯´ T`. d .nh ngh˜ hiˆ’n nhiˆn c´ Q = Rt . ˙ u ¯i ıa, e eo V´ du 1.4.1 X´t d` thi G trong H` 1.18. Ma trˆn kˆ cua G l` a`˙ . e’ ı. e ¯o . ˆ ınh a v v2 v3 v4 v5 v6 v7 1  v1 0 1 0 0 1 0 0   v2  0 1 0 1 0 0 0   v3  0 0 0 0 1 0 0   A = v4  0 . 0 0 0 0 1 0     v5  0 0 0 0 0 1 0   v6  1 0 0 1 0 0 0   v7 0 0 0 1 0 1 0 34
v1 •... .. ... .. .... . ... .. .. ... .. ... .. ... ... .. . ... ... .. ... . ... .. .. .... .......... .... .... . ... ......... ..... . .... .. .... ... .... ... . . .. ... ... ... ... .. .. .. . .. ... ... . .. . . . . ... . ... . . . .. . . . ... ... . . . .. . .. ... . . ... . . ... . ... . . .. . . . . . .... . ... ... .. . . . v2 • ... ... ... . ... .. .. . ... . ... .. . . ... . .. ... . . ............... . ............ .. . . . .. . . . .. . . . . . .. . . . .. . .. . . . .. . . . . .. . . . . .. . . . .. . .. . . . .. . v6 . . . .. . . . . .. . . . • .. . . . . .. ........ ..... ....... . .. ..... . .......... . .... . . . ..... ... . .. . ... . . . ..... ..... . . . ... ... . . . ..... ..... . . . ..... .. . . ..... .. . . ....... .. . . ..... . . . ........... . . . ........ . . . . . . . . . . .. ..... . ..... . . . . .. .. ... ..... . ... .. ..... . .. . .. . . . . . ...... .. . ... ..... ...... . . . . ... . ... .... .. . . . . . . . ..... ..... . . .. . . . ..... . ..... . . . . . . .. ..... ..... . . . .. . . . ..... . . . ..... .. . . .. .. ..... . . ..... . . . . ...... .... . .. .. . .. .. .. . . . .. ....... ... . . .......... ... . .. . . ... ..... . . ... ..... ..... . • v3 . ..... .. . • . . ..... . . .... . .. ....... ....... .. . .. ... . .. .... . .... ... . . ... .... . . .... v7 .... .. . ... ... .... .. . . . .... . .. ... ........ . ... . .. . . . .. ... .... . ... .. .... . . .... ... ... .... . .. . . .... . .. . .... . .... . ... .. ..... ... . . .... .... . ...... ... ... .. . .... . . . .... . .. .... . .. ... . . .... ... . .... .. ... . .. .... ... . .... . . .... .... . .. .... . ... . .... .... . .... . .. . ..... .... . .... .... . . . .... .... . . .... . ... ............. ... ... ........... .. .... ............................................................................... ......................................... .................................. .. ... • v5 •.. ..... .. .. ... ... .. . . .. .. . .. .. .. v4 . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. .. . .... ... ... ... ... .... .... ............... . ............ H` 1.18: ınh C´c tˆp pham vi c´ thˆ’ x´c d .nh t`. Phu.o.ng tr` (1.1) nhu. sau ˙ aa o e a ¯i u ınh . . R(v1 ) = {v1 } ∪ {v2 , v5 } ∪ {v2 , v4 , v5 } ∪ {v2 , v4 , v5 } = { v1 , v 2 , v 4 , v 5 } , R(v2 ) = {v2 } ∪ {v2 , v4 } ∪ {v2 , v4 , v5 } ∪ {v2 , v4 , v5 } = { v2 , v 4 , v 5 } , R(v3 ) = { v3 } ∪ { v4 } ∪ { v5 } ∪ { v5 } = { v3 , v 4 , v 5 } , R(v4 ) = { v4 } ∪ { v5 } ∪ { v5 } = { v4 , v 5 } , R(v5 ) = { v5 } ∪ { v5 } = {v5 }, R(v6 ) = {v6 } ∪ {v3 , v7 } ∪ {v4 , v6 } ∪ {v3 , v5 , v7 } ∪ {v4 , v5 , v6 } = { v3 , v 4 , v 5 , v 6 , v 7 } , R(v7 ) = {v7 } ∪ {v4 , v6 } ∪ {v3 , v5 , v7 } ∪ {v4 , v5 , v6 } = { v3 , v 4 , v 5 , v 6 , v 7 } . 35
Do d o ma trˆn pham vi c´ dang ¯´ a o. . . v v2 v3 v4 v5 v6 v7 1  v1 1 1 0 1 1 0 0   v2  0 1 0 1 1 0 0   v3  0 0 0 1 1 1 0    0 . R = v4  0 0 0 1 1 0    v5  0 0 0 0 0 1 0   v6  1 0 0 1 1 1 1   v7 0 0 1 1 1 1 1 Cˆn ch´ y rˇ ng, do R v` Q l` c´c ma trˆn Boole, mˆ i h`ng cua ch´ng c´ thˆ’ lu.u dang ˙ u´ ` ˜ ` ˙ ’ a a a aa a oa u oe . . .n mˆt t`. (word) . Viˆc t` c´c ma trˆn n`y l` mˆt t´ to´n d o.n gian do chı ˙ ’ ˙ ’ mˆt hoˇc ho o a ou e ım a a a a o ınh a ¯ . . . . . . .a v`o c´c ph´p to´n logic. du a a e a . T`. d .nh ngh˜ R(vi ) ∩ Q(vj ) l` tˆp c´c d ınh vk m` c´ ´ nhˆ t mˆt d u.`.ng d i t`. vi dˆn ´ o¯o ´ a a a ¯˙ ’ u ¯i ıa, a o ıt a ¯u ¯e . . ´´ ´’ ¯˙’ a ¯˙ ’ a ˙ a ¯˙ ’ vj qua d ınh vk . C´c d ınh n`y goi l` cˆt yˆu. Tˆ t ca c´c d ınh vk ∈ R(vi ) ∩ Q(vj ) goi l` khˆng a . ao e / .a o ´t yˆu hay du. th`.a do bo ch´ng d i khˆng anh hu.o.ng dˆn c´c d u.`.ng d i t`. vi dˆn vj . ´ ´ a ¯o ´ ˙u¯ ’ ˙ ’ ˙ ’ cˆ e o u o ¯e ¯u ¯e C´c ma trˆn R v` Q d .nh ngh˜ trˆn l` tuyˆt d ˆi theo ngh˜ sˆ c´c cung trˆn d u.`.ng .´ ´ a a a ¯i ıa e a e ¯o ıa o a e ¯o . . v dˆn v khˆng bi han chˆ. Mˇt kh´c ta c˜ng c´ thˆ’ d inh ngh˜ tu.o.ng tu. c´c ma ˙ ¯. ´ ´ d i t` i ¯e j ¯u o e a a u oe ıa .a .. . trˆn n`y v´.i sˆ cung trˆn d u.`.ng d i khˆng vu.o.t qu´ mˆt sˆ cho tru.´.c. V´.i mo. rˆng n`y ta ´ ´ ˙o ’. a aoo e ¯o ¯ o aoo o o a . . . .o.c c´c ma trˆn han chˆ theo lu.o.c d` trˆn. c˜ng c´ thˆ’ t´ d u . a ˙ ´ u o e ınh ¯ a e . ¯ˆ e o . . D` thi d u.o.c goi l` bˇc cˆu nˆu tˆn tai c´c cung (vi , vj ) v` (vj , vk ) th` c˜ng tˆn tai cung -ˆ .¯ . . a a ` e ` . a´a´o `. o a ıu o ´ a ˙ ¯o . (vi , vk ). Bao d ´ng bˇc cˆu cua d` thi G = (V, E ) l` d` thi Gtc = (V, E ∪ E ) trong d o E l` a` ’ˆ ¯o a ¯o . ˆ ¯´ a .o.c thˆm v`o ´ nhˆ t dˆ’ d` thi G c´ t´ bˇc cˆu. Dˆ d`ng ch´.ng minh rˇ ng ˙ ¯o . tc o ınh a ` ´a ˜a ` ´ c´c cung d u . a ¯ e a ıt a ¯e ˆ e u a ` ` cua d` thi Gtc ch´ l` ma trˆn pham vi R v` bˇ ng ˙ ¯ˆ . ’o ma trˆn kˆ ae ınh a a aa . . . A + A2 + · · · + Ap , (p ≤ n − 1), a`˙ . e’ trong d o A l` ma trˆn kˆ cua G. (Tai sao?) ¯´ a . ` 1.4.2 T` c´c th`nh phˆn liˆn thˆng manh ım a a a e o . Th`nh phˆn liˆn thˆng manh d .nh ngh˜ trong phˆn tru.´.c tru.´.c l` d` thi con liˆn thˆng ` ` a ae o ¯i ıa a o o a ¯ˆ . o e o . .n nhˆ t trong G. V` v´.i d` thi liˆn thˆng manh, v´.i moi cˇp d ınh v , v , luˆn luˆn ´ a ¯˙ ’ manh l´ o a ı o ¯ˆ . e o o o o o . . .. ij ` n tai mˆt d u.`.ng d i t`. d ınh vi dˆn d ınh vj v` ngu.o.c lai, nˆn tˆn tai duy nhˆ t mˆt th`nh ´ ¯˙ `. ´o ¯ u ¯˙ ’ ’ tˆ . o o ¯o ¯e a eo a a . .. . phˆn liˆn thˆng manh ch´.a mˆt d ınh cho tru.´.c v` vi s˜ xuˆ t hiˆn trong tˆp c´c d ınh cua ` ´e o ¯˙ ’ a a ¯˙ ’ ˙ ’ ae o u oa ea . . . . ˙n nhiˆn (tai sao?). ’ ˙ ’ ` oa˙o ’. mˆt v` chı mˆt th`nh phˆn liˆn thˆng manh. Khˇng d .nh n`y l` hiˆ a ae o a ¯i aae e . . . 36
Nˆu d ınh vi d u.o.c coi v`.a l` xuˆ t ph´t v`.a l` kˆt th´c th` tˆp c´c d ınh cˆt yˆu tu.o.ng ´’ ´ ´ ´´ e ¯˙ ı a a ¯˙ ’ ¯. uaa a u ae u oe . .ng v´.i hai d ınh tr`ng nhau n`y (t´.c l` tˆp c´c d ınh thuˆc mach n`o d ´ ch´.a v ) x´c d inh ¯˙ ’ u a a a ¯˙ ’ u ´ o u a o a ¯o u i a ¯. . . . .i R(v ) ∩ Q(v ). V` tˆ t ca c´c d ınh cˆt yˆu n`y c´ thˆ’ dˆn t`. v v` ngu.o.c lai nˆn ch´ng ˙´ ´’ ´´ ˙ ’ ı a ˙ a ¯˙ ’ bo o e a o e ¯e u i a ..e u i i ˙ dˆn d u.o.c c´c d ınh kh´c trong tˆp n`y v` ngu.o.c lai. Ho.n n˜.a, dˆ thˆ y rˇ ng ’ ¯e ¯ . a ¯˙ ˜a` ´ ´a ’ c˜ng c´ thˆ u oe a aaa u e . .. tˆp R(vi ) ∩ Q(vi ) x´c d inh c´c d ınh cua th`nh phˆn liˆn thˆng manh duy nhˆ t tu.o.ng u.ng ` ´ a ¯˙’ ˙ ’ a a ¯. a ae o a ´ . . .i d ınh v . v´ ¯˙ o’ i Nˆu ta loai c´c d ınh n`y khoi d` thi G = (V, Γ) th` c´ thˆ’ ´p dung t` th`nh phˆn ˙ ´ ` . a ¯˙ ’ ˙ ¯o . ’ˆ e a ı o ea ım a a . .o.c G v´.i tˆp d ınh V \ (R(v ) ∩ Q(v )). Qu´ tr` liˆn thˆng manh trˆn d` thi con nhˆn d u . o a ¯˙ ’ e o e ¯ˆ . o a¯ a ınh . . . i i ´n khi tˆ t ca c´c th`nh phˆn liˆn thˆng manh d u.o.c t` Kˆt th´c ta c´ d` ´ ˙a ` ´ ’ n`y lˇp lai cho dˆ aa. ¯e a a ae o ¯ . ım. e u o ¯ˆo . . thi G d u.o.c phˆn hoach th`nh c´c th`nh phˆn liˆn thˆng manh. ` ¯. a a a a ae o . . . V´ du 1.4.2 X´t d` thi trong H` 1.19. Ch´ng ta h˜y t` th`nh phˆn liˆn thˆng manh ` ı. e ¯o . ˆ ınh u a ım a ae o . .a d ınh v . ch´ ¯˙ ’ u 1 v1 v6 v10 v11 •......................................................................................•....................................................................................•................................................................................•............................ .. ... .. ... .. ... . . . . .. ....... ..... . .. . ........... . . . . . . . . .. . . . .. . . . .. . . . .... ..... . ... .. .. .... .... . . . ..... ...... . ... .. .. .. . .. .. .. .... .... ... .. . .. ... ... ..... . ... .. .. . .. .. ..... ... ...... .. .. . ..... ... ...... .. ... .. . ... .. .. .. . . .... .. .. .. . . .. ... ... ..... ... .. .. . ... .... .... .. . .. .... . ... .. .. . .. .. .... ... .... . .. .. .. .... .. ... ... .... ... • v13 . .. . .. .. ... .. . . ... .. .... . ..... ... ... .. .... .... . ... ... . . .. . ... .. . ... . . .. . . .. . .. ... ... . . ... ... . .. ... . . ... .. .. .. ... . . .. ... . .. . ... . . .. .... . .... . ... ... ... . . . .. ... . .. .. . .. . .... .. ... .. . .. ... .. .. .... .. . ... .. ... . .. .. .. . .. ... .. . .. .... .. .... .. ... .. . ... .. .. ... .. . .. .. .. ....... ... . . ....... .. .. .. ... . . ... .. ... .. . . .. . .. . .. .. ... . . .... .. . ... . . .. . . ........ . ... . . . .. ... . . .. ... . . . . .... .. . ... . . .. ... . . ..... .. ... . . . . ... .. ..... .. . . ... .. .... .. .. .. . .... . . • • • • ........................................... ................... .................. .. . ... . ... . . . . ... .. .. .. ... .. ... . ..... . . ... ... . . ... . v2 v5 v8 v12 . . .... ... . ... . ... . . . ... ... ... . . ... . . . ... ... . ... . . ... . . ... ... . ... . . ... . . . ... ... ... . . ... . . ... ... ... .... . ... ... . ... . . . .... . ... . .. . . ..... . . ... ... .. .. ... . . .... .. . . .. ... . . .. ... . . ... ... . ... ... . . ... . . ... ... . . ... . . ... ... . . ... ... . . ... . . ... . ... . . ... . ... . ... . . ... . ... . ... . • v9 ... . .... . . • • ... . ... ...................................... . ... . .................................... .. . . .. . . ... ... . ... .. . ... . v3 v7 ... .. . .. . ... ... ... ... . . ... . ... ... ... . . ... .. ... . .. . ... ... ... . ... . ... . ... .... .... ... ... . ... ... . .. .... .... . . .. . . .... ... .... ... . . . ... . . ... .. ... . ... . ... ... . ... ... . . ... ... ... . ... . ... . ... ... . ..... ... . ...... . ... . .. ... . ... .... ... . ....... • .. .. v4 -ˆ . H` 1.19: D` thi G. ınh o T`. c´c phu.o.ng tr` (1.1) v` (1.2) ta c´ ua ınh a o R(v1 ) = {v1 , v2 , v4 , v5 , v6 , v7 , v8 , v9 , v10 } v` a Q(v1 ) = {v1 , v2 , v3 , v5 , v6 }. Do d o th`nh phˆn liˆn thˆng manh ch´.a d ınh v1 l` d` thi con ` u ¯˙ ’ ¯´ a ae o a ¯ˆ . o . R(v1 ) ∩ Q(v1 ) = {v1 , v2 , v5 , v6 } . 37
Tu.o.ng tu., th`nh phˆn liˆn thˆng manh ch´.a d ınh v8 l` d` thi con {v8 , v10 } , ch´.a ` u ¯˙ ’ a ae o a ¯o . ˆ u . . d ınh v7 l` d` thi con {v4 , v7 , v9 } , ch´.a d ınh v11 l` d` thi con {v11 , v12 , v13 } , v` ch´.a d ınh ¯˙’ u ¯˙ ’ a u ¯˙ ’ a ¯o . ˆ a ¯o . ˆ v3 l` d` thi con {v3 } . D` thi thu gon Gr d u.o.c cho trong H` 1.20. -ˆ . a ¯ˆ . o o ¯. ınh . ∗ ∗ v1 = {v1 , v2 , v5 , v6 } v2 = {v8 , v10 } • • .. ....................................................................................................... ..................................................................................................... .. . . . . ... ..... . . .. . ..... . ... . .... . . ..... . .... . . .. .... . .... . ... . . .... . . ... .... . . ... .... . . .... ... . . .... . ... . .... . . ... . . .... ... .... . . . ... . .... . .... . ... . . .... . ... . .... . ... . . .... . ... .... . . ... . .... . . .... ... . . ...... ... . . ..... . . ... ...... . . .. ... ...... . . ... . . ..... ..... . . ... . .... . ... .... . . ... . . .... ... . .... . . . ... .... . . .... ... . . . .... ... . .... . ... . . .... . . ... .... . . ... .... . . .... ... . . .... ... . . .... . . ... . .... . ... . .... . .. .... . .... . .... .... .. . ∗ .. . • v4 = {v11 , v12 , v13 } .... . .... .... . . . .. ... . . . ... . ... . .. . . .. . . ... ... ... . . . ... . ... . . . . ... ... . . . . . . ... ... . . . . ... . . ... . . . . ... ... . . . . ... . . ... . . . . ... ... . . . . ... . . ... . . . . ... ... . . . . ... . . ... . . . . ... ... . . . . . ... . ... . . . . ... . ... . . . . ... . ... . . . . ... . ... . . . . ... . ... . . ... . . ... . . ... . . . . ... . . •∗ •∗ .. . .. ................................................................................................ . .............................................................................................. .. .. . .. v5 = {v3 } v3 = { v4 , v 7 , v 9 } -ˆ . H` 1.20: D` thi thu gon Gr . ınh o . C´c ph´p to´n d u.o.c miˆu ta trˆn dˆ’ t` c´c th`nh phˆn liˆn thˆng manh cua mˆt d` ˙ ` e ˙ e ¯e ım a ’ ˙ ’ a e a¯. a ae o o ¯o .ˆ . . dung tru.c tiˆp d ˆi v´.i c´c ma trˆn R v` Q d inh ngh˜ phˆn tru.´.c. Do thi c˜ng c´ thˆ’ su . ˙’ ´ ´ ıa ` o e˙ .u e ¯o o a a a ¯. a o . . ´u ta k´ hiˆu R ⊗ Q c´ ngh˜ l` ma trˆn nhˆn d u.o.c t`. R v` Q bˇ ng c´ch nhˆn c´c ` d o nˆ ¯´ e ye o ıa a a a ¯. u a a a aa . . . phˆn tu. tu.o.ng u.ng th` phˆn tu. (R ⊗ Q)ij = rij qij bˇ ng 1 nˆu tˆn tai d u.`.ng d i t`. vi dˆn vj ` ` ı` e ` .¯o ´o ´ a˙ ’ a˙ ’ ´ a ¯u ¯e .o.c lai, v` bˇ ng 0 trong tru.`.ng ho.p ngu.o.c lai. Do d o hai d ınh thuˆc c`ng mˆt th`nh ` ¯˙’ v` ngu . . a a a o ¯´ ou o a . .. . . ` n liˆn thˆng manh nˆu v` chı nˆu c´c h`ng (hoˇc cˆt) tu.o.ng u.ng bˇ ng nhau. C´c d ınh ` ´ a ˙e a a’´ a ¯˙ ’ phˆ e a o e ao ´ a . .. .o.ng u.ng ch´.a mˆt phˆn tu. 1 o. cˆt v tao th`nh tˆp d ınh cua th`nh phˆn liˆn ` ` a˙ ’ ˙o j. ’. a ¯˙ ’ ˙ ’ m` h`ng tu aa ´ u o a a ae . . .a v . Hiˆ’n nhiˆn rˇ ng c´ thˆ’ biˆn d o’i ma trˆn R ⊗ Q bˇ ng ph´p ho´n vi ˙ ˙ e ¯ˆ ˙ ` ` ´ thˆng manh ch´ i o u e ea oe a a e a. . . c´c h`ng v` c´c cˆt sao cho ma trˆn thu d u.o.c c´ dang khˆi ch´o; mˆ i ma trˆn con ch´o˜ ´ aa aa o a ¯. o . o e o a e . . . .o.ng u.ng v´.i mˆt th`nh phˆn liˆn thˆng manh cua G v` c´ c´c phˆn tu. bˇ ng 1, c´c phˆn a ˙` ` ` ` ˙ ’ ’a tu ´ oo a ae o aoa a a . . 38
tu. kh´c bˇ ng 0. V´.i v´ du trˆn, ma trˆn R ⊗ Q d u.o.c sˇp x´6p lai c´ dang ` ´ ˙’ aa oı.e a ¯. a e .o. . v1 v2 v5 v6 v8 v10 v4 v7 v9 v11 v12 v13 v3   v1 1 1 1 1   v2 1 1 1 1    1  v5 1 1 1   1  v6 1 1 1     v8  1 1    v10   1 1     R ⊗ Q = v4  1 1 1 .   v7   1 1 1   v9   1 1 1     v11  1 1 1    v12   1 1 1     v13  1 1 1  v3 1 Co. so. ˙’ 1.4.3 Tˆp B c´c d ınh c´ thˆ’ dˆn d u.o.c moi d ınh cua d` thi v` nho nhˆ t theo ngh˜ khˆng c´ tˆp ˙´ ´ a ¯˙ ’ . ¯˙’ ˙ ¯o . a ’ˆ ˙a ’ a o e ¯e ¯ . ıa o oa . . .c su. n`o cua n´ c´ t´ chˆ t n`y goi l` co. so.. Do d o nˆu ta viˆt R(B ) l` tˆp pham ´ ´ ´ con thu . a ˙ o o ınh a a . a ’ ˙ ’ ¯´ e e aa . . . vi cua B -t´.c l` ˙ ’ ua R(B ) = ∪vi ∈B R(vi ) th` B l` co. so. nˆu v` chı nˆu ’´ ’´ ˙e a ˙e ı a 1. B (V ) = V ; v` a 2. v´.i moi tˆp con S ⊂ B th` R(S ) = V. o .a ı . Diˆu kiˆn th´. hai tu.o.ng d u.o.ng v´.i d iˆu kiˆn vj ∈ R(vi ) v´.i hai d ınh phˆn biˆt vi , vj ∈ B ; -` o ¯` ¯˙’ e e u ¯ e e / o a e . . . .c l` mˆt d ınh thuˆc B khˆng thˆ’ dˆn d u.o.c t`. mˆt d ınh kh´c trong B. Diˆu n`y c´ thˆ’ -` ˙´ ˙ t´ a o ¯˙ ’ e ¯e ¯ . u o ¯˙ ’ u o o a eaoe . . . .ng minh nhu. sau: ch´u Do v´.i hai tˆp con H v` H ⊂ H ta c´ R(H ) ⊂ R(H ) nˆn d iˆu kiˆn R(S ) = V v´.i moi e ¯` o a a o e e o . . . .o.ng d u.o.ng v´.i R(B \{v }) = V v´.i moi v ∈ B. N´i c´ch kh´c, R(v ) ⊂ R(B \{v }). S ⊂ B tu ¯ o o oa a .j j j j Nhu.ng d iˆu kiˆn n`y thoa m˜n nˆu v` chı nˆu vj ∈ R(B \ {vj }), t´.c l` vj ∈ R(vi ) v´.i moi ¯` ´ ’´ ˙ a e a ˙e ’ e ea / ua / o . . vi , vj ∈ B. Vˆy, co. so. l` mˆt tˆp B c´c d ınh thoa m˜n hai d iˆu kiˆn sau: ¯` ˙a o a ’ a ¯˙ ’ ˙a ’ a e e . .. . 39
1. tˆ t ca c´c d ınh cua G c´ thˆ’ dˆn d u.o.c t`. d ınh n`o d o cua B ; v` ˙´ ´’ a ˙ a ¯˙ ’ ˙ ’ o e ¯e ¯ . u ¯ ˙ ’ a ¯´ ˙ ’ a 2. khˆng d ınh n`o trong B c´ thˆ’ dˆn d u.o.c t`. mˆt d ınh thuˆc B. ˙´ o ¯˙ ’ o e ¯e ¯ . u o ¯˙ .’ a o . T`. hai d iˆu kiˆn n`y ta suy ra ¯` u e ea . Mˆnh d` 1.4.3 (i) Khˆng tˆn tai hai d ı’nh trong co. so. B sao cho ch´ng thuˆc c`ng mˆt `. ¯˙ ˙’ e ¯ˆe o o u ou o . . . ` n liˆn thˆng manh cu a G. ˙’ th`nh phˆ e a a o . (b) D` thi khˆng mach c´ duy nhˆ t mˆt co. so. gˆm tˆp c´c d ı’nh c´ bˆc trong bˇ ng khˆng. -ˆ . o ` ´o ˙` ’ o a a ¯˙ o o a oa a o . . . . Ch´.ng minh. Suy tru.c tiˆp t`. d .nh ngh˜ ´ u e u ¯i ıa. . Theo Mˆnh d` trˆn v` do d` thi thu gon Gr cua d` thi G khˆng c´ manh nˆn tˆp co. ˙ ¯ˆ . ’o e ¯ˆ e a e ¯o . ˆ o o. ea . . . . B cua G l` tˆp c´c d ınh c´ bˆc trong bˇ ng khˆng. C´c tˆp co. so. cua G c´ thˆ’ x´c d inh ˙ ` so r ˙ ˙ ’ ’ a ¯˙’ ˙˙ ’’ raa oa a o aa o e a ¯. . . . du.a v`o Br . Cu thˆ’ l` nˆu Br = {S1 , S2 , . . . , Sk }, trong d o k l` sˆ c´c tˆp d ınh Sj trong co. ˙ ´ ´ ¯´ a o a a ¯˙ ’ .a . ea e . . B cua G , th` B l` tˆp dang {v , v , . . . , v } v´.i v ∈ S , j = 1, 2, . . . , k. so r ˙ ˙ ’ ’ ı aa o ij . . r i1 i2 ik j V´ du 1.4.4 V´.i d` thi trong H` 1.19, d` thi thu gon trong H` 1.20. Co. so. cua d` ˙ ˙ ¯ˆ ’’ ı. o ¯o . ˆ ınh ¯o . ˆ ınh o . ` ´’ ∗∗ ∗ ∗ ¯˙’ a˙ thi n`y l` {v4 , v5 } do v4 v` v5 l` hai d ınh duy nhˆ t cua G c´ bˆc trong bˇ ng khˆng. Suy ra aa a a oa a o . . c´c tˆp co. so. cua G l` {v3 , v11 }, {v3 , v12 } v` {v3 , v13 .} ˙˙ ’’ aa a a . Dˆi ngˆu v´.i kh´i niˆm co. so. c´ thˆ’ d .nh ngh˜ theo thuˆt ng˜. cua c´c tˆp ho.p Q(vi ) -o ˙ ˜ ´ ˙ o e ¯i ’ u˙ aa ’ ao ae ıa a . . . . . sau. nhu Dˆi co. so. l` tˆp B c´c d ınh cua d` thi G = (V, Γ) thoa m˜n ˙ a a ¯ a ¯˙ -o ´ ’ ’ ˙ ¯ˆ . ’o ˙a ’ . ¯ Q(B ) = Q(vi ) = V, vi ∈B ¯ ∀S ⊂ B, Q(S ) = V. T´.c l` B l` tˆp nho nhˆ t c´c d ınh c´ thˆ’ dˆn d u.o.c t`. c´c d ınh kh´c. C´c t´ chˆ t cua B u a¯aa a ınh a ˙ ¯ ˙´ ´ ´’ ˙ a a ¯˙ ’ ’ o e ¯e ¯ . u a ¯ ˙ ’ a . .o.ng tu. v´.i cua B trong d o c´c kh´i niˆm vˆ hu.´.ng d u.o.c thay bˇ ng ban sao ngu.o.c lai. ` ae` .o˙ ’ ˙ ’ tu ¯´ a eo ¯. a . .. Do vˆy, d ˆi co. so. cua d` thi thu gon Gr l` tˆp c´c d ınh cua Gr c´ bˆc ngo`i bˇ ng a` ´ ˙ ˙ ¯ˆ . ’’ a a a ¯˙ ’ ˙ ’ a ¯o o oa a . . . . . d o ta c´ thˆ’ nhˆn d u.o.c d oi co. so. cua G tu.o.ng tu. nhu. d a thu.c hiˆn o. trˆn. ˙. ´ ˙˙ ’’ e˙e’ khˆng, v` t` ¯´ o au o e a ¯ . ¯ˆ ¯˜ . . . Trong v´ du cua d` thi G trong H` 1.19, d` thi thu gon Gr chı ch´.a mˆt d ınh v3 ∗ ı . ˙ ¯o . ’ ˙u ’ o ¯˙’ ˆ ınh ¯o . ˆ . . . so. cua G l` {v ∗ } v` bo.i vˆy d ˆi co. so. cua G l` ` ´ ´ c´ bˆc ngo`i bˇ ng khˆng. Do d ´ d ˆi co ˙ ˙ ’’ a ˙ a ¯o ’. ˙˙ ’’ oa aa o ¯o ¯o ra a . 3 {v4 }, {v7 } v` {v9 }. a 40
Ap dung trong cˆ u tr´ c tˆ’ ch´.c ´ ˙u ´ a uo . Nˆu d` thi biˆ’u diˆn cˆ u tr´c anh hu.o.ng cua mˆt tˆ’ ch´.c th` c´c phˆn tu. cua mˆt th`nh ˙ ˙ ˜a ´ˆ e´ ` u˙ ’ ˙ ’ ˙ ’ a˙˙ ’’ e ¯o . e oou ıa o a . . .o.ng v` ch´.c nˇng ngang nhau. Mˆt co. so. cua G c´ ` phˆn liˆn thˆng manh cua G c´ anh hu ˙ ˙ ’ o˙ ’ ’ ˙˙ ’’ ae o aua o o . . thˆ’ hiˆ’u l` mˆt “liˆn minh” c´ sˆ ngu.`.i ´ nhˆ t nhu.ng l˜nh d ao moi c´ nhˆn trong tˆ’ ch´.c. ˙˙ ˙ ´ ´ eeao e oo o ıt a a ¯. aa ou . . Trˆn tˆp c´c d ınh biˆ’u diˆn c´c th`nh viˆn cua c`ng tˆ’ ch´.c, ta x´t d` thi G d u.o.c ˙ ˙ ˜a e a a ¯˙ ’ ˙u ’ e e a e ou e ¯o . ˆ ¯. . .ng dˆ’ biˆ’u diˆn c´c kˆnh truyˆn thˆng sao cho tˆn tai cung (v , v ) nˆu v c´ thˆ’ giao ˙e ˙ ˙ ˜ae ` `. ´ io e xˆy du ¯e a e e o o e . ij tiˆp v´.i vj . D` thi G d˜ nhiˆn c´ liˆn quan v´.i G. Sˆ ngu.`.i ´ nhˆ t m` biˆt hoˇc c´ thˆ’ -ˆ . ˙ ´ ´ ´ ´ eo o ı e oe o o o ıt a ae aoe . . kiˆn vˆ tˆ’ ch´.c tao th`nh mˆt d ˆi co. so. cua G . Ta c´ thˆ’ n´i rˇ ng mˆt ˙u. ˙o` nhˆn tˆ t ca c´c su e ` o .´’ .´ a a ˙a . . e ˙˙ ’’ a o ¯o oe a o . ˙ dˆ’ l˜nh d ao tˆ’ ch´.c l` tˆp H nh˜.ng ngu.`.i thoa m˜n: ˙ ˙ u aa ’ ¯e a ˙a ’ liˆn minh hiˆu qua e e ¯. o u o . . ¯ H = B (G) ∪ B (G ), trong d o B (G) v` B (G ) l` mˆt trong c´c co. so. v` c´c d ˆi co. so. cua G v` G tu.o.ng u.ng a¯ ´ ˙ a a ¯o ’ ˙˙ ’’ ¯´ ao a a ´ . .o.c chon sao cho #H nho nhˆ t. ´ ˙ ’a du . ¯ . Kˆ tiˆp x´t co. so. lu˜ th`.a l` tˆp c´c d ınh Bp ⊂ V sao cho ´´ ˙ y u a a a ¯˙ ’ ’ ee e . R(Bp ) = V, Q(Bp ) = Bp , R(S ) = V, ∀ S ⊂ Bp . Diˆu kiˆn th´. hai ngh˜ l` chı nh˜.ng ngu.`.i bˆn trong Bp m´.i c´ thˆ’ c´ anh hu.o.ng dˆn -` ˙ ´ ıa a ˙ u’ o o e o˙ ’ ˙ ’ e e u oe ¯e . .`.i kh´c c˜ng trong B v` c´ thˆ’ thay bˇ ng d iˆu kiˆn tu.o.ng d u.o.ng: R(V \ B ) ∩ B = ∅. ˙ ` ¯` ngu o au pao e a e e ¯ p p -` ` ´ ` ˙ ’ o ¯˙ ’ ˙ ’ Diˆu kiˆn n`y chı ra rˇ ng nˆu mˆt d ınh trong th`nh phˆn liˆn thˆng manh cua G thuˆc Bp e ea a e a ae o o . . . . th` moi d ınh kh´c trong c`ng th`nh phˆn liˆn thˆng manh n`y c˜ng thuˆc Bp . Do tˆp co. ` ı . ¯˙ ’ a u a ae o au o a . . . so. cua Gr l` tˆp c´c d ınh c´ bˆc trong bˇ ng khˆng nˆn tˆp co. so. l˜y th`.a cua G ch´ l` ` ˙˙ ’’ a a a ¯˙ ’ ˙u ’ u˙ ’ oa a o ea ınh a . . . Bp = Si . Si ∈B ∗ Chˇng han d` thi trong H` 1.19 c´ co. so. l˜y th`.a l` {v3 , v11 , v12 , v13 }. Cˆn ch´ y ˙ ’ ` ˙u ’ a . ¯o . ˆ ınh o ua a u´ rˇ ng, nˆu d` thi n`y tu.o.ng u.ng mˆt tˆ’ ch´.c th` v3 c´ thˆ’ xem l` ngu.`.i l˜nh d ao cao nhˆ t ˙ ˙ ` ´ˆ ´ a e ¯o . a ´ oou ı oe a oa ¯. a . ∗∗ ∗ ˙a ’ cua c´c nh´m v1 , v2 v` v3 . o a -a ˙ ’ Dˇ ng cˆ u cua c´c d` thi ´ ˙ ’ a ¯ˆ . 1.5 a o Ta d ˜ biˆt rˇ ng c`ng mˆt d` thi c´ thˆ’ d u.o.c biˆ’u diˆn bˇ ng nhiˆu h` v˜ kh´c nhau. Viˆc ˙ ˙ ¯a e ` ˜a e` ´a ` u o ¯ˆ . o e ¯ . .o e e ınh e a e . .o.c trong tru.`.ng ho.p n`o hai h` v˜ biˆ’u diˆn c`ng mˆt d` thi, trong tru.`.ng ˙ ˜u ´ nhˆn biˆt d u . a e¯ o a ınh e e e o ¯o . ˆ o . . . ho.p n`o biˆ’u diˆn hai d` thi kh´c nhau, l` mˆt vˆ n d` khˆng d o.n gian. ˙ ˜ ´e ˙ ’ a e e ¯ˆ . a o a o a ¯ˆ o ¯ . . 41
R˜ r`ng l` hai h` cho tru.´.c biˆ’u diˆn c`ng mˆt d` thi chı khi c´c d iˆu kiˆn sau d ˆy ˙ ˜u a ¯` o ¯ˆ . ˙ ’ oa a ınh o e e .o e e ¯a . .o.c thoa m˜n: ˙a ’ du . ¯ ` ´’ o ¯˙ 1. Sˆ d ınh bˇ ng nhau; a ` ´ 2. Sˆ canh bˇ ng nhau; o. a a` ´’ o ¯˙ 3. Sˆ d ınh c`ng bˆc bˇ ng nhau. u .a D´ l` nh˜.ng d iˆu kiˆn cˆn: hai h` khˆng thoa m˜n mˆt trong c´c d iˆu kiˆn d ´ th` -o a u ¯` e` a ¯` ˙a ’ e .a ınh o o e e ¯o ı . . .ng ch´ng c˜ng khˆng phai l` d iˆu kiˆn d u (h˜y cho khˆng biˆ’u diˆn c`ng mˆt d` thi. Nhu ˙ ˜u ˙ a ¯` ’ e ¯˙ a ’ o e e o ¯ˆ . o u u o e . . v´ du). Hiˆ’n nhiˆn rˇ ng ˙ ` ı. e ea -. -` Dinh l´ 1.5.1 Diˆu kiˆn cˆn v` d u dˆ’ hai h` biˆ’u diˆn c`ng mˆt d` thi l` tˆn tai mˆt ’˙ ˙ ˜u e ` a ¯ ˙ ¯e o ¯ˆ . a ` . y e .a ınh e e .o o o . .o.ng u.ng mˆt-mˆt lˆn gi˜.a c´c d ı’nh cu a hai h` sao cho nˆu hai d ı’nh cu a h` n`y d u.o.c ´ ˙ ˙ ’ ˙ ˙ ınh a ¯ . ’ tu ´ o oe u a¯ ınh e ¯ . . nˆi bo.i mˆt canh th` hai d ı’nh tu.o.ng u.ng cu a h` kia c˜ng d u.o.c nˆi v´.i nhau bo.i mˆt ´’ ´ o˙ ¯˙ ˙’ ınh ˙ ’ o. ı ´ u ¯. oo o . . .o.c lai. canh v` ngu . . a . Viˆc t` mˆt tiˆu chuˆ’n d o.n gian v` hiˆu qua dˆ’ ph´t hiˆn t´ d ang cˆ u cua c´c d` ˙ ’˙ ˙ ’ ´ ˙ a ¯o ˙ae ’ ˙ ¯e a ’ e ım o e a¯ e ınh ¯ˇ a ˆ . . . . . cua l´ thuyˆt d` thi v` d ang c`n d u.o.c tiˆp tuc nghiˆn c´.u. ˜ ´o ´ thi vˆn l` b`i to´n mo ˙ y ˙’ ’ .a aa a e ¯ˆ . a ¯ o¯. e. eu ˙ ’ ´ 1.5.1 1−d a ng cˆ u ¯ˇ a D` thi c´ c´c d iˆ’m kh´.p gˆm ´ nhˆ t hai d` thi con khˆng c´ d iˆ’m kh´.p. Mˆ i d` thi con -ˆ . o a ¯e ˙ ˙ ˜ˆ o ` ıt a ´ o o ¯ˆ . o o o ¯e o o ¯o . .n nhˆ t khˆng c´ d iˆ’m kh´.p goi l` khˆi. D` thi trong H` 1.21 c´ nˇm khˆi . a o -ˆ . ˙ ´ ´ ´ liˆn thˆng l´ e o o a o o ¯e o o ınh oa o ˙m kh´.p a, b v` c). Ch´ y rˇ ng d` thi liˆn thˆng khˆng c´ d iˆ’m kh´.p chı c´ mˆt ’ ˙ ` ˙o o ’ (v` ba d iˆ a ¯e o a u´ a ¯o . e ˆ o o o ¯e o . ´ khˆi. o • • • ...... ..... ...... ..... ..... .... . .. . ....... ... .... ... ..... .. . ....... ... ..... ... ..... . ... ....... ... .. . ... ... .. . .... .. .... .... ... ... .. . ... ... . .... ... ... .. . .. .... .... ... ... .. ... . . .... . . . .... ... ... . ... ... . .. ... .. .... ... .... .. .... .. . .... ... ... . ... ... ... .... . ... . .... ... . . .. ... . . ... ... .... a c . ... ... ... .. . ... .... . . b ... ... . . .... . . . .. ... ... ... .... . ... ... ... . .. ... . .... . ... . .... . ... .... .... . ... .. .... .... ... . . ... ... .. ... . . • • • • . . . ...................................................................... ..... ..................................................................... . .. .... . .... . ....... .. . .. .. . . ... .. . . ... . .. . . . . .... . ..... . .... . ....... ... .. . ... . . .. ... . ... . . . .. . . . ... . . .... ... .... .. . . . .... ... .... . ... .. . . . . . .. . . . . .... ... . .... .... . ... ... . .... . ... .. . . . . . .. . .... .. . ... .... . .. . .. ... .. .. . . . ... . .... .... . . . ... .... . .... ... .. . . . ... .. . ... .... . .... . .... .... ... .. . . . ... .. . . .. ... . .... .... ... .... .. .... . .. . ... . ... . .. . . .. .... ... . .... . .... ... .. . .... ... . . . ... .... .. . . ... .. . ....... . .... ... .. . . ... . ... .... .. . ..... .... . . ... .... . .... .. . .. . .... . . • • • . .... .... .... .... . .. . .. .. . . . . . . . . . . . . . . . . . . . . . . . . . • . . H` 1.21: ınh 42