intTypePromotion=1

Phần tích thiết kế giải thuật (phần 12)

Chia sẻ: Nguyen Kien | Ngày: | Loại File: PDF | Số trang:0

0
58
lượt xem
16
download

Phần tích thiết kế giải thuật (phần 12)

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

Lại trở lại với kiến thức có liên quan tới đồ thị , trong tài liệu này sẽ cung cấp và bổ sung cho bạn thêm những kiến thwucs về đồ thị cơ bản, rất hữu ích cho sinh viên công nghệ thông tin

Chủ đề:
Lưu

Nội dung Text: Phần tích thiết kế giải thuật (phần 12)

  1. ÑÒNH NGHÓA ÑOÀ THÒ ÑOÀ THÒ COÙ HÖÔÙNG NG Moät ñoà thò coù höôùng G=(X, U) ñöôïc ñònh nghóa bôûi: taäp hôïp X ≠ ∅ ñöôïc goïi laø taäp caùc ñænh cuûa ñoà thò; taäp hôïp U laø taäp caùc caïnh cuûa ñoà thò; moãi caïnh u∈U ñöôïc lieân keát vôùi moät caëp ñænh (i, j)∈X2. Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 2 1
  2. ÑOÀ THÒ COÙ HÖÔÙNG NG Hình veõ beân laøø minh hoïïa hình hoïïc cuûûa moäät ñoà thò coùù: la ho ho cu mo co Taääp ñænh laøø {A, B, C, D}. Ta ñænh la Taääp caïïnh laøø {u1,u2,u3,u4,u5,u6}. Ta ca nh la A u4 AÙnh xaïï ϕ ñònh nghóa nhö sau: nghó nhö sau: nh xa u1 u1 vaøø u2 lieân keáát vôùùi caëëp (A, B) u1 va ke vô ca D u2 B u3 lieân keáát vôùùi caëëp (A, C) u3 ke vô ca u3 u4 lieân keáát vôùùi caëëp (D, A) u4 ke vô ca u6 u5 lieân keáát vôùùi caëëp (C, B) u5 ke vô ca u5 C u6 lieân keáát vôùùi caëëp (C, D). u6 ke vô ca Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 3 ÑOÀ THÒ VOÂ HÖÔÙNG NG Neááu chuùùng ta khoâng phaân bieäät thöù töï cuûûa caëëp ñænh lieân bie thöù cu ca ñænh Ne chu ng keáát vôùùi moãi caïïnh thì seõ coùù ñöôïc ñoà thò voâ höôùng. Ñoà thò ca nh thì co ñöô ng. ke vô voâ höôùng G=(X, E) ñöôïc ñònh nghóa bôûûi: ñöô nghó bô ng taääp hôïïp X ≠ ∅ ñöôïc goïïi laøø taääp caùùc ñænh cuûûa ñoà thò; ñöô go la ta ca ñænh cu thò; ta hô taääp hôïïp E laøø taääp caùùc caïïnh cuûûa ñoà thò. thò. ta hô la ta ca ca nh cu moãi caïïnh e∈E ñöôïc lieân keáát vôùùi moäät caëëp ñænh ñöô ke vô mo ca ñænh moã ca nh {i, j} ⊆ X khoâng phaân bieäät thöù töï. öù bie th Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 4 2
  3. ÑOÀ THÒ VOÂ HÖÔÙNG NG Hình veõ döôùi laøø minh hoïïa hình hoïïc cuûûa moäät ñoà thò coùù: la ho ho cu mo co Taääp ñænh laøø {A, B, C, D}. Ta ñænh la Taääp caïïnh laøø {e1,e2,e3,e4,e5,e6,e7}. Ta ca nh la A AÙnh xaïï ϕ ñònh nghóa nhö sau: nghó nhö sau: nh xa e4 e1 vaøø e2 lieân keáát vôùùi {A, B} e1 va ke vô e1 e3 lieân keáát vôùùi {A, C} e3 ke vô D e2 e4 lieân keáát vôùùi {A, D} e4 ke vô B e7 e3 e5 lieân keáát vôùùi {B, C} e5 ke vô e6 lieân keáát vôùùi {C, D} e6 ke vô e6 e5 e7 lieân keáát vôùùi {D}. e7 ke vô C Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 5 MOÄT SOÁ TÖØ NGÖÕ vaø QUI ÖÔÙC Khi moäät caïïnh u ñöôïc lieân keáát vôùùi caëëp ñænh (i, j): Khi mo ca nh ñöô ke vô ca ñænh ta noùùi caïïnh u keàà vôùùi ñænh i vaøø keàà vôùùi ñænh j (hay cuõng ta no ca nh ke vô ñænh va ke vô ñænh noùùi ñænh i vaøø ñænh j keàà vôùùi caïïnh u); no ñænh va ñænh ke vô ca nh ta coùù theåå vieáát taéét u=(i, j), nhö vaääy coùù luùùc ta vieáát u=(i, nhö va co lu ta co the vie ta vie j) vaøø v=(i, j) nhöng laïïi hieååu u ≠ v; nhö la hie va neááu ñoà thò voâ höôùng, ta noùùi hai ñænh i vaøø j ñöôïc noáái ng, ñænh va ñöô no ne no vôùùi nhau, neááu ñoà thò coùù höôùng (töùc caëëp ñænh (i, j) ñöôïc vô nhau, ne ca ñænh ñöô co ng toân troïïng thöù töï) ta noùùi ñænh i ñöôïc noáái tôùùi ñænh j. tro ng thöù no ñænh ñöô no tô ñænh neááu ñoà thò coùù höôùng thì ta noùùi caïïnh u baéét ñaàu töø ñænh i ng thì no ca nh ba ñænh ne co vaøø keáát thuùùc taïïi ñænh j, ta cuõng noùùi caïïnh u ñi ra khoûûi nh va ke thu ta ñæ no ca nh kho ñænh i vaøø ñi vaøøo ñænh j. ñænh va va ñænh Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 6 3
  4. MOÄT SOÁ TÖØ NGÖÕ vaø QUI ÖÔÙC Ngoaøøi ra, trong giaùùo trình naàày chuùùng ta chæ laøøm vieääc vôùùi Ngoa ra, gia trì na chu ng chæ la vie vô tröôøng hôïïp caùùc ñoà thò coùù taääp ñænh vaøø taääp caïïnh höõu haïïn. trö ng hô ca co ta ñænh va ta ca nh ha Ñeå cho chính xaùùc thì phaûûi nhaáán maïïnh laøø ÑOÀ THÒ HÖÕU chí xa thì pha nha ma nh la HÖ HAÏÏN, tuy nhieân ñeå ngaéén goïïn chuùùng ta chæ duøøng thuaäät chæ du ng thua HA N, nga go chu ng ngöõ ÑOÀ THÒ vaøø hieååu ngaààm ñoù laøø ñoà thò höõu haïïn. ngö va hie nga la ha Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 7 MOÄT SOÁ TÖØ NGÖÕ vaø QUI ÖÔÙC Ví duïï: Trong hai ví duïï treân u1 vaøø u2 laøø hai caïïnh song du du va la ca nh song trong ñoà thò thöù nhaáát, e1 vaøø e2 laøø hai caïïnh song thöù nha va la ca nh song vaøø e7 laøø moäät khuyeân trong ñoà thò thöù hai. thöù hai. va la mo A A e4 u4 e1 u1 e2 D u2 D e7 B e3 B u3 e6 u6 e5 u5 C C Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 8 4
  5. CAÙC DAÏNG ÑOÀ THÒ ÑAËC BIEÄT NG ÑOÀ THÒ ÑÔN: khoâng coùù khuyeân vaøø khoâng coùù caïïnh co va co ca nh song song. song. ÑOÀ THÒ ÑUÛ: ñoà thò voâ höôùng, ñôn maøø giöõa hai ñænh baáát ng, ma giö ñænh ba kyøø ñeàu coùù ñuùng moäät caïïnh noáái chuùùng. Ta coùù: co ng mo ca nh no chu ng. ky co Moäät ñoà thò ñuû n ñænh seõ coùù n(n-1)/2 caïïnh.K5 ñænh co n(n- Mo ca nh.K5 Ñoà thò ñuû n ñænh ñöôïc kyùù hieääu laøø Kn. ñænh ñöô ky hie la Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 9 CAÙC DAÏNG ÑOÀ THÒ ÑAËC BIEÄT NG ÑOÀ THÒ LÖÔÕNG PHAÂN (HAI PHAÀÀN) LÖ PHA N) Cho G=(X, E) laøø moäät ñoà thò voâ höôùng, ñoà thò G ñöôïc ng, ñöô Cho la mo goïïi laøø ñoà thò löôõng phaân neááu taääp X ñöôïc chia thaøønh ñöô go la ne ta tha nh hai taääp X1 vaøø X2 sao cho: cho: ta va hai taääp X1 vaøø X2 phaân hoaïïch X, nghóa laøø: nghó la hai ta va hoa ch X1≠∅≠X2 vaøø X1∩X2=∅; va hai ñænh baáát kyøø trong X1 khoâng ñöôïc noáái vôùùi hai ñænh ba ky ñöô no vô nhau; hai ñænh baáát kyøø trong X2 cuõng khoâng ñöôïc nhau; ñænh ba ky ñöô noáái vôùùi nhau. no vô nhau. Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 10 5
  6. CAÙC DAÏNG ÑOÀ THÒ ÑAËC BIEÄT NG ÑOÀ THÒ LÖÔÕNG PHAÂN ÑUÛ LÖ Cho G=(X, E) laøø moäät ñoà thò voâ höôùng löôõng phaân Cho la mo ng vôùùi hai taääp X1 vaøø X2 ñònh nghóa nhö treân. G ñöôïc goïïi ó nhö ñöô go vô ta va ngh laøø ñoà thò löôõng phaân ñuû neááu: la ne Vôùùi moïïi caëëp ñænh (i, j) maøø i∈X1 vaøø j∈X2 thì coùù ñuùng Vô mo ca ñænh thì co ng ma va moäät caïïnh cuûûa G noáái i vaøø j. mo ca nh cu no va Neááu ⏐X1⏐=n vaøø ⏐X2⏐=m thì G coùù mxn caïïnh vaøø thì Ne va co ca nh va ñöôïc kyùù hieääu laøø Km, n. ñöô ky hie la Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 11 CAÙC DAÏNG ÑOÀ THÒ ÑAËC BIEÄT NG K4 K4 K3 K2 ≡ K1, 1 K3, 3 K2, 3 Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 12 6
  7. BAÄC CUÛA ÑÆNH BAÄÄC (ÑOÀ THÒ VOÂ HÖÔÙNG) BA (Ñ HÖ NG) Baääc cuûûa moäät ñænh x trong ñoà thò voâ höôùng laøø toåång soáá Ba cu mo ñænh ng la to ng so caùùc caïïnh keàà vôùùi ñænh x, qui öôùc laøø moãi khuyeân phaûûi nh ca ca nh ke vô ñæ la pha ñöôïc tính hai laààn. Baääc cuûûa ñænh x trong ñoà thò G ñöô la Ba cu ñænh ñöôïc kyùù hieääu laøø dG(x) (hay d(x) neááu ñang xeùùt moäät ñöô ky hie la dG(x) d(x) ne xe mo ñoà thò naøøo ñoù). na ). Ví duïï: ñoà thò voâ höôùng trong ví duïï 2 coùù d(B)=3 vaøø du co d(B)=3 va du ng d(D)=4. d(D)=4. Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 13 BAÄC CUÛA ÑÆNH BAÄÄC (ÑOÀ THÒ COÙÙ HÖÔÙNG) BA (Ñ CO NG) Nöûa baääc ngoaøøi cuûûa ñænh x: kyùù hieääu d+(x) laøø soáá caùùc ba ngoa cu ñænh (x) la so ca ky hie caïïnh ñi ra khoûûi ñænh x (hay khôûûi ñaàu töø ñænh x). kho ñænh ñænh ca nh khô Nöûa baääc trong cuûûa ñænh x: kyùù hieääu d (x) la so ca cu ñænh -(x) laøø soáá caùùc ba ky hie caïïnh ñi vaøøo ñænh x (hay keáát thuùùc taïïi ñænh x). ca nh va ñænh ke thu ta ñænh Baääc cuûûa ñænh x: d(x) = d (x) Ba cu ñænh d(x) +(x) + d-(x) (x) Ví duïï: ñoà thò coùù höôùng trong ví duïï 1 coùù d+(A)=1 vaøø du co (A)=1 va du co ng d-(A)=3. Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 14 7
  8. BAÄC CUÛA ÑÆNH ÑÆNH TREO, ÑÆNH COÂ LAÄÄP ÑÆNH ÑÆNH LA Ñænh treo laøø ñænh coùù baääc baèèng 1. Ñænh la ñænh co ba ba ng Ñænh coâ laëëp laøø ñænh coùù baääc baèèng 0. Ñænh la la ñænh co ba ba ng Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 15 BAÄC CUÛA ÑÆNH ÑÒNH LYÙÙ (coâng thöùc lieân heää giöõa baääc vaøø soáá caïïnh) thöù he giö ba va so ca nh) LY a) Xeùùt ñoà thò coùù höôùng G=(X, U). Ta coùù: a) Xe co ng co ∑ d+(x) = ∑ d-(x) = ⏐U⏐ vaøø ∑ d(x) = 2⏐U⏐. (x) (x) va d(x) x∈X x∈X x∈X b) Xeùùt ñoà thò voâ höôùng G=(X, E). Ta coùù: b) Xe ng co ∑ d(x) = 2⏐E⏐. d(x) x∈X Heää quaû: soáá löôïng caùùc ñænh coùù baääc leûû trong moäät ñoà thò laøø ng ca ñænh co ba le He so mo la moäät soáá chaúún. mo so cha Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 16 8
  9. ÑAÚNG CAÁU ÑOÀ THÒ, NG ÑOÀ THÒ CON, ÑOÀ THÒ BOÄ PHAÄN ÑAÚNG CAÁÁU ÑOÀ THÒ VOÂ HÖÔÙNG HÖ NG NG CA Cho hai ñoà thò voâ höôùng G1=(X1, E1) vaøø Cho ng va G2=(X2, E2). Hai ñoà thò G1 vaøø G2 ñöôïc goïïi laøø ñaúng caááu vôùùi nhau ñöô go la ng ca vô Hai va neááu toààn taïïi hai song aùnh ψ vaøø δ thoûûa maõn ñieààu kieään ne to ta nh va tho ie kie sau: sau: ψ: X1 → X2 vaøø δ: E1 → E2 va Neááu caïïnh e ∈ E1 lieân keáát vôùùi caëëp ñænh {x, y} ⊆ ke vô ca ñænh Ne ca nh X1 xeùùt trong ñoà thò G1 thì caïïnh δ(e) seõ lieân keáát thì ca nh xe ke vôùùi caëëp ñænh {ψ(x), ψ(y)} xeùùt trong ñoà thò G2 vô ca ñænh xe (ñieààu naàày ñöôïc goïïi laøø söï töông öùng caïïnh). ie na ñöô go la ng ca nh). Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 17 ÑAÚNG CAÁU ÑOÀ THÒ, NG ÑOÀ THÒ CON, ÑOÀ THÒ BOÄ PHAÄN ÑAÚNG CAÁÁU ÑOÀ THÒ COÙÙ HÖÔÙNG NG CA CO NG Cho hai ñoà thò coùù höôùng G1=(X1, U1) vaøø G2=(X2, Cho co ng va U2). Hai ñoà thò G1 vaøø G2 ñöôïc goïïi laøø ñaúng caááu vôùùi nhau ñöô go la ng ca vô Hai va neááu toààn taïïi hai song aùnh ψ vaøø δ thoûûa maõn ñieààu kieään ne to ta nh va tho ie kie sau: sau: ψ: X1 → X2 vaøø δ: E1 → E2 va Neááu caïïnh e ∈ E1 lieân keáát vôùùi caëëp ñænh (x, y) ∈ ke vô ca ñænh Ne ca nh X1 xeùùt trong ñoà thò G1 thì caïïnh δ(e) seõ lieân keáát thì ca nh xe ke vôùùi caëëp ñænh (ψ(x), ψ(y)) xeùùt trong ñoà thò G2 nh vô ca ñæ xe (ñieààu naàày ñöôïc goïïi laøø söï töông öùng caïïnh). ie na ñöô go la ng ca nh). Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 18 9
  10. ÑAÚNG CAÁU ÑOÀ THÒ, NG ÑOÀ THÒ CON, ÑOÀ THÒ BOÄ PHAÄN Ñoà thò (G1) vaøø (G2) ñaúng caááu nhau. va ng ca ψ(1)=a, ψ(2)=b, ψ(3)=c, ψ(4)=d δ(u1)=e1, δ(u2)=e2, δ(u3)=e6, δ(u4)=e5, δ(u5)=e4, δ(u6)=e3. 1 2 a u1 u5 u4 u2 e4 e2 (G2) e1 (G1) e6 u3 d 4 e5 3 e3 c b u6 Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 19 ÑAÚNG CAÁU ÑOÀ THÒ, NG ÑOÀ THÒ CON, ÑOÀ THÒ BOÄ PHAÄN Hai ñoà thò voâ höôùng G1 vaøø G2 ñaúng caááu nhau Hai ng va ng ca 1 1 G1 G2 3 2 3 2 Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 20 10
  11. ÑAÚNG CAÁU ÑOÀ THÒ, NG ÑOÀ THÒ CON, ÑOÀ THÒ BOÄ PHAÄN Hai ñoà thò coùù höôùng G3 vaøø G4 khoâng ñaúng caááu nhau Hai co ng va ng ca 1 1 G4 G3 3 2 3 2 Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 21 ÑAÚNG CAÁU ÑOÀ THÒ, NG ÑOÀ THÒ CON, ÑOÀ THÒ BOÄ PHAÄN ÑOÀ THÒ CON Cho hai ñoà thò G=(X, U) vaøø G1=(X1, U1). Ta noùùi G1 Cho va no laøø ñoà thò con cuûûa ñoà thò G vaøø kyùù hieääu G1 ≤ G neááu: la cu va ky hie ne X1 ⊆ X; U1 ⊆ U Vôùùi moïïi caïïnh u=(i, j) ∈ U cuûûa G, neááu u ∈ U1 Vô mo ca nh cu ne thì i, j ∈ X1 thì ÑOÀ THÒ BOÄÄ PHAÄÄN BO PHA Cho ñoà thò G1=(X1, U1) laøø ñoà thò con cuûûa ñoà thò Cho la cu G=(X, U). G1 goïïi laøø ñoà thò boää phaään cuûûa G neááu go la bo pha cu ne X=X1. Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 22 11
  12. ÑAÚNG CAÁU ÑOÀ THÒ, NG ÑOÀ THÒ CON, ÑOÀ THÒ BOÄ PHAÄN ÑOÀ THÒ CON SINH BÔÛÛI TAÄÄP ÑÆNH BÔ TA ÑÆNH Cho ñoà thò G=(X, U) vaøø A ⊆ X. Ñoà thò con sinh bôûûi Cho va bô taääp A, kyùù hieääu laøø ñöôïc ñònh nghóa laøø =(A, ô ó la ta ky hie la ñö ngh V), trong ñoù: (i) taääp caïïnh V ⊆ U (i) ta ca nh (ii) Goïïi u=(i, j) ∈ U laøø moäät caïïnh cuûûa G, neááu i, j ∈ (ii) Go la mo ca nh cu ne A thì u ∈ V thì Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 23 ÑAÚNG CAÁU ÑOÀ THÒ, NG ÑOÀ THÒ CON, ÑOÀ THÒ BOÄ PHAÄN G1, G2, G3 laøø ñoà thò con cuûûa ñoà thò G. G2 laøø ñoà thò (con) G1, la cu la boää phaään cuûûa G. G3 laøø ñoà con cuûûa G sinh bôûûi taääp ñænh bô ta ñænh bo pha cu la cu {1, 2, 4, 5}. G1 khoâng phaûûi laøø ñoà thò boää phaään vaøø cuõng pha la bo pha va khoâng sinh bôûûi taääp ñænh {1, 2, 3, 4} vì thieááu caïïnh e7. bô ta ñænh thie ca nh (G1) (G2) 1 e1 e5 1 e1 1 e4 e1 e5 e3 2 e4 e22 e3 e3 2 2 e22 e22 4 e6 5 4 4 e6 e7 e6 5 e7 3 e8 3 3 e9 Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 24 12
  13. DAÂY CHUYEÀN, CHU TRÌNH, N, ÑÖÔØNG ÑI vaø MAÏCH NG CH Cho ñoà thò G=(X, U). Cho DAÂY CHUYEÀÀN: DAÂ CHUYE N: Moäät daây chuyeààn trong G laøø moäät daõy luaân phieân caùùc ñænh ca ñænh Mo chuye la mo vaøø caïïnh: va ca nh: x1 u1 x2 u2... xm-1 um-1 xm (xi laøø ñænh vaøø ui laøø caïïnh) la ñænh va la ca nh) trong ñoà thò thoûûa maõn ñieààu kieään ui lieân keáát vôùùi caëëp ñænh ke vô ca ñænh tho ie kie xi, xi+1 khoâng phaân bieäät thöù töï, nghóa laøø: bie thöù nghó la ui=(xi, xi+1) hay ui=(xi+1, xi) neááu ñoà thò coùù höôùng, ng, ne co ui={xi, xi+1} neááu ñoà thò voâ höôùng. ng. ne Khi ñoù ta goïïi x1 laøø ñænh ñaàu vaøø xm laøø ñænh cuoáái cuûûa daây la ñænh la ñænh cuo cu Khi go va chuyeààn. chuye Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 25 DAÂY CHUYEÀN, CHU TRÌNH, N, ÑÖÔØNG ÑI vaø MAÏCH NG CH DAÂY CHUYEÀÀN SÔ CAÁÁP: daây chuyeààn khoâng coùù ñænh co ñænh DAÂ CHUYE CA P: chuye laëëp laïïi. la la CHU TRÌNH: laøø moäät daây chuyeààn x1 u1 x2 u2... xm-1 um-1 CHU la mo chuye xm um x1 sao cho caùùc ñænh x1, x2, ..., xm ñoâi moäät khaùùc ca ñænh mo kha nhau Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 26 13
  14. DAÂY CHUYEÀN, CHU TRÌNH, N, ÑÖÔØNG ÑI vaø MAÏCH NG CH ÑÖÔØNG ÑI ÑÖÔ NG Moäät ñöôøng ñi trong G laøø moäät daõy luaân phieân caùùc ñænh Mo ñöô ng ca ñænh la mo vaøø caïïnh: : va ca nh x1 u1 x2 u2... xm-1 um-1 xm (xi laøø ñænh vaøø ui laøø caïïnh) la ñænh va la ca nh) trong ñoà thò thoûûa maõn ñieààu kieään ui lieân keáát vôùùi caëëp ñænh ke vô ca ñænh tho ie kie (xi, xi+1), nghóa laøø: nghó la ui lieân keáát vôùùi (xi, xi+1) neááu ñoà thò coùù höôùng, ng, ke vô ne co ui lieân keáát vôùùi {xi, xi+1} neááu ñoà thò voâ höôùng. ng. ke vô ne Khi ñoù ta goïïi x1 laøø ñænh ñaàu vaøø xm laøø ñænh cuoáái cuûûa la ñænh la ñænh cuo cu Khi go va ñöôøng ñi. ñöô ng Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 27 DAÂY CHUYEÀN, CHU TRÌNH, N, ÑÖÔØNG ÑI vaø MAÏCH NG CH ÑÖÔØNG ÑI SÔ CAÁÁP: ñöôøng ñi khoâng coùù ñænh laëëp laïïi. ÑÖÔ NG CA P: ñöô ng co ñænh la la MAÏÏCH: laøø moäät ñöôøng ñi x1 u1 x2 u2... xm-1 um-1 xm um x1 MA CH: la mo ñöô ng sao cho caùùc ñænh x1, x2, ..., xm ñoâi moäät khaùùc nhau . ca ñænh mo kha Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 28 14
  15. DAÂY CHUYEÀN, CHU TRÌNH, N, ÑÖÔØNG ÑI vaø MAÏCH NG CH Trong tröôøng hôïïp ñoà thò voâ höôùng thì: Trong trö ng hô ng thì hai khaùùi nieääm daây chuyeààn vaøø ñöôøng ñi laøø nhö nhau, chuye va ñöô ng la nhö nhau, hai kha nie hai khaùùi nieääm chu trình vaøø maïïch laøø nhö nhau. trì va ma ch la nhö nhau. hai kha nie Do ñoù, chuùùng ta cuõng duøøng thuaäät ngöõ ñöôøng ñi cho ñoà du ng thua ngö ñöô ng Do chu ng thò voâ höôùng. Ñoâi khi moäät maïïch trong ñoà thò coùù höôùng ng. mo ma ch co ng cuõng ñöôïc goïïi laøø moäät “chu trình coùù höôùng”, hay moäät ñöô go la mo trì co ng” mo ñöôøng ñi trong ñoà thò coùù höôùng cuõng ñöôïc goïïi laøø ñöô ng ñöô go la co ng “ñöôøng ñi coùù höôùng” ñeå nhaáán maïïnh. ñöô ng co ng” nha ma nh. Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 29 DAÂY CHUYEÀN, CHU TRÌNH, N, ÑÖÔØNG ÑI vaø MAÏCH NG CH Khi caùùc caïïnh hoaøøn toaøøn ñöôïc hieååu roõ (chaúúng haïïn trong Khi ca ca nh hoa toa ñöô hie cha ng ha moäät ñoà thò voâ höôùng khoâng coùù caïïnh song song) thì: song) thì mo ng co ca nh moäät daây chuyeààn x1 u1 x2 u2... xm-1 um-1 xm coùù theåå vieáát mo chuye co the vie goïïn laøø x1 x2... xm-1 xm ; go la moäät chu trình x1 u1 x2 u2... xm-1 um-1 xm um x1 coùù theåå trì mo co the vieáát goïïn laøø x1 x2... xm-1 xm x1 vie go la Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 30 15
  16. DAÂY CHUYEÀN, CHU TRÌNH, N, ÑÖÔØNG ÑI vaø MAÏCH NG CH Trong ñoà thò coùù höôùng (G): Trong co ng Daõy caùùc ñænh caïïnh: 1 e1 2 e6 3 e8 5 laøø Daõ ca ñænh ca nh: la (G) moäät daây chuyeààn sô caááp (nhöng khoâng ca nhö mo chuye 1 e1 e5 phaûûi ñöôøng ñi vì caïïnh e6 ngöôïc höôùng). pha ñöô ng ca nh ngö ng). e3 e4 2 e2 Daõy caùùc ñænh caïïnh: 1 e1 2 e6 3 e8 5 e4 1 nh ca nh: Daõ ca ñæ e6 2 laøø moäät chu trình (nhöng khoâng phaûûi trì nhö la mo pha 4 5 maïïch vì caïïnh e6 ngöôïc höôùng). ö ng). ma ch ca nh ng e7 Daõy caùùc ñænh caïïnh: 1 e3 4 e7 3 e6 2 e9 5 3 Daõ ca ñænh ca nh: e8 laøø moäät ñöôøng ñi sô caááp. la mo ñöô ng ca e9 Daõy caùùc ñænh caïïnh: 1 e3 4 e7 3 e6 2 e9 5 e4 1 Daõ ca ñænh ca nh: laøø moäät maïïch. la mo ma ch. Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 31 DAÂY CHUYEÀN, CHU TRÌNH, N, ÑÖÔØNG ÑI vaø MAÏCH NG CH Trong ñoà thò voâ höôùng (H): Trong ng Daõy caùùc ñænh caïïnh: 5 e4 1 e3 4 e2 2 e1 1 Daõ ca ñænh ca nh: e4 laøø moäät daây chuyeààn khoâng sô caááp. la mo chuye ca (H) Daõy caùùc ñænh caïïnh: 5 e4 1 e3 4 e7 3 e6 2 Daõ ca ñænh ca nh: e4 1 e1 laøø moäät daây chuyeààn sô caááp vaøø cuõng laøø moäät la mo chuye ca va la mo e5 e4 e3 ñöôøng ñi sô caááp. ñöô ng 2 ca e22 Daõy caùùc ñænh caïïnh: 1 e4 5 e5 1 laøø moäät chu Daõ ca ñænh ca nh: e4 la mo 4 e6 5 trình. trì nh. e7 3 Daõy caùùc ñænh caïïnh: 1 e1 2 e6 3 e7 4 e3 1 Daõ ca ñænh ca nh: e1 laøø moäät chu trình. trì la mo Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 32 16
  17. BIEÅU DIEÃN BAÈNG MA TRAÄN NG Xeùùt ñoà thò G=(X, U) (coù höôùng hay voâ höôùng). (coù ng). Xe ng Giaûû söû taääp X goààm n ñænh vaøø ñöôïc saéép thöù töï ñænh va ñöô sa thöù Gia ta go X={x1, x2, …, xn}, taääp U goààm n caïïnh vaøø ñöôïc saéép thöù töï ca nh va ñöô sa thöù ta go U={u1, u2, …, um}. Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 33 BIEÅU DIEÃN BAÈNG MA TRAÄN NG Ma traään keàà cuûûa ñoà thò G, kyùù hieääu B(G), laøø moäät ma traään Ma tra ke cu ky hie la mo tra nhò phaân caááp n x n ñöôïc ñònh nghóa nhö sau: B=(Bij) vôùùi ñöô nghó nhö sau: B=(B vô ca Bij=1 neááu coùù caïïnh noáái xi tôùùi xj, ne co ca nh no tô Bij=0 neááu ngöôïc laïïi. ne ngö la Neááu G laøø ñoà thò voâ höôùng, ma traään lieân thuoääc (hay lieân ng, Ne la tra thuo keáát ñænh caïïnh ) cuûûa ñoà thò G, kyùù hieääu A(G), laøø ma traään ke ñænh ca nh cu ky hie la tra nhò phaân caááp n x m ñöôïc ñònh nghóa nhö sau: A=(Aij) vôùùi ô ó nhö sau: A=(A vô ca ñö ngh Aij=1 neááu ñænh xi keàà vôùùi caïïnh uj, ne ñænh ke vô ca nh Aij=0 neááu ngöôïc laïïi. ne ngö la Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 34 17
  18. BIEÅU DIEÃN BAÈNG MA TRAÄN NG Neááu G laøø ñoà thò coùù höôùng khoâng coùù khuyeân, ma traään lieân Ne la co ng co tra thuoääc (hay lieân keáát ñænh caïïnh) cuûûa ñoà thò G, kyùù hieääu ke ñænh ca nh) cu thuo ky hie A(G), laøø ma traään n x m ñöôïc ñònh nghóa laøø A=(Aij) vôùùi ñöô nghó la A=(A vô la tra qui öôùc: Aij = 1 neááu caïïnh uj höôùng ra khoûûi ñænh xi , ng kho ñænh ne ca nh Aij = -1 neááu caïïnh uj höôùng vaøøo ñænh xi , ng va ñænh ne ca nh Aij = 0 neááu caïïnh uj khoâng keàà ñænh xi . ke ñænh ne ca nh Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 35 BIEÅU DIEÃN BAÈNG MA TRAÄN NG Neááu ta saéép thöù töï caùùc ñænh vaøø caïïnh cuûûa ñoà thò G laøø sa thöù ca ñænh va ca nh cu Ne la X={A, B, C, D} vaøø U={u1, u2, u3, u4, u5, u6} thì ma traään thì va tra lieân thuoääc cuûûa ñoà thò laøø: thuo cu la A u4 u1 D B u2 u3 u6 u5 C Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 36 18
  19. BIEÅU DIEÃN BAÈNG MA TRAÄN NG Neááu ta saéép thöù töï caùùc ñænh vaøø caïïnh cuûûa ñoà thò G laøø sa thöù ca ñænh va ca nh cu Ne la X={A, B, C, D} vaøø U={u1, u2, u3, u4, u5, u6} thì ma traään thì va tra keàà cuûûa ñoà thò laøø: ke cu la A u4 u1 D B u2 u3 u6 u5 C Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 37 BIEÅU DIEÃN BAÈNG MA TRAÄN NG Goïïi H laøø ñoà thò coùù ñöôïc töø ñoà thò G noùùi treân baèèng caùùch co ñöô Go la no ba ng ca ch boûû ñi höôùng caùùc caïïnh vaøø ta saéép thöù töï caùùc ñænh, caïïnh nhö ng ca ca nh va sa thöù ca ñænh, ca nh nhö bo treân thì ma traään lieân thuoääc cuûûa ñoà thò laøø: : thì tra thuo cu la A e4 e1 D e2 B e7 e3 e6 e5 C Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 38 19
  20. BIEÅU DIEÃN BAÈNG MA TRAÄN NG Goïïi H laøø ñoà thò coùù ñöôïc töø ñoà thò G noùùi treân baèèng caùùch co ñöô Go la no ba ng ca ch boûû ñi höôùng caùùc caïïnh vaøø ta saéép thöù töï caùùc ñænh, caïïnh nhö ng ca ca nh va sa thöù ca ñænh, ca nh nhö bo treân thì ma traään keàà cuûûa ñoà thò laøø: thì tra ke cu la A e4 e1 D e2 B e7 e3 e6 e5 C Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 39 CAÙC THAØNH PHAÀN LIEÂN THOÂNG NH VAØ TÍNH LIEÂN THOÂNG Cho ñoà thò G=(X, U) voâ höôùng hay coùù höôùng. Ta ñònh ng. Cho ng co nghóa moäät quan heää ∼ nhö sau treân taääp ñænh X: nghó mo he nhö ta ñænh ∀i, j∈X, i ∼ j ⇔ (i=j hay coùù daây chuyeààn ñænh ñaàu laøø i vaøø ñænh cuoáái laøø j). chuye ñænh la va ñænh cuo la co Lyù Thuyeát Ñoà Thò - Caùc khaùi nieäm cô baûn - Khoa CNTT - Ñaïi Hoïc KHTN 40 20
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2