CH
NG 2
ƯƠ
BI U DI N Đ TH TRÊN MÁY TÍNH
Ồ Ị
Ễ
Ể
ọ ố ơ
i,j : i,j=1, 2,. . . ,n} v i aớ i, j = 0, n u (i,j)
ˇ ˛ E, i, j=1, 2,. . .,n. E và ai,j = 1 , n u (i,j) ế ế 1. Ma tr n k , ma tr n tr ng s ậ ề ậ Xét đ n đ th G=(V,E) ồ ị a) Ma tr n k : ậ ề Ma tr n A={a ậ g i là ma tr n k c a đ th G. ậ ọ ề ủ ồ ị
Ví d : ụ
ng G và Đ th có h ng ồ ị ướ ồ ị ướ
Hình 1. Đ th vô h G 11
1 2 3 4 5 6 1 2 3 4 5 6
1 0 1 1 0 1 0 1 0 1 1 0 0 0
2 1 0 1 0 1 0 2 0 0 0 0 0 0
3 1 1 0 1 0 0 3 0 1 0 1 0 0
4 0 0 1 0 1 1 4 0 0 0 0 0 0
5 1 1 0 1 0 1 5 0 0 0 1 0 1
6 0 0 0 1 1 0 6 0 0 0 0 1 0
Ma tr n k c a G ề ủ ậ Ma tr n k c a G 1 ề ủ ậ
p =A.A. . .A (p th a s ) ừ ố ỉ
ng: ậ ề ủ ồ ị ướ ấ ủ ố ứ ầ ừ ỉ trên dòng i (c t j) b ng b c c a đ nh i (đ nh j). c a ma tr n A * Tính ch t c a ma tr n k c a đ th vô h - Tính đ i x ng: a[i,j]=a[j,i], i,j=1,2,. . .,n. - T ng các ph n t ằ ổ - G i aọ jị ậ ủ ỉ ậ ng đi khác nhau t đ nh i đ n đ nh j qua p-1 đ nh trung gian. Khi đó: a jị ộ p , i,j=1, 2,. . . ,n là ph n t ầ ử ủ p , i,j=1, 2,. . . ,n là s đ ố ườ ừ ỉ ế ỉ
ng: ậ ề ủ ồ ị ướ ố ứ * Tính ch t c a ma tr n k c a đ th có h ấ ủ - Không có tính đ i x ng - T ng các ph n t trên dòng i b ng bán b c ra c a đ nh i và t ng các ph n t trên c t j b ng bán ầ ừ ủ ỉ ầ ừ ậ ằ ổ ằ ộ
ng ổ b c vào c a đ nh j. ậ - Gi ng t/ch 3 c a vô h ố ủ ỉ ủ ướ
1
* Ma tr n k c a đa đ th : ậ ề ủ ồ ị a[i,j]=s c nh (cung) n i hai đ nh i, j. ố ạ ố ỉ
ậ ọ ồ ị ố ủ ạ ộ ọ ọ ị ồ ị ố ử ụ ỗ ạ ố ậ ọ
ˇ E
˛ ế ế ¥ E và c[i,j]=q n u (i,j) c đ t b ng m t trong các giá tr sau: 0, + , - ¥ . b) Ma tr n tr ng s : ố Đ th có tr ng s là đ th mà m i c nh (i,j) có m t giá tr c(i,j) g i là tr ng s c a c nh. Đ bi u ể ể ồ ị ọ di n đ th ta s d ng ma tr n tr ng s C= {c[i,j], i,j=1, 2,. . .,n} ễ v i ớ c[i,j]=c(i,j) n u (i,j) trong đó s ố q có th đ ể ượ ặ ằ ộ ị
ng pháp bi u di n đ th b ng ma tr n k (ho c ma tr n tr ng s ) là đ ớ ươ ể ề ậ ậ ọ ố ấ ủ ỉ ễ ồ ị ặ ỉ ả ự ệ ể ồ ị ằ i câu h i: Hai đ nh u,v có k nhau trên đ th hay không, chúng ta ch ph i th c hi n m t phép so ng pháp này là: không ph thu c vào s c nh c a đ th , ta luôn ộ ủ ồ ị ấ ủ ố ạ ụ ớ ộ u đi m l n nh t c a ph Ư ể tr l ề ỏ ả ờ sánh. nh c đi m l n nh t c a ph ể ượ 2 đ n v b nh đ l u tr ma tr n k c a nó. ph i s d ng n ả ử ụ ươ ớ ể ư ề ủ ị ộ ữ ậ ơ
ậ 2. Ma tr n liên thu c đ nh-c nh ạ ng. Ma tr n liên thu c đ nh-c nh có d ng: Xét G=(V, E) là đ n đ th có h ộ ỉ ướ ơ ộ ỉ ồ ị ậ ạ ạ
ỉ ầ ủ
ỉ = a ij ế ế ế ủ 1, n u i là đ nh đ u c a cung e j -1, n u i là đ nh cu i c a cung e ố ủ j 0, n u i không là đ u mut c a cung e ầ j Ví d : Hinh 2 ụ 2 4
1 6
3 5
A=
1 2 3 4 5 6 (1,2) 1 -1 0 0 0 0 (1,3) 1 0 -1 0 0 0 (2,3) 0 1 -1 0 0 0 (2,4) 0 1 0 -1 0 0 (3,5) 0 0 1 0 -1 0 (4,5) 0 0 0 1 0 0 (4,6) 0 0 0 1 0 -1 (5,2) 0 -1 0 0 1 0 (5,6) 0 0 0 0 1 -1
i ta th ườ ạ ợ ố ạ ườ ng ấ ẳ ườ ứ ả ồ ị ướ ạ ồ ị i d ng danh sách c nh. ạ ấ ả ộ ạ ễ ữ ủ ồ ị ể ư ư ậ ế c đi m c a cách bi u di n này tìm các đ nh k v i m t đ nh cho tr ủ ể ễ ủ ồ ị ị ộ ơ c chúng ta ph i làm ng h p đ th có ườ ả ồ ị ấ ả ệ ợ 3. Danh sách c nh (cung) ng h p đ th th a (đ th có s c nh m tho mãn b t d ng th c: m<6n) ng Trong tr ồ ị ư dùng cách bi u di n đ th d ạ ể Chúng ta s l u tr danh sách t t c các c nh (cung) c a đ th . M t c nh (cung) e=(x,y) c a đ th ẽ ư s t ng ng v i hai bi n Dau[e], Cuoi[e]. Nh v y, đ l u tr đ th ta c n s d ng 2m đ n v b ớ ẽ ươ ứ ữ ồ ị nh . Nh ể ượ ớ ộ ỉ ỉ c m phép so sánh (khi duy t qua danh sách t ủ ồ ị ỡ tr ng s ta c n thêm m đ n v b nh đ l u tr tr ng s c a các c nh. ạ ị ộ ớ ể ư ọ ầ ử ụ ướ t c các c nh c a đ th ). Trong tr ữ ọ ề ớ ạ ố ủ ầ ơ ố
Ví d : ụ
2
1) ( hình 1)
Dau Cuoi
Dau Cuoi
1
2
1
2
1
3
1
3
1
5
3
2
2
3
3
4
2
5
5
4
3
4
5
6
4
5
6
5
4
6
5
6
D/s c nh (cung) c a G (G ủ ạ
D/s c nh c a G D/s cung c a G1 ủ ạ ủ
4. Danh sách kề
˛ V: (v,u)˛ E} ư ữ ỗ ỉ ề ớ ỉ
ỉ Danh sách k c a G1 (hình 1) ề ủ Đ nh đ u ầ V i m i đ nh v, ta l u tr danh sách các đ nh k v i v: Ke(v)={u ớ Ví d : ụ Danh sách k c a G (hình 1 ) ề ủ Đ nh đ u ầ ỉ
Trong cách bi u di n này chúng ta c n ph i s d ng c m+n đ n v b nh . ị ộ ớ ả ử ụ ễ ể ầ ỡ ơ
3
