intTypePromotion=2
Array
(
    [0] => Array
        (
            [banner_id] => 141
            [banner_name] => KM2 - Tặng đến 100%
            [banner_picture] => 986_1568345559.jpg
            [banner_picture2] => 823_1568345559.jpg
            [banner_picture3] => 278_1568345559.jpg
            [banner_picture4] => 449_1568779935.jpg
            [banner_picture5] => 
            [banner_type] => 7
            [banner_link] => https://tailieu.vn/nang-cap-tai-khoan-vip.html
            [banner_status] => 1
            [banner_priority] => 0
            [banner_lastmodify] => 2019-09-18 11:12:45
            [banner_startdate] => 2019-09-13 00:00:00
            [banner_enddate] => 2019-09-13 23:59:59
            [banner_isauto_active] => 0
            [banner_timeautoactive] => 
            [user_username] => minhduy
        )

)

Lý thuyết đồ thị cây

Chia sẻ: Le Xuan Lê Xuân | Ngày: | Loại File: PDF | Số trang:0

0
300
lượt xem
122
download

Lý thuyết đồ thị cây

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

Tham khảo tài liệu 'lý thuyết đồ thị cây', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:
Lưu

Nội dung Text: Lý thuyết đồ thị cây

  1. CAÂY Ñònh nghóa „ Ñònh nghó nghóa caây: … Caây laø laø ñoà thò lieân thoâng vaø vaø khoâng coù coù chu trì trình … Moä Moät röø röøng ng p caây laø laø moä moät ñoà thò goà goàm p thaø thaønh nh phaà phaàn lieân thoâng, trong ñoù moãi thaø thaønh nh phaà phaàn lieân thoâng laø laø moä moät caây „ Ghi chuù chuù: Ñònh nghó nghóa caây haø haøm yù yù raè raèng ng moï moïi caây ñeàu khoâng chöù chöùa khuyeân cuõng khoâng chöù chöùa caï caïnh nh song song. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 2 1
  2. Ñònh nghóa „ Ví duï duï. G vaø vaø G1 khoâng laø laø caây (G) (G1) Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 3 Ñònh nghóa „ Ví duï duï duï.ï.G du (G2) 2 vaø vaø vaø G3ø (G3) va laø laø caâylaø la(chuù ø caâyù y(chuù (chu ù ñònhù ynghó (chu ù ñònh ngh óa chu nghó nghtrì óaình tr chu cuû cutrì ûa ìñnh tr oà cuû thò cuûacoù ñoù hà thò co öôùng ncoù g ù trong co höôùng ngchö chtrong öông chö I) öông I) ch (G2) (G3) Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 4 2
  3. Ñònh lyù veà söï toàn taïi caùc ñænh treo „ Neá Neáu moä moät caây T goà goàm n ñænh ñænh vôù vôùi n ≥ 2 thì thì T chöù chöùa ít nhaá nhaát hai ñænh ñænh treo „ Chöù Chöùng ng minh: Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 5 Ñònh lyù veà caùc ñònh nghóa töông ñöông „ Xeù Xeùt moä moät ñoà thò G goà goàm n ñænh, ñænh, caùcaùc khaú khaúng ng ñònh sau ñaây laø laø töông ñöông: ñöông: … (a) Ñoà thò G laø laø caây. … (b) GiöGiöõa hai ñænh ñænh baá baát kyø kyø cuû cuûa G, toà toàn taï taïi duy nhaá nhaát moä moät daây chuyeà chuyeàn noánoái chuù chuùngng vôùvôùi nhau. … (c) G lieân thoâng toá toái tieå tieåu (nghó (nghóa laø laø G lieân thoâng vaø vaø neá neáu xoù xoù a ñ i baá á t kyøø moä ä t caï ba ky mo ca nh na cu ï nh naøø o cuû û a G thìì th nonoùù khoâ n g coø coøn lieân thoâng nö nöõa). Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 6 3
  4. Ñònh lyù veà caùc ñònh nghóa töông ñöông „ Xeù Xeùt moä moät ñoà thò G goà goàm n ñænh, ñænh, caù caùc khaú khaúng ng ñònh sau ñaây laø laø töông ñöông ñöông (tt): … (d) Theâm moämoät caï caïnh nh noá noái 2 ñænh ñænh baá baát kyø kyø cuû cuûa G thì thì G seõ chöù chöùa moä moät chu trì trình duy nhaá nhaát.t. … (e) G lieân thoâng vaø vaø coù coù n-1 caï caïnh.nh. … (f) G khoâng coù coù chu trì trình vaø vaø coù coù n-1 caï caïnh. nh. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 7 Caây toái ñaïi (caây phuû, caây bao truøm, m, caây khung) „ Ñònh nghó nghóa: … Cho G=(X, E) laø laø moä moät ñoà thò lieân thoâng vaø vaø T=(X, F) laø laø moä moät ñoà thò boä boä phaä phaän cuûcuûa G. Neá Neáu T laølaø caây thì thì T ñöô ñöôïc goï goïi laø laø moä moät caây toá toái ñaïi cuû cuûa G. „ Ñònh lyù lyù (söï (söï toà toàn taï taïi caây toá toái ñaïi) i) … Moï Moïi ñoà thò lieân thoâng ñeàu coù coù chöù chöùa ít nhaá nhaát moä moät caây toá toái ñaïi Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 8 4
  5. Caây toái ñaïi (caây phuû, caây bao truøm, m, caây khung) „ Thuaä Thuaät toaù toaùn PRIM (tì (tìm moä moät caây toá toái ñaïi cuû cuûa ñoà thò G) Cho G=(X, E) laø laø moä moät ñoà thò lieân thoâng goà goàm n ñænh. ñænh. Thuaä Thua toaä t toaù ù n sau ñ aâ y cho pheùù phe t p tì ìm ra ñöô ô ñö moïc moäät caâ y toá toái ñaïi cuû cuûa G. … Böôùc1. c1. ChoïChoïn tuø tuøy yù yù v ∈ X vaø vaø khôû khôûi taï taïo V := { v }; T := ∅ … Böôùc 2. 2. Choï Choïn w∈w∈ X \ V sao cho coù coù moä moät caï caïnh nh e naønaøo ñoù cuû cuûa G noá noái w vôù vôùi moä moät ñænh ñænh trong V … Böôùc 3. 3. Gaù Gaùn V := V ∪ {w} vaø vaø T := T ∪ {e} … Böôùc 4. 4. Neá Neáu T ñuû n-1 phaàphaàn töû töû thì thì döøng, ng, ngö ngöôïc laïlaïi laø laøm tieá tieáp tuï tuïc bö böôùc 2. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 9 Caây toái ñaïi ngaén nhaát „ Ñònh nghó nghóa: Cho ñoà thò G=(X, E). … (a) Ñoà thò G ñöôñöôïc goï goïi laø laø coù coù troï troïng ng neá neáu moãi caï caïnh nh cuû cuûa G ñöô ñöôïc tötöông öùng ng vôù vôùi moä moät soá soá thöï thöïc dö döông, nghó nghóa laø laø coù coù moä aùnh moät aù nh xaï xaï nhö nhö sau: L: E ⎯⎯→ |R+ e |⎯⎯→ |⎯⎯→ L(e) … Thuaä Thuaät ngöngöõ thö thöôøng ng duø duøng: ng: troï troïng, ng, troï troïng ng lö löôïng, ng, chieà chieàu daø daøi, i, chi phí phí, … Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 10 5
  6. Caây toái ñaïi ngaén nhaát „ Ñònh nghó nghóa: Cho ñoà thò G=(X, E). … (b) Troï Troïng ng lö löôïng ng (hay giaùgiaù) cuû cuûa moämoät caây toá toái ñaïi T trong ñoà thò lieân thoâng coù co tro ng ba ng vô to ng troï ù troïï ng baè è ng vôù ù i toå ång troïng ng lö löôïng ng caù caùc caï caïnh nh trong caây: L(T) = ∑(e∈ (e∈T) L(e) … (c) Giaû Giaû söû G lieân thoâng coù coù troï troïng. ng. Caây toá toái ñaïi ngaé ngaén nhaá nhaát cuû cuûa G laø laø caây toá toái ñaïi coùcoù troï troïng ng lölöôïngng nhoû nhoû nhaá nhaát khi xeù xeùt trong taä taäp hôï hôïp taá taát caû caû caù caùc caây toátoái ñaïi coùcoù theå theå coù coù cuû cuûa G. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 11 Thuaät toaùn Prim „ Cho G=(X, E) laø laø moä moät ñoà thò lieân thoâng coù coù troï troïng ng goà goàm n ñænh. ñænh. Thuaä Thuaät toaù toaùn Prim ñöô ñöôïc duøduøng ng ñeå tìm ra caây toá toái ñaïi ngaé ngaén nhaá nhaát cuû cuûa G. „ Böôùc 1.1. Choï Choïn tuø tuøy yù yù v ∈ X vaø vaø khôû khôûi taï taïo Y := { v }; T := ∅ „ Böôùc 2.2. Trong soá soá nhö nhöõng caï caïnh nh e noá noái ñænh ñænh w vôù vôùi v maø maø w ∈ X\V vaøvaø v ∈ Y ta choï choïn caï caïnh nh coù coù troï troïng ng lö löôïng ng nhoû nhoû nhaá nhaát.t. „ Böôùc 3.3. Gaù Gaùn Y := Y ∪ {w} vaø vaø T := T ∪ {e} „ Böôùc 4.4. Neá Neáu T ñuû n-1 phaà phaàn töû töû thì thì döøng, ng, ngö ngöôïc laï laïi laø laøm tieá tieáp tuï tuïc bö böôùc 2. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 12 6
  7. Thuaät toaùn Prim „ Caø Caøi ñaët thuaä thuaät toaù toaùn Prim „ Trong caù caùc thuaä thuaät toaù toaùn tì tìm caây toá toái ñaïi ngaé ngaén nhaá nhaát chuùchuùng ng ta coùù theåå boûû ñ i höö ôù co the bo h ng ca ca nh va cang caùù c caïï nh vaø ø caù ù c khuyeâ n ; ñ o á i vôù vôùi caù caùc caï caïnhnh song song thì thì coù coù theå theå boû boû ñi vaø vaø chæ chæ ñeå laï laïi moä moät caï caïnh nh troï troïng ng lölöôïng ng nhoûnhoû nhaá nhaát trong chuù chuùng.ng. VìVì vaä vaäy dödöõ lieä lieäu nhaä nhaäp cho thuaä thuaät toaù toaùn thö thöôøngng laø laø ma traätraän troï troïng ng lölöôïng ng ñöôñöôïc qui öôùc nhö nhö sau: troï troïng ng lö löôïng ng caï caïnhnh nhoû nhoû nhaá nhaát noá noái i ñeán j neá neáu coù coù „ Lij = 0 neá neáu khoâng coù coù caï caïnh nh noá noái i ñeán j Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 13 Thuaät toaùn Kruskal „ Cho ñoà thò G=(X, E). „ Böôùc 1.1. Saé Saép xeá xeáp caù caùc caï caïnhnh theo thöù thöù töï troï troïng ng lö löôïng ng taêng daà daàn vaø vaø khôû khôûi taï taïo T := ∅. „ Böôùc 2.2. Laà Laàn lö löôït laá laáy töø töøng ng caï caïnh nh e thuoä thuoäc danh saùsaùch ch ñaõ saé saép xeá xeáp. p. Neá Neáu T+{e} khoâng chöù chöùa chu trì trình thìthì gaù gaùn T := T+{e}. „ Böôùc 3.3. Neá Neáu T ñuû n-1 phaà phaàn töû töû thì thì döøng, ng, ngö ngöôïc laï laïi laø laøm tieá tieáp tuï tuïc bö böôùc 2. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 14 7
  8. Caây coù höôùng ng (caây ngoaøi) i) Ñoà thò coù goác „ Ñoà thò coùcoù goá goác … Cho G=(X, E) laø laø moä moät ñoà thò coù coù höôùng. ng. Ta noùnoùi G laø laø moä mo ä t ñ o à thò coù ù goá á c neá á u toà co go ne to ta ñæ à n taï ï i ñænh nh r ∈ X sao cho töø t r öø coù coù ñöô ñöôøng ng ñi ñeán taá taát caû caû caù caùc ñænh ñænh khaù khaùc cuû cuûa ñoà thò. … Chuù Chuù yù ñònh nghó nghóa trong chö chöông 1 veà veà ñöô ñöôøng ng ñi trong ñoà thò coù coù höôùng ng Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 15 Caây coù höôùng ng (caây ngoaøi) i) Ñoà thò coù goác „ Ñoà thò (G1): caùcaùc ñænh ñænh b, c, d ñeàu laø laø goá goác; c; ñænh ñænh a khoâng phaû phaûi laø laø goá goác. c. „ Ñoà thò (G2) khoâng phaû phaûi laø laø ñoà thò coù coù goá goác. c. a (G2) (G1) b d c Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 16 8
  9. Caây coù höôùng ng (caây ngoaøi) i) Ñoà thò töïa lieân thoâng maïnh nh „ Cho G=(X, E) laø laø moä moät ñoà thò coù coù höôùng. ng. Ta noù noùi G laø laø ñoà thò töïa lieân thoâng maï maïnh nh neá neáu: u: vôù vôùi moï moïi ñænh ñænh i, j ∈ X luoân toàtoàn taï taïi moä moät ñænh ñænh k ∈ X sao cho coù coù ñöô ñöôøng ng ñi töø töø k ñeán i vaø vaø coù coù ñöô ñöôøng ng ñi töø töø k ñeán j. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 17 Caây coù höôùng ng (caây ngoaøi) i) Ñoà thò töïa lieân thoâng maïnh nh „ Nhaä Nhaän xeù xeùt: t: … Töø caù caùc ñònh nghó nghóa ta suy ra ngay tí tính chaá chaát sau ñoái vôù vôùi moä moät moä moät ñoà thò coù coù höôùng: ng: Coù Coù goá goác ⇒ Töïa lieân thoâng maï maïnhnh ⇒ Lieân thoâng. … Do títính chaá chaát höõu haï haïn cuû cuûa caù caùc ñoà thò trong giaù giaùo trì trình naà naày, y, chuù chuùng ng ta cuõng coù coù ñònh lyù lyù sau ñaây. „ Ñònh lyù lyù. G laø laø ñoà thò coù coù goá goác ⇔ G laø laø ñoà thò töï töïa lieân thoâng maï maïnh nh Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 18 9
  10. Caây coù höôùng ng (caây ngoaøi) i) Ñònh nghóa caây coù höôùng ng „ Cho G=(X, E) laø laø moä moät ñoà thò coù coù höôùng. ng. G ñöô ñöôïc goï goïi laø laø caây coù coù höôùng ng neá neáu: u: … (a) G khoâng coùcoù chu trì trình, … (b) G coù coù goá goác. c. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 19 Caây coù höôùng ng (caây ngoaøi) i) Ñònh nghóa caây coù höôùng ng „ Ghi chuù chuù. … Theo ñònh nghó nghóa trong chöchöông 1, moä moät chu trì trình coù coù theå theå khoâng keåkeå ñeán hö höôùng ng cuû cuûa caù caùc caï caïnh. nh. … Töø ñònh nghó nghóa ta suy ra caây coù coù höôùng ng cuõng laølaø caây. … Khaù Khaùi nieä nieäm caây coùcoù höôùng ng trong ñònh nghó nghóa treân vaãn coø coøn toå toång ng quaù quaùt hôn khaù khaùi nieä nieäm caây trong caùcaùc giaù giaùo trì trình tin hoï hoïc (chaú (chaúng ng haï haïn nhö nhö giaù giaùo trì trình caá caáu truù truùc dö döõ lieä lieäu). u). Caù Caùc caây trong caù caùc giaù giaùo trì trình tin hoï hoïc ñöô ñöôïc veõ ra giaágiaáy vôù vôùi nuù nuùt goá goác ñöô ñöôïc veõ treân cuøcuøng, ng, nuù nuùt cha luoân ôû ôû phí phía treân, ngoaø ngoaøi ra phaû phaûi coù coù söï phaân bieä bieät giö giöõa caây con beân traù traùi vaø vaø caây con beân phaû phaûi. i. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 20 10
  11. Caây coù höôùng ng (caây ngoaøi) i) Ñònh nghóa caây coù höôùng ng „ Hai caây coù coù höôùng ng (T1) vaø vaø (T2) xem nhö nhö ñaúng ng caá caáu nhau trong giaù giaùo trì trình lyù lyù thuyeá thuyeát ñoà thò nhö nhöng chuù chuùng ng laø laø hai caây hoaø hoaøn toaø toaøn khaù khaùc nhau trong giaù giaùo trì trình caá caáu truù truùc dö döõ lieä lieäu. u. (T1) A (T2) A B C C B D E F E F D Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 21 Caây coù höôùng ng (caây ngoaøi) i) Ñònh lyù veà caùc ñieàu kieän töông ñöông vôùi ñònh nghóa cuûa caây coù höôùng ng „ Cho G=(X, E) laø laø moä moät ñoà thò coù coù höôùngng goàgoàm n ñænh. ñænh. Caù Caùc ñieà ieàu sau ñaây tö töông ñöông ñöông vôù vôùi nhau. … (a) G laølaø moä moät caây coù coù höôùng. ng. … (b) G coù coù moä moät ñænhñænh r vaøvaø töø r toà toàn taï taïi moä moät ñöô ñöôøngng ñi duy nhaá nhaát ñeán taá taát caû caû caù caùc ñænh ñænh coøcoøn laï laïi. i. … (c) G töïtöïa lieân thoâng maï maïnhnh toá toái tieå tieåu (töù (töùc laø laø neá neáu xoù xoùa bôù bôùt baá á t kyø ø moä ä t ba ky mo ca nh na thcaïï nh naøø o thìì G seõ khoâ n g coøø co t n töï öï a lieâ n thoâng maïmaïnh). nh). Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 22 11
  12. Caây coù höôùng ng (caây ngoaøi) i) Ñònh lyù veà caùc ñieàu kieän töông ñöông vôùi ñònh nghóa cuûa caây coù höôùng ng „ Cho G=(X, E) laø laø moä moät ñoà thò coù coù höôùngng goà goàm n ñænh. ñænh. Caù Caùc ñieà ieàu sau ñaây tötöông ñöông ñöông vôùvôùi nhau. … (d) G lieân thoâng vaø vaø coù coù ñænh ñænh r sao cho: d-(r)=0 vaøvaø d-(i)=1, ∀i∈X\{r}. … (e) G khoâng coù coù chu trì trình vaø vaø coù coù ñænh ñænh r sao cho: d (r)=0 vaø - vaø d (i)=1, ∀i∈X\{r}. - … (f) G töï töïa lieân thoâng maïmaïnh nh vaø vaø khoâng coù coù chu trì trình. … (g) G töï töïa lieân thoâng maïmaïnh nh vaø vaø coù coù n-1 caï caïnh. nh. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 23 Caây coù höôùng ng (caây ngoaøi) i) Ñònh lyù veà caùc ñieàu kieän töông ñöông vôùi ñònh nghóa cuûa caây coù höôùng ng „ Ghi chuù chuù: … Ñænh Ñænh r trong ñònh lyù lyù treân laø laø duy nhaá nhaát vaø vaø ñöô ñöôïc goï goïi laø laø goá goác cuû cuûa caây coù coù höôùng. ng. … Moãi ñænh ñænh i∈ i∈X, i≠ i≠r do d-(i)=1 neân coù coù duy nhaá nhaát moä moät ñænh ñænh j maømaø caï caïnh nh lieân keá keát vôù vôùi (j, i) hö höôùng ng vaø vaøo i, ñænh ñænh j ñöô ñöôïc goï goïi ñænh ñænh cha cuû cuûa I. … Neá Neáu ñænh ñænh x∈ x∈X thoû thoûa ñieà ieàu kieä kieän d+(x)=0 thìthì x ñöô ñöôïc goï goïi laø laø laù laù cuû cuûa caây coù coù höôùng. ng. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 24 12
  13. Caây coù höôùng ng (caây ngoaøi) i) Söï toàn taïi caây coù höôùng ng „ Cho G laølaø ñoà thò coù coù höôùng.ng. … (a) Neá Neáu G coù coù chöù chöùa moä moät ñoà thò boä boä phaä phaän laø laø caây coù coù höôùng ng ththìì G töï töï a lieâ n thoâ n g maï ï ma nh.nh. … (b) Neá Neáu G töï töïa lieân thoâng maï maïnh nh thìthì G coù coù chöù chöùa moä moät ñoà thò boä boä phaä phaän laø laø caây coù coù höôùng.ng. „ Ghi chuù chuù. … Neá Neáu G töï töïa lieân thoâng maï maïnh, nh, T laølaø moä moät caây coù coù höôùng ng laø laø ñoà thò boä boä phaä phaän G thìthì T cuõng ñöô ñöôïc goïgoïi laø laø caây coù coù höôùng ng toá toái ñaïi cuû cuûa G. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 25 Caây coù höôùng ng (caây ngoaøi) i) Ma traän Kirchoff Ñònh nghó nghóa „ Cho G=(X, E) laø laø moä moät ñoà thò coù coù höôùng. ng. Ta ñònh nghó nghóa ma traä traän K nhö nhö sau: d-(i) neá neáu i=j „ Kij = -Bij neá neáu i≠i≠j (Trong ñoù Bij laø laøphaà phaàn töû töû ôû doø doøng ng i coä coät j cuû cuûa ma traä traän keà keà) Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 26 13
  14. Caây coù höôùng ng (caây ngoaøi) i) Ma traän Kirchoff „ Ñònh lyù lyù (Kirchoff) … Giaû Giaû söû G laø laø ñoà thò coù coù höôùng ng ñôn, n ñænh, ñænh, n- n-1 caï caïnh nh coù coù ma traä tra ä n Kirchoff laø laø K. … Goï Goïi K(1, 1) laø laø ma traä traän coù coù ñöô ñöôïc töø töø ma traä traän K baè baèng ng caù caùch ch boû boû ñi doø doøngng 1 vaø vaø coä coät 1, … khi ñoù G laø laø caây ngoaø ngoaøi coù coù goá goác taï taïi ñænh ñænh 1∈ 1∈X khi vaøvaø chæ chæ khi det K(1, 1)=1. Lyù Thuyeát Ñoà Thò - Caây - Khoa CNTT - Ñaïi hoïc KHTN 27 14

CÓ THỂ BẠN MUỐN DOWNLOAD

AMBIENT
Đồng bộ tài khoản