Tính liên thông của đồ thị

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

1
433
lượt xem
72
download

Tính liên thông của đồ thị

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

Đồ thị liên thông: một cặp đỉnh bất kỳ được nối với nhau bằng ít nhất một đường đi.

Chủ đề:
Lưu

Nội dung Text: Tính liên thông của đồ thị

  1. Tính lieân thoâng cuûa ñoà thò Tính lieân thoâng cuûa ñoà thò Tính lieân thoâng cuûa ñoà thò. Tính song lieân thoâng. Ñænh khôùp Caàu Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 2 1
  2. Nhaéc laïi moät soá khaùi nieäm Tính lieân thoâng Ñoà thò lieân thoâng: moät caëp ñænh baát kyø ñöôïc noái vôùi nhau baèng ít nhaát moät ñöôøng ñi. ng ng Ñoà thò lieân thoâng Ñoà thò khoâng lieân thoâng Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 4 2
  3. Tính lieân thoâng Thaønh phaàn lieân thoâng: ñoà thò con lieân thoâng toái nh ñaïi cuûa G. Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 5 Quan heä töông ñöông Moät quan heä treân taäp hôïp S laø taäp R caùc caëp coù thöù töï caùc phaàn töû cuûa S ñònh nghóa bôûi moät thuoäc tính naøo ñoù Ví duï: S ={ 1, 2, 3, 4 } R ={ (i,j) ∈ S ´ S sao cho i < j } ={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 6 3
  4. Quan heä töông ñöông Moät quan heä töông ñöông laø quan heä vôùi caùc thuoäc tính sau: Tính phaûn xaï: (x,x) ∈ R, ∀ x ∈ S (reflexive) Tính ñoái xöùng:(x,y) ∈ R ⇒ (y,x) ∈ R ng (symmetric) Tính baéc caàu :(x,y), (y,z) ∈ R⇒ (x,z) ∈ R (transitive) Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 7 Quan heä töông ñöông Quan heä C treân taäp caùc ñænh cuûa ñoà thò: (u,v) Î C Û u vaø v thuoäc cuøng moät thaønh phaàn ng nh lieân thoâng laø quan heä töông ñöông. Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 8 4
  5. DFS treân ñoà thò khoâng lieân thoâng DFS treân ñoà thò khoâng lieân thoâng Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 10 5
  6. DFS treân ñoà thò khoâng lieân thoâng Sau khi thöïc hieän DFS(1): k 1 2 3 4 5 6 7 val[k] 1 4 0 2 0 0 3 Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 11 DFS treân ñoà thò khoâng lieân thoâng Haøm ñeä qui DFS thaêm taát caû caùc ñænh thuoäc thaønh phaàn lieân thoâng. nh Caàn theâm vaøo moät voøng laëp for ñeå thaêm taát caû ng caùc ñænh cuûa ñoà thò: for k = 1 to N do if (val[k] = 0) then dfs(k) Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 12 6
  7. DFS treân ñoà thò khoâng lieân thoâng Caùch bieåu dieãn caùc thaønh phaàn lieân thoâng: ch nh Duøng maûng Comp[1..N] ñeå bieåu dieån: ng ng Comp[k] = i neáu ñænh k ∈ thaønh phaàn lieân nh thoâng i Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 13 DFS treân ñoà thò khoâng lieân thoâng Sau khi thöïc hieään DFS(1): thöï hie DFS(1): k 1 2 3 4 5 6 7 8 val[k] 1 val[k] 1 2 3 2 3 2 1 Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 14 7
  8. Thuaät toaùn DFS xaùc ñònh caùc thaønh phaàn lieân thoâng nh Algorithm DFS(v, id) Algorithm DFS(v, id) Input: Moät ñænh v cuûa ñoà thò, chæ Input: Moät ñænh v cuûa ñoà thò, chæ soá id cuûa tplt soá id cuûa tplt Output: Output: Gaùn nhaõn id cho taát caû Gaùn nhaõn id cho taát caû caùc ñænh cuûa tplt caùc ñænh cuûa tplt Comp[v] Comp[v] =id; =id; for (moïi ñænh k keà vôùi v) do for (moïi ñænh k keà vôùi v) do if Comp[k]= 0 then if Comp[k]= 0 then Goïi ñeä qui DFS(k, id); Goïi ñeä qui DFS(k, id); Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 15 Thuaät toaùn DFS xaùc ñònh caùc thaønh phaàn lieân thoâng nh Algorithm ThanhPhanLT Input: Ñoà thò G Output: Maûng Comp cho bieát caùc tplt Maû bieá caù id = 0; for k = 1 to N do Comp[k] = 0; for k = 1 to N do if (Comp[k] = 0) then id++; DFS(k, id); Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 16 8
  9. Tính song lieân thoâng Caùc ñænh khôùp Ñænh khôùp (cutvertex) laø ñænh neáu khi huyû noù ra khoûi ñoà thò seõ laøm taêng soá thaønh phaàn lieân nh thoâng cuûa ñoà thò Neáu G lieân thoâng, w laø ñænh khôùp cuûa G thì sau khi huyû w, G khoâng coøn lieân thoâng. Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 18 9
  10. Caùc ñænh khôùp Ví duï, ORD vaø DEN laø caùc ñænh khôùp, MSD khoâng phaûi. Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 19 Caùc ñænh khôùp Neáu saân bay DEN (Denver) bò ñoùng cöûa, caùc ng tuyeán bay noái mieàn ñoâng vaø mieàn taây USA seõ bò giaùn ñoaïn, neáu saân bay ORD (Chicago) bò ñoùng ng cöûa, ta khoâng theå ñi töø Providence (PVD) ñeán Denver Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 20 10
  11. Ñoà thò song lieân thoâng Ñoà thò song lieân thoâng (biconnected Graph) laø ñoà thò lieân thoâng vaø khoâng chöùa ñænh khôùp. Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 21 Ñoà thò song lieân thoâng Neáu môû theâm hai tuyeán bay LGA-ATL vaø DFW-LAX, maïng löôùi seõ trôû thaønh ñoà thò song ng nh lieân thoâng. Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 22 11
  12. Ñoà thò song lieân thoâng Moät soá tính chaát cuûa ñoà thò song lieân thoâng: Coù ít nhaát hai ñöôøng ñi khaùc nhau giöõa hai ng ñænh baát kyø. Giöõa hai ñænh baát kyø, toàn taïi chu trình sô caáp ñi qua chuùngng Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 23 Ñoà thò song lieân thoâng Ta qui öôùc, ñoà thò K2 laø ñoà thò song lieân thoâng, maëc duø noù khoâng thoaû hai tính chaát treân Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 24 12
  13. Thaønh phaàn song lieân thoâng nh Thaønh phaàn song lieân thoâng: ñoà thò con song lieân nh thoâng toái ñaïi cuûa G. Maáu choát cuûa vieäc xaùc ñònh tính song lieân thoâng cuõng nhö caùc thaønh phaàn song lieân thoâng laø tìm nh caùch xaùc ñònh caùc ñænh khôùp. ch Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 25 Thaønh phaàn song lieân thoâng nh Caùc thaønh phaàn song lieân thoâng cuûa moät ñoà thò nh khoâng coù caïnh chung nhöng moät ñænh coù theå nh thuoäc nhieàu thaønh phaàn song lieân thoâng (ví duï nh DEN, ORD). Nhöõng ñænh loaïi naøy chính laø caùc ñænh khôùp. Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 26 13
  14. Thuaät toaùn tìm caùc ñænh khôùp Thuaät toaùn Brute-Force (veùt caïn) Huyû moät ñænh ra khoûi ñoà thò, xaùc ñònh tính lieân thoâng cuûa noù. Thöû cho taát caû caùc ñænh cuûa ñoà thò ta seõ coù keát quaû mong muoán Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 28 14
  15. Thuaät toaùn Brute-Force (veùt caïn) Algorithm Brute-Force {tìm ñænh khôùùp} Brute-Force {tìm ñænh khô p} Algorithm Brute- ñænh khôù Input: Input: Ñoà thò lieân thoâng G Ñoà thò lieân thoâng G Output: Output: Danh saùch L caùc ñænh khôùp Danh saù saùch L caù ñænh khôù caùc ñænh khôùp L = ∅; L = ∅; for (moïi ñænh k cuûa G) do for (moïi ñænh k cuû G) do moï ñænh cuûa Huyû k ra khoûi G; Huyû k ra khoû G; Huyû khoûi Kieåm tra tính lieân thoâng cuûa G; Kieå tra ttính lieân thoâng cuû G; Kieåm í cuûa Neáu G khoâng lieân thoâng L = L +[k]; Neá G khoâng lieân thoâng L = L +[k]; Neáu Ñaët k vaøo laïi G; Ñaët k vaø laï G; vaøo laïi Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 29 Thuaät toaùn Brute-Force (veùt caïn) Ñoä phöùc taïp cuûa thuaät toaùn: Caàn n laàn kieåm tra tính lieân thoâng. Moãi laàn kieåm tra toán chi phí O(n + m). Nhö vaäy, toång chi phí seõ laø O(n2 + nm). ng Chi phí nhö vaäy seõ khoaûng O(n3), raát cao. ng Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 30 15
  16. Thuaät toaùn ñaùnh soá DFS nh (DFS numbering) Nhaéc laïi laø khi duyeät caây baèng DFS, caùc caïnh ng nh cuûa ñoà thò ñöôïc chia laøm hai loaïi: caïnh thuoäc nh caây DFS vaø backedge. (u,v) laø caïnh thuoäc caây DFS nh val [u] < val [v] (u,v) laø backedge val[u] > val[v] Ta seõ xaùc ñònh caùc ñænh khôùp thoâng qua caùch ch ñaùnh soá DFS vaø hai thuoäc tính … nh Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 31 Thuaät toaùn ñaùnh soá DFS nh (DFS numbering) Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 32 16
  17. Thuaät toaùn ñaùnh soá DFS nh (DFS numbering) Thuoäc tính 1 (goác): goác (root) cuûa caây DFS laø ñænh khôùp neáu coù 2 hoaëc nhieàu hôn caïnh treân nh caây ñi ra töø noù. Trong quaù trình duyeät, ta ñaõ phaûi quay laïi goác ñeå ñi ñeán nhöõng nuùt coøn laïi trong ñoà thò Khi ñang ñöùng ôû moät caây con cuûa Root, ta chæ ng coù theå ñi ñeán caây con khaùc baèng caùch baêng ng ch qua goác. Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 33 Thuaät toaùn ñaùnh soá DFS nh (DFS numbering) Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 34 17
  18. Thuaät toaùn ñaùnh soá DFS nh (DFS numbering) Thuoäc tính 2 (phöùc hôïp): moät ñænh v khoâng phaûi laø goác cuûa caây DFS laø ñænh khôùp neáu noù coù ñænh con w sao cho khoâng coù backedge naøo noái w vôùi caùc “toå tieân” cuûa v. Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 35 Thuaät toaùn ñaùnh soá DFS nh (DFS numbering) Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 36 18
  19. Thuaät toaùn ñaùnh soá DFS nh (DFS numbering) Moät soá ñònh nghóa: Low(v): ñænh ñöôïc ñaùnh soá vôùi chæ soá nhoû nh nhaát coù theå ñi ñeán ñöôïc töø v baèng caùch duøng ng ch ng moät con ñöôøng coù höôùng (taïo ñöôïc trong quaù ng ng trình duyeät DFS) maø treân ñoù coù toái ña moät caïnh backedge. nh Min(v) = val(low(v)). Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 37 Thuaät toaùn ñaùnh soá DFS nh (DFS numbering) Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 38 19
  20. Thuaät toaùn DFS tìm ñænh khôùp Algorithm DFS {tìm ñænh khôùùp} Algorithm DFS {tìm ñænh khô p} ñænh khôù Input: Ñoà thò lieân thoâng G Input: Ñoà thò lieân thoâng G Output: Danh saùch L caùc ñænh khôùp Output: Danh saù saùch L caù ñænh khôù caùc ñænh khôùp L = ∅; L = ∅; Thöïc hieään DFS treân ñoà thò G Thöï c hie n DFS treân ñoà thò G Thöï hieä Kieååm tra neááu root cuûûa caây DFS coùù ít nhaáátt 2 con Kie m tra ne u root cu a caây DFS co ít nha 2 con Kieå neá cuû coù nhaá ((thoaû maõn thuoääc tính 1) thì L = L +[root] thoaûû maõn thuo c ttính 1) thì L = L +[ root] thoa thuoä í thì +[root] Vôùùi i moãi i ñænh v, kieååm tra neááu coùù caïïnh (v, w) Vô moã ñænh v, kie m tra ne u co ca nh (v, w) Vôù ñænh kieå neá coù caïnh cuûûa caây DFS thoaûû Min(w) ≥ val[v]thì L = L +[v] cu a caây DFS thoa Min(w) ≥ val[v]thì L = L +[ cuû thoaû val[v]thì +[v] Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 39 Thuaät toaùn DFS tìm ñænh khôùp Ñeå xaùc ñònh Min(v) ta coù quan heä sau: Min(v) = val(low(v)) laø soá nhoû nhaát trong caùc giaù trò Val[v] soá nhoû nhaát trong caùc soá Min(w) vôùi (v, w) laø caïnh treân caây nh soá nhoû nhaát trong caùc soá Val[z] vôùi (v, z) laø backedge. Nhö vaäy, ta coù theå xaùc ñinh Min(v) baèng thuaät ng toaùn ñeä qui. Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 40 20

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản