Bài giảng: Các thuật toán trên đồ thị

- Thành ph n liên thông và thành ph n liên thông ầ ầ m nh ạ.
- Đ th đ nh h ồ ị ị ướ ng không có chu trình.
- Đ ườ ng đi ng n nh t ắ ấ.
- B n đ đ ả ồ ườ ng đi gi a các thành ph ữ ố.
- Tìm đ ườ ng đi ng n nh t ắ ấ.
- M t đ th đ nh h ộ ồ ị ị ướ ng G = <V, E>.
- V là t p các đ nh, E là t p các cung n i các đ nh ậ ỉ ậ ố ỉ.
- Đ th đ nh h ồ ị ị ướ ng.
- M t đ th vô h ộ ồ ị ướ ng G = <V, E>.
- V là t p các đ nh, E là t p các c nh n i các đ nh ậ ỉ ậ ạ ố ỉ.
- Đ th vô h ồ ị ướ ng.
- Đ ườ ng đi đ n ơ.
- Là m t dãy h u h n các đ nh (v ộ ữ ạ ỉ 0 , v 1.
- V i đ th có tr ng s đ dài đ ớ ồ ị ọ ố ộ ườ ng đi đ ượ c tính là t ng tr ng ổ ọ s trên các c nh trên đ ố ạ ườ ng đi.
- Chu trình.
- Là đ ườ ng đi khép kín, t c là đ ứ ườ ng đi (v 0 , v 1.
- Trong đ th đ nh h ồ ị ị ướ ng d ướ i đây thì (v 4 , v 1 , v 2 , v 3 ) là m t ộ đ ườ ng đi t v ừ 4 đ n v ế 3 , và (v 4 , v 1 , v 2 , v 4 ) là m t chu trình ộ.
- Đ th G’=<V’, E’>.
- Ví d 1 ụ : cho đ th vô h ồ ị ướ ng.
- Ví d 2 ụ : cho đ th đ nh h ồ ị ị ướ ng.
- Ví d 1 ụ : cho đ th đ nh h ồ ị ị ướ ng.
- Đ th đ nh h ồ ị ị ướ ng 12.
- V i m i đ nh, l p m t danh sách các đ nh k v i nó ớ ỗ ỉ ậ ộ ỉ ề ớ.
- Danh sách các đ nh k là m t danh sách móc n i ỉ ề ộ ố.
- S d ng m ng A[1..n], trong đó A[i] là con tr tr t i đ u ử ụ ả ỏ ỏ ớ ầ danh sách các đ nh k c a đ nh th I ỉ ề ủ ỉ ứ.
- Nh ượ c đi m: ể mu n bi t có cung/c nh (v ố ế ạ i , v j ) hay không (và tr ng s c a nó) ta ph i duy t danh sách các đ nh k c a v ọ ố ủ ả ệ ỉ ề ủ i.
- cho đ th đ nh h ồ ị ị ướ ng.
- T đ nh u l n l ừ ỉ ầ ượ t thăm các đ nh v k u và ch a ỉ ề ư đ ượ c thăm..
- Đ nh v nào đ ỉ ượ c thăm tr ướ c thì các đ nh k nó cũng ỉ ề đ ượ c thăm tr ướ c.
- Thu t toán ậ.
- S d ng hàng đ i Q đ l u các đ nh đã đ ử ụ ợ ể ư ỉ ượ c thăm nh ng ch a thăm các đ nh k c a nó ư ư ỉ ề ủ.
- S d ng m ng father[1..n] đ l u l i v t c a đ ử ụ ả ể ư ạ ế ủ ườ ng đi xu t phát t đ nh u, father[w.
- Danh sách các đ nh k c a v ký hi u là Adj(v) ỉ ề ủ ệ.
- Chú ý: n u G là đ th không có tr ng s thì khi g i th t c ế ồ ị ọ ố ọ ủ ụ BFS(u) tìm ra đ ườ ng đi ng n nh t t u đ n các đ nh có th ắ ấ ừ ế ỉ ể đ t t i t u, s d ng m ng father đ xây d ng đ ạ ớ ừ ử ụ ả ể ự ườ ng đi ng n ắ nh t tìm ra.
- Th t các đ nh đ ứ ự ỉ ượ c thăm:.
- THÀNH PH N LIÊN THÔNG Ầ.
- Đ th vô h ồ ị ướ ng G=<V, E>.
- đ ượ c g i là liên thông n u t n ọ ế ồ t i đ ạ ườ ng đi n i m i c p đ nh c a nó.
- N u G không liên thông thì m t đ th con liên thông c c đ i ế ộ ồ ị ự ạ c a G đ ủ ượ c g i là m t thành ph n liên thông ọ ộ ầ.
- Áp d ng thu t toán tìm ki m theo chi u sâu, s tìm đ ụ ậ ế ề ẽ ượ ấ c t t c các thành ph n liên thông.
- Th t c Comp_Search(G), tìm các thành ph n liên thông ủ ụ ầ.
- Bi n c đ m s thành ph n liên thông ế ế ố ầ.
- Th t c Comp(u) đi theo đ sâu t u, và gán cho các đ nh ủ ụ ộ ừ ỉ đ t t i t u m t s hi u thành ph n liên thông c nào đó ạ ớ ừ ộ ố ệ ầ.
- THÀNH PH N LIÊN THÔNG M NH Ầ Ạ.
- đ ượ c g i là liên ọ thông m ng n u m i c p đ nh (u,v) c a nó đ u ạ ế ọ ặ ỉ ủ ề t n t i đ ồ ạ ườ ng đi t u đ n v và t v đ n u.
- Trong đ th đ nh h ồ ị ị ướ ng không liên thông m nh ạ ta g i m t đ th con liên thông m nh c c đ i ọ ộ ồ ị ạ ự ạ c a nó là m t thành ph n liên thông m nh.
- S d ng thu t toán tìm ki m theo chi u sâu, ta ử ụ ậ ế ề có th xây d ng đ ể ự ượ c thu t toán xác đ nh thành ậ ị ph n liên thông m nh, g m các b ầ ạ ồ ướ c:.
- TÌM THÀNH PH N LIÊN THÔNG M NH Ầ Ạ.
- Duy t đ th theo chi u sâu và đánh s các đ nh c a nó theo ệ ồ ị ề ố ỉ ủ th t sau (post_visited) ứ ự.
- Xây d ng đ th G’ t đ th G b ng cách đ i h ự ồ ị ừ ồ ị ằ ổ ướ ng t t c ấ ả các cung.
- Khi đi t u mà ch a thăm h t các đ nh c a G’ thì l i ớ ấ ừ ư ế ỉ ủ ạ duy t G’ b t đ u t đ nh w có pre_visited[w] l n nh t trong ệ ắ ầ ừ ỉ ớ ấ các đ nh còn l i.
- L p l i quá trình cho đ n khi t t c các đ nh ỉ ạ ặ ạ ế ấ ả ỉ c a G’ đ ủ ượ c thăm.
- M i cây nh n đ ỗ ậ ượ ở ướ c b c 3 là m t thành ph n liên thông ộ ầ m nh c a đ th G.
- Đ th đ nh h ồ ị ị ướ ng G.
- Các thành ph n liên ầ thông m nh c a G ạ ủ.
- TÌM Đ ƯỜ NG ĐI NG N NH T Ắ Ấ.
- Duy t đ th theo chi u r ng đ tìm đ ệ ồ ị ề ộ ể ườ ng đi ng n nh t ắ ấ.
- là đ th đ nh h ả ế ồ ị ị ướ ng có tr ng s ọ ố.
- Đ dài đ ộ ườ ng đi t v ừ 0 đ n v ế k là δ(v 0 ,v k.
- Tìm đ ườ ng đi ng n nh t t m t đ nh ngu n đ n các đ nh ắ ấ ừ ộ ỉ ồ ế ỉ còn l i c a đ th ạ ủ ồ ị.
- Tìm đ ườ ng đi ng n nh t gi a m i c p đi m c a đ th ắ ấ ữ ọ ặ ể ủ ồ ị.
- Đ ƯỜ NG ĐI NG N NH T T M T Đ NH Ắ Ấ Ừ Ộ Ỉ NGU N – THU T TOÁN Dijkstra Ồ Ậ.
- ng n nh t ngu n đ n trên đ th đ nh h ắ ấ ồ ơ ồ ị ị ướ ng có tr ng s ọ ố.
- THU T TOÁN Dijkstra Ậ.
- T p S l u các đ nh mà đ ậ ư ỉ ườ ng đi ng n nh t t i chúng đã tìm đ ắ ấ ớ ượ c.
- M ng D[2..n] v i m i D[u] l u đ dài đ ả ớ ỗ ư ộ ườ ng đi ng n nh t t 1 đ n u ắ ấ ừ ế.
- Khi S=V thì D[u] l u đ dài đ ư ộ ườ ng đi ng n nh t t 1 đ n u, v i ắ ấ ừ ế ớ u=2...n.
- M ng P[2..n] l u v t c a đ ả ư ế ủ ườ ng đi, P[w]=v n u w k v trên đ ế ề ườ ng đi.
- CÂY BAO TRÙM NG N NH T Ắ Ấ.
- là đ th vô h ồ ị ướ ng v i c(u,v)≥0, (u,v) ớ ∈ E.
- Gi s G là đ th liên thông ả ử ồ ị.
- G i T là cây bao trùm c a đ th G n u T là đ th con liên ọ ủ ồ ị ế ồ ị thông, không có chu trình và ch a t t c các đ nh c a G ứ ấ ả ỉ ủ.
- Đ dài c a cây T là t ng đ dài c a các c nh t o thành ộ ủ ổ ộ ủ ạ ạ cây.
- Đ th vô h ồ ị ướ ng, liên thông G.
- Cây bao trùm ng n nh t c a G ắ ấ ủ.
- Thu t toán s d ng t p U ch a các đ nh k các c nh trong ậ ử ụ ậ ứ ỉ ề ạ T, ban đ u U ch a m t đ nh b t kỳ trong G ầ ứ ộ ỉ ấ.
- T là t p các c nh trong G, ban đ u T r ng ậ ạ ầ ỗ.
- Đ ƯỜ NG ĐI-CHU TRÌNH EULER.
- Bài toán: Có t n t i chu trình đ n trong đa đ th ch a ồ ạ ơ ồ ị ứ t t c các c nh? ấ ả ạ.
- Đ nh nghĩa: ị Đ ườ ng đi/Chu trình đ n ch a t t c các c nh ơ ứ ấ ả ạ c a đ th G đ ủ ồ ị ượ c g i là Đ ọ ườ ng đi/chu trình Euler..
- Không có chu trình hay đ ườ ng đi Euler.
- Đ ườ ng đi Euler a, c, d, e, b, d, a, b.
- Đi u ki n c n và đ cho chu trình/đ ề ệ ầ ủ ườ ng.
- Đ nh lý 1 ị : M t đa đ th liên thông có chu trình Euler ộ ồ ị khi và ch khi m i đ nh c a nó đ u có b c ch n ỉ ỗ ỉ ủ ề ậ ẵ.
- Đ nh lý 2 ị : M t đa đ th liên thông có đ ộ ồ ị ườ ng đi Euler nh ng không có chu trình Euler khi và ch khi nó có ư ỉ đúng hai đ nh b c l ỉ ậ ẻ.
- THU T TOÁN TÌM CHU TRÌNH EULER Ậ.
- là m t đa đ th liên thông và có t t c các ộ ồ ị ấ ả.
- Output: Chu trình Euler.
- T p S l u các đ nh mà chu trình Euler đi qua, Ban đ u S ch a 1 ậ ư ỉ ầ ứ đ nh u nào đó, v ỉ ∈ V..
- Ti p t c quá trình cho đ n khi lo i b h t các c nh c a G ế ụ ế ạ ỏ ế ạ ủ.
- Đ ƯỜ NG ĐI-CHU TRÌNH HAMILTON.
- Output: Có hay không m t chu trình đi qua t t c các đ nh c a ộ ấ ả ỉ ủ đ th m i đ nh đúng m t l n? ồ ị ỗ ỉ ộ ầ.
- v n ) v i v ớ i ≠ v j (0 ≤ i ≠ j ≤ n) đ ượ c g i là đ ọ ườ ng đi Hamilton.
- v n , v 0 ) là chu trình Hamilton n u (v ế 0 , v 1.
- v n ) là đ ườ ng đi Hamilton.
- Không có chu trình và đ ườ ng đi Hamilton.
- Có chu trình Hamilton.
- Đ n đ th G = <V, E>, liên thông có n đ nh, trong đó n ≥ 3 ơ ồ ị ỉ.
- G có chu trình Hamilton khi và ch khi m i đ nh c a nó ỉ ỗ ỉ ủ đ u có b c ≥ [n/2] ề ậ.
- THU T TOÁN TÌM CHU TRÌNH HAMILTON Ậ.
- Ch n đ nh v trong danh sách các đ nh k c a u ọ ỉ ỉ ề ủ IF (H[v

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt