intTypePromotion=1

Cây trong đồ thị

Chia sẻ: Trần Huy | Ngày: | Loại File: PDF | Số trang:0

0
99
lượt xem
24
download

Cây trong đồ thị

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 'cây trong đồ thị', công nghệ thông tin, kỹ thuật lập trình 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: Cây trong đồ thị

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

 

Đồng bộ tài khoản