DANH M C HÌNH VỤ Ẽ
Trang
Hình 1.1 Đ th hàm s y = sinxồ ị ố ......................................................................4
Hình 1.2 Đ th bi u di n ví d 1ồ ị ể ễ ụ ...................................................................5
Hình 1.3 Đ th bi u di n ví d 2ồ ị ể ễ ụ ...................................................................6
Hình 1.4 Đ th bi u di n ví d 3ồ ị ể ễ ụ ...................................................................6
Hình 1.5 Bi u di n ph ng c a Graphể ễ ẳ ủ .............................................................7
Hình 1.6 Bi u di n Graph con và Graph thành ph nể ễ ầ ......................................8
Hình 1.7 Bi u di n b c c a đ nhể ễ ậ ủ ỉ .....................................................................9
Hình 1.8 Dãy c nh k ti pạ ế ế ...............................................................................9
Hình 1.9 Bi u di n c nh có h ngể ễ ạ ướ ...............................................................12
Hình 2.1 Ma tr n k đ th vô h ng không tr ng s và đ th có h ng cóậ ề ồ ị ướ ọ ố ồ ị ướ
tróng số...........................................................................................................14
Hình 2.2 Bi u di n cài đ t đ th b ng danh sách c nh trên m ng và trênể ễ ặ ồ ị ằ ạ ả
danh sách móc n iố..........................................................................................17
Hình 2.3 Đ th vô h ng không tr ng sồ ị ướ ọ ố....................................................20
Hình 2.4 Bi u di n Graph b ng danh sách kể ễ ằ ề..............................................22
Hình 2.5 Đ th vô h ngồ ị ướ ..............................................................................24
Hình 2.6 Ma tr n k đ th tr ng s vô h ng và đ th tr ng s có h ngậ ề ồ ị ọ ố ướ ồ ị ọ ố ướ
31
Hình 2.7a Đ th tr ng s có h ng ồ ị ọ ố ướ .............................................................31
Hình 2.7b Bi u di n đ th tr ng s b ng danh sách lân c n kể ễ ồ ị ọ ố ằ ậ ề.................31
Hình 2.8 Đ th vô h ng có tr ng s ồ ị ướ ọ ố ví d 4ụ..............................................33
Hình 2.9 Cây khung DFS(1) và cây khung BFS(1)........................................37
Hình 2.10 Đ th vô h ng có tr ng s ồ ị ướ ọ ố ví d 5ụ............................................40
M C L CỤ Ụ
Trang
M Đ UỞ Ầ ..........................................................................................................1
Ch ng 1ươ
M T S V N Đ V LÝ THUY T GRAPHỘ Ố Ấ Ề Ề Ế ...........................................4
1.1. Khái ni m c b n v graphệ ơ ả ề ...................................................................4
1.1.1. Nh ng bài toán và v n đ d n đ n khái ni m graph [1]ữ ấ ề ẫ ế ệ ...............4
1.1.2. Đ nh nghĩa graph và các khái ni m c b nị ệ ơ ả .....................................7
1.1.3. Graph con và graph thành ph nầ.......................................................8
1.2. Phân lo i graphạ.......................................................................................9
1.2.1. Graph vô h ngướ ...............................................................................9
1.2.2. Graph có h ngướ .............................................................................12
1.3. K t lu n ch ng 1ế ậ ươ ...............................................................................13
Ch ng 2ươ
M T S THU T TOÁN C B N TRÊN GRAPHỘ Ố Ậ Ơ Ả ...............................14
2.1. Bi u di n graph trên máy tínhể ễ ............................................................14
2.1.1. Bi u di n b ng ma tr n lân c n [6]ể ễ ằ ậ ậ .............................................14
2.1.2. Bi u di n b ng danh sách c nh [6]ể ễ ằ ạ ..............................................17
2.1.3. Bi u di n danh sách lân c n [6]ể ễ ậ ....................................................19
2.2. Phép duy t m t graphệ ộ ..........................................................................24
2.2.1. Tìm ki m theo chi u sâuế ề ...............................................................25
2.2.2. Tìm ki m theo chi u r ngế ề ộ .............................................................26
2.2.3. Tìm đ ng đi và ki m tra tính liên thông c a đ thườ ể ủ ồ ị....................28
2.3. Đ th tr ng sồ ị ọ ố.....................................................................................30
2.3.1. Khái ni mệ.......................................................................................30
2.3.2. Bi u di n đ th tr ng sể ễ ồ ị ọ ố..............................................................30
2.4. Đ ng đi trên đ th tr ng sườ ồ ị ọ ố..............................................................32
2.4.1. Thu t toán tìm đ ng đi ng n nh t t m t đ nh đ n t t c cácậ ườ ắ ấ ừ ộ ỉ ế ấ ả
đ nh khácỉ..................................................................................................32
Đ ph c t p c a gi i thu t: Thu t toán Dijkstra tìm đ c đ ng điộ ứ ạ ủ ả ậ ậ ượ ườ
ng n nh t trên đ th sau th i gian c O(n2). [2]ắ ấ ồ ị ờ ỡ ...................................33
Ví d 4: Cho đ th vô h ng có tr ng s G trong hình 2.8 d i đ y.ụ ồ ị ướ ọ ố ướ ấ
Tìm đ ng đi ng n nh t t đ nh 1 đ n t t c các đ nh khác trong G.ườ ắ ấ ừ ỉ ế ấ ả ỉ ..33
Ma tr n tr ng s c a đ th có d ng:ậ ọ ố ủ ồ ị ạ .....................................................33
K t qu tính toán theo thu t toán đ c trình bày trong b ng d i đây.ế ả ậ ượ ả ướ
Quy c vi t hai thành ph n c a nhãn theo th t : d[v], Truoc[v]. Đ nhướ ế ầ ủ ứ ự ỉ
đ c đánh d u ‘*’ là đ nh đ c ch n đ c đ nh nhãn b c l p đangượ ấ ỉ ượ ọ ể ố ị ở ướ ặ
xét, nhãn c a nó không bi n đ i các b c ti p theo, vì th ta đánhủ ế ổ ở ướ ế ế
d u -.ấ........................................................................................................34
B c l pướ ặ ..................................................................................................34
Đ nh 1ỉ.......................................................................................................34
Đ nh 2ỉ.......................................................................................................34
Đ nh 3ỉ.......................................................................................................34
Đ nh 4ỉ.......................................................................................................34
Kh i t oở ạ ...................................................................................................34
0, 1............................................................................................................34
10, 1..........................................................................................................34
6, 1............................................................................................................34
2, 1*..........................................................................................................34
1................................................................................................................34
-.................................................................................................................34
5, 4............................................................................................................34
3, 4 *.........................................................................................................34
-.................................................................................................................34
2................................................................................................................34
-.................................................................................................................34
5, 4 *.........................................................................................................34
-.................................................................................................................34
-.................................................................................................................34
.................................................................................................................34
Nh n xét: T b ng k t qu ta có th truy xu t ra đ c đ ng đi tậ ừ ả ế ả ể ấ ượ ườ ừ
đ nh 1 t i t t c các đ nh còn l i trong đ th nh sau:ỉ ớ ấ ả ỉ ạ ồ ị ư .........................34
Đ ng đi t đ nh 1 t i đ nh 2: ườ ừ ỉ ớ ỉ ................................................................34
Ta có đ nh tr c đ nh 2 là Truoc[2] = 4 v y 4 là đ nh tr c đ nh 2 trênỉ ướ ỉ ậ ỉ ướ ỉ
đ ng đi này.ườ ...........................................................................................34
Tr c đ nh 4 là Truoc[4] = 1 v y 1 là đ nh tr c đ nh 4 trên đ ng điướ ỉ ậ ỉ ướ ỉ ườ
này............................................................................................................34
D ng, ta thu đ c đ ng đi ng n nh t t đ nh 1 t i đ nh 2 là:ừ ượ ườ ắ ấ ừ ỉ ớ ỉ ............34
1 – 4 – 2 v i đ dài đ ng đi ng n nh t là d[2] = 5.ớ ộ ườ ắ ấ ..........................34
T ng t ta có các đ ng đi sau:ươ ự ườ ............................................................34
Đ ng đi ng n nh t t đ nh 1 đ n đ nh 3 là: 1 – 4 – 3 v i đ dài đ ngườ ắ ấ ừ ỉ ế ỉ ớ ộ ườ
đi ng n nh t là d[3] = 3.ắ ấ ..........................................................................34
Đ ng đi ng n nh t t đ nh 1 đ n đ nh 4 là: 1 – 4 v i đ dài đ ng điườ ắ ấ ừ ỉ ế ỉ ớ ộ ườ
ng n nh t là d[4]=2.ắ ấ ................................................................................34
2.4.2. Thu t toán Floyd tìm đ ng đi ng n nh t gi a t t c các c pậ ườ ắ ấ ữ ấ ả ặ
đ nhỉ...........................................................................................................34
- Kh i t o: ở ạ ..................................................................................................36
.....................................................................................................................36
Nh n xét: Đ ng đi t đ nh 1 t i các đ nh còn l i trong đ th :ậ ườ ừ ỉ ớ ỉ ạ ồ ị ...............36
Đ ng đi t đ nh 1 đ n đ nh 2: ườ ừ ỉ ế ỉ .................................................................36
Tr c 2 là p[1,2]=4 v y 4 là đ nh tr c 2 trên đ ng đi này. ướ ậ ỉ ướ ườ ..................36
Tr c 4 là p[1,4]=0, v y đ nh 1 đ ng tr c đ nh 4 trên đ ng đi này.ướ ậ ỉ ứ ướ ỉ ườ ....36
D ng, đ ng đi thu đ c là: 1 – 4 – 2 v i đ dài đ ng đi là d[1,2] = 5.ừ ườ ượ ớ ộ ườ
......................................................................................................................36
T ng t ta tìm đ c đ ng đi ng n nh t t đ nh 1 đ n đ nh 3 là: 1 – 4 –ươ ự ượ ườ ắ ấ ừ ỉ ế ỉ
3 v i đ dài d[1,3] = 3. ớ ộ ...............................................................................37
Do p[1,4] = 0 nên đ ng đi t đ nh m t t i đ nh 4 là đ ng đi tr c ti pườ ừ ỉ ộ ớ ỉ ườ ự ế
v i đ dài là p[1,4]= 2.ớ ộ ................................................................................37
Đ tìm đ ng đi gi a t t c c p đ nh còn l i trong đ th ta làm t ngể ườ ữ ấ ả ặ ỉ ạ ồ ị ươ
t .ự.................................................................................................................37
2.5. Cây khung và cây khung v i giá tr c c ti uớ ị ự ể .......................................37
2.6. K t lu n ch ng 2ế ậ ươ ...............................................................................46
Ch ng 3ươ
NG D NG GRAPH GI I M T S BÀI TOÁN TRONGỨ Ụ Ả Ộ Ố ...................47
CH NG TRÌNH TIN H C PH THÔNGƯƠ Ọ Ổ ............................................47
3.1. Gi i thi u m t s bài toán v đ th trong ch ng trình tin h c trungớ ệ ộ ố ề ồ ị ươ ọ
h c ph thôngọ ổ ..............................................................................................47
3.2. M t s bài toán v phép duy t đ thộ ố ề ệ ồ ị.................................................47
3.2.1. Bài toán 1- Đ m s thành ph n liên thông [4]ế ố ầ ..............................48
3.2.2. Bài toán 2 - D ti c ự ệ ....................................................................50
3.2.3. Bài toán 3 - B n đ [2]ả ồ ..................................................................52
3.3. M t s bài toán v đ ng đi trong đ thộ ố ề ườ ồ ị...........................................53
3.3.1. Bài toán 1 - Đ ng đi [4]ườ ...............................................................53
3.3.2. Bài toán 2 - Du l ch [4]ị...................................................................56
3.3.3. Bài toán 3 - Đ n tr ng [7]ế ườ ...........................................................58
3.4. M t s bài toán v cây khung đ thộ ố ề ồ ị...................................................61
3.4.1. Bài toán 1 - D ánự.........................................................................61
3.4.2. Bài toán 2 - Thay h th ng [4]ệ ố ......................................................64
3.4.3. Bài toán 3 – Bão S n Tinhơ.............................................................67
3.5. K t lu n ch ng 3ế ậ ươ ...............................................................................70