Graph và một số ứng dụng trong chương trình THPT

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 ể ễ

.....................................................................9 Hình 1.7 Bi u di n b c c a đ nh ễ ậ ủ ỉ ể

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

ng không tr ng s và đ th có h ng có Hình 2.1 Ma tr n k đ th vô h ậ ề ồ ị ướ ồ ị ọ ố ướ

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 ề ồ ị ọ ậ ố ướ ồ ị ọ ố ướ

ng .............................................................31 Hình 2.7a Đ th tr ng s có h ồ ị ọ ố ướ

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 ế ậ ươ

2 Ch ng ươ

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 ể ễ ậ

..........................................................................24 2.2. Phép duy t m t graph ệ ộ

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

m t đ nh đ n t t c các 2.4.1. Thu t toán tìm đ ậ ườ ng đi ng n nh t t ắ ấ ừ ộ ỉ ế ấ ả

..................................................................................................32 đ nh khác ỉ

i thu t: Thu t toán Dijkstra tìm đ c đ ng đi Đ ph c t p c a gi ứ ạ ủ ộ ả ậ ậ ượ ườ

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 đ đ nh 1 đ n t t c các đ nh khác trong G. . .33 ườ ng đi ng n nh t t ắ ấ ừ ỉ ế ấ ả ỉ

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 l p đang b ượ ấ ỉ ượ c ch n đ c đ nh nhãn ể ố ị ọ ở ướ ặ

xét, nhãn c a nó không bi n đ i các b c ti p theo, vì th ta đánh ổ ở ủ ế ướ ế ế

........................................................................................................34 d u -.ấ

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

Nh n xét: T b ng k t qu ta có th truy xu t ra đ c đ ng đi t ừ ả ế ể ậ ả ấ ượ ườ ừ

i t i trong đ th nh sau: .........................34 đ nh 1 t ỉ ớ ấ ả t c các đ nh còn l ỉ ạ ồ ị ư

Đ 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 đ đ nh 1 t i đ nh 2 là: ............34 ừ c đ ượ ườ ng đi ng n nh t t ắ ấ ừ ỉ ớ ỉ

1 – 4 – 2 v i đ dài đ ..........................34 ớ ộ ườ ng đi ng n nh t là d[2] = 5. ấ ắ

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

..........................................................................34 đi ng n nh t là d[3] = 3. ấ ắ

Đ 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 ắ ấ

...........................................................................................................34 đ nhỉ

- Kh i t o: ở ạ ..................................................................................................36

.....................................................................................................................36

Nh n xét: Đ ng đi t đ nh 1 t i trong đ th : ườ ậ ừ ỉ ớ i các đ nh còn l ỉ ạ ồ ị ...............36

Đ ng đi t .................................................................36 ườ ừ ỉ đ nh 1 đ n đ nh 2: ế ỉ

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 đ nh 4 trên đ ng đi này. ....36 ướ c 4 là p[1,4]=0, v y đ nh 1 đ ng tr ậ ứ ỉ ướ ỉ ườ

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 ự

................................................................................37 v i đ dài là p[1,4]= 2. ớ ộ

Đ tìm đ ng đi gi a t t c c p đ nh còn l ể ườ ữ ấ ả ặ ỉ ạ i trong đ th ta làm t ồ ị ươ ng

.ự .................................................................................................................37 t

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 ươ

...................47 Ứ NG D NG GRAPH GI I M T S BÀI TOÁN TRONG Ả Ộ Ố Ụ

CH ............................................47 ƯƠ NG TRÌNH TIN H C PH THÔNG Ọ Ổ

3.1. Gi i thi u m t s bài toán v đ th trong ch ng trình tin h c trung ớ ề ồ ị ộ ố ệ ươ ọ

..............................................................................................47 h c ph thông ổ ọ

3.2. M t s bài toán v phép duy t đ th ệ ồ ị.................................................47 ộ ố ề

..............................48 3.2.1. Bài toán 1- Đ m s thành ph n liên thông [4] ố ế ầ

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 ế ậ ươ

K T LU N Ậ ....................................................................................................71 Ế

TÀI LI U THAM KH O Ả ............................................................................72 Ệ

M Đ UỞ Ầ

1. Lý do ch n đ tài ọ ề

Trên th c t có nhi u bài toán liên quan t i m t t p các đ i t ng và ự ế ề ớ ộ ậ ố ượ

nh ng m i liên h gi a chúng, đòi h i toán h c ph i đ t ra m t mô hình ỏ ệ ữ ả ặ ữ ố ộ ọ

bi u di n m t cách ch t ch và t ng quát b ng ngôn ng ký hi u, đó là đ ữ ẽ ệ ễ ể ặ ằ ộ ổ ồ

c đ a ra t th k th XVIII b i nhà th . Nh ng ý t ữ ị ưở ng c b n c a nó đ ơ ả ủ ượ ư ừ ế ỷ ứ ở

toán h c Th y Sĩ Leonhard Euler, ông đã dùng mô hình đ th đ gi i bài ồ ị ể ả ụ ọ

toán v nh ng cây c u Konigsberg n i ti ng. M c dù Lý thuy t đ th đã ế ồ ị ổ ế ữ ề ầ ặ

đ c khoa h c phát tri n t r t lâu nh ng l ượ ể ừ ấ ư ọ ạ ạ i có nhi u ng d ng hi n đ i. ề ứ ụ ệ

t trong kho ng vài ch c năm tr Đ c bi ặ ệ ụ ả l ở ạ ờ ủ i đây, cùng v i s ra đ i c a ớ ự

máy tính đi n t và s phát tri n nhanh chóng c a Tin h c, Lý thuy t đ th ệ ử ế ồ ị ủ ự ể ọ

càng đ c quan tâm đ n nhi u h n. Đ c bi t là các thu t toán trên đ th ượ ế ề ặ ơ ệ ồ ị ậ

đã có nhi u ng d ng trong nhi u lĩnh v c khác nhau nh : M ng máy tính, ề ứ ự ư ụ ề ạ

Lý thuy t mã, T i u hoá, Kinh t h c v.v... ố ư ế ế ọ

M t trong các m c tiêu khi đ a tin h c vào nhà tr ng là nh m giúp cho ư ụ ộ ọ ườ ằ

ng hóa, khái quát hóa h c sinh có kh năng phân tích, t ng h p, tr u t ọ ừ ượ ả ổ ợ

t là phát tri n t duy. Hi n nay, có nhi u bài toán trong v n đ và đ c bi ấ ề ặ ệ ể ư ệ ề

ch c gi ươ ng trình trung h c ph thông đ ọ ổ ượ ả ế i quy t nh v n d ng lý thuy t ờ ậ ụ ế

ồ ị Đ tìm hi u sâu v lý thuy t đ th và ng d ng c a nó trong đ th . ế ồ ị ứ ụ ủ ể ề ể

ch ng trình tin h c ph thông nên em đã ch n đ tài “Graph và m t s ươ ộ ố ề ổ ọ ọ

ng d ng trong ch ứ ụ ươ ng trình trung h c ph thông”. ọ ổ

2. M c đích nghiên c u ụ ứ

Tìm hi u m t s v n đ v Graph nh các khái ni m c b n v Graph, ộ ố ấ ề ề ơ ả ư ể ệ ề

ậ phân lo i Graph… Đ hi u sâu s c h n lý thuy t Graph, cài đ t m t s thu t ắ ơ ể ể ộ ố ế ạ ặ

toán, t đó ng d ng lý thuy t Graph vào ch ừ ứ ụ ế ươ ng trình tin h c ph thông đ ọ ổ ể

gi i quy t m t s bài toán liên quan. ả ộ ố ế

• M t s v n đ v lý thuy t v Graph.

3. N i dung tìm hi u, nghiên c u ứ ộ ể

• M t s thu t toán c b n trên Graph.

ộ ố ấ ế ề ề ề

ộ ố ơ ả ậ

•

i quy t m t s bài toán c th trong Ứ ng d ng lý thuy t Graph vào gi ế ụ ả ụ ể ộ ố ế

ch ươ ng trình tin h c ph thông. ọ ổ

• Nghiên c u tài li u: Nghiên c u các tài li u v lý thuy t đ th và các

4. Ph ng pháp nghiên c u ươ ứ

ế ồ ị ứ ứ ệ ề ệ

• Ph

bài toán liên quan.

ng pháp th c nghi m: L p trình ki m th , tìm hi u thông tin ươ ử ự ệ ể ể ậ

• T ng k t kinh nghi m: T ng k t các ki n th c đã h c t p đ

trong m t s Website trên m ng. ộ ố ạ

c. ọ ậ ượ ứ ế ế ế ệ ổ ổ

ầ • Tham kh o ý ki n chuyên gia: Ti p thu ý ki n đóng góp c a các th y ế ủ ế ế ả

cô và ý ki n c a các b n bè. ế ủ ạ

C u trúc c a đ tài ủ ề ấ

M đ u: ng pháp, n i dung tìm hi u và ở ầ Nêu ra lý do ch n đ tài, ph ề ọ ươ ể ộ

m c đích nghiên c u, c u trúc đ tài. ứ ụ ề ấ

Ch ng 1: M t s v n đ v lý thuy t Graph. ươ ộ ố ấ ề ề ế

Ch ng 2: M t s thu t toán c b n trên Graph: ươ ộ ố ơ ả ậ Tìm hi u và cài ể

đ t các thu t toán c b n trên Graph c th nh : bi u di n Graph trên máy ặ ụ ể ơ ả ư ể ễ ậ

tính, phép duy t Graph, tìm đ ệ ườ ủ ng đi và ki m tra tính liên thông c a ể

Graph….Các thu t toán đ c cài đ t trên ngôn ng l p trình Pascal. ậ ượ ữ ậ ặ

Ch ng 3: ng trình Tin h c ph ươ ng d ng c a Graph vào ch Ứ ụ ủ ươ ọ ổ

thông: Đ a ra và v n d ng lý thuy t Graph vào cài đ t m t s bài toán c ế ộ ố ư ụ ậ ặ ụ

th trong ch ng trình tin h c ph thông theo t ng d ng: Bài toán duy t đ ể ươ ệ ồ ừ ạ ọ ổ

th , bài toán v đ ề ườ ị ng đi trên đ th , bài toán v cây khung đ th . ồ ị ồ ị ề

K t lu n: ậ Nêu ra nh ng v n đ đã tìm hi u, m t s công vi c chính đã ộ ố ế ữ ệ ề ể ấ

đ c th c hi n, h ng phát tri n ti p theo c a đ tài trong t ng lai. ượ ự ệ ướ ủ ề ể ế ươ

ả Em xin chân thành c m n Th y giáo, TS Nguy n M nh Đ c - Gi ng ả ơ ứ ễ ầ ạ

viên Tin h c, Khoa Toán, Đ i h c S ph m Thái Nguyên, ng ạ ọ ư ạ ọ ườ ự i đã tr c

ti p h ng d n và t n tình ch b o em trong su t quá trình làm đ tài. ế ướ ỉ ả ề ẫ ậ ố

Em xin chân thành c m ban ch nhi m Khoa Toán cùng các Th y, Cô ủ ệ ả ầ

trong khoa đã t o đi u ki n đ em th c hi n đ tài này. ự ệ ề ể ệ ề ạ

Tôi cũng xin c m n các b n sinh viên, ng i thân đã đ ng viên, giúp đ ả ơ ạ ườ ộ ỡ

trong th i gian th c hi n đ tài. ự ề ệ ờ

Thái Nguyên, tháng 4 năm 2013

Sinh viên

Vi Văn S nơ

Ch ng 1 ươ

M T S V N Đ V LÝ THUY T GRAPH Ộ Ố Ấ Ề Ề Ế

1.1. Khái ni m c b n v graph ơ ả ề ệ

1.1.1. Nh ng bài toán và v n đ d n đ n khái ni m graph [1] ề ẫ ế ữ ệ ấ

Hai ch “đ th ” v n th ng xuyên xu t hi n trong toán h c và c trong ữ ồ ị ẫ ườ ệ ấ ả ọ

h c toán, chúng ta có nói t đ i s ng hàng ngày. Trong các gi ờ ố ờ ọ ớ ồ ị ủ i đ th c a

h ng h n, trong hình d i có bi u di n đ th c a hàm s các hàm s . Cố ẳ ạ ướ ồ ị ủ ễ ể ố

y=sinx.

ả Trong các công s , các nhân viên ph i ở

ng tiêu l p các bi u đ theo dõi s l ồ ậ ố ượ ể

th đi n ho c xăng d u hàng tháng,và h ụ ệ ặ ầ ọ

Hình 1.1. Đ th hàm s y =sinx

ồ ị

ố

cũng có th g i nh ng bi u đ đó là đ ữ ể ọ ể ồ ồ

th ... Tóm l ị ạ i khái ni m đ th là m t khái ồ ị ệ ộ

ng quan ni m toán h c khá quen thu c đ i v i chúng ta nh m bi u di n t ộ ố ớ ễ ươ ể ệ ằ ọ

đi l i hai đ i t ng ho c nhi u đ i t ng toán h c khác nhau. ạ ố ượ ố ượ ề ặ ọ

Lý thuy t đ th (theo ti ng Anh và ti ng Đ c đ c là: “graph”) nghiên ế ồ ị ứ ế ế ọ

ả c u nh ng tính ch t toán h c, nh ng quan h mà không ph thu c vào b n ứ ụ ữ ữ ệ ấ ọ ộ

ồ ị ủ ch t riêng c a nh ng m i quan h này. Đ tránh kh i b nh m là đ th c a ỏ ị ủ ữ ệ ể ấ ầ ố

hàm s , ta s d ng thu t ng “graph” trong tài li u này ữ ử ụ ệ ậ ố ở ế các ph n ti p ầ

theo.

Graph là m t mô hình toán h c có th dùng đ gi i quy t khá nhi u bài ể ả ể ộ ọ ế ề

ộ ệ ố toán và v n đ toán h c. M t graph có th hi u đ n gi n là m t h th ng ể ể ề ấ ả ọ ộ ơ

các đ nh và các c nh n i v i nhau. G n v i mô hình lí thuy t graph là các ầ ố ớ ế ạ ớ ỉ

bài toán thoáng qua nh nh ng bài toán hình h c mà th c ch t vi c gi ữ ự ư ệ ấ ọ ả i

quy t chúng không th ch s d ng nh ng ki n th c hình h c thông ỉ ử ụ ữ ứ ể ế ế ọ

th ng. Trên m t ph ng, có nh ng bài toán d ườ ữ ặ ẳ ườ ọ ng nh là bài toán hình h c ư

nh th , nh ng chúng ta có th xem xét m t s ví d đ th y không ch có ụ ể ấ ư ế ộ ố ư ể ỉ

i quy t đ th dùng ki n th c hình h c đ gi ứ ể ả ế ể ọ ế ượ c chúng. Vi c mu n gi ệ ố ả i

quy t nh ng bài toán này c n đi sâu h n n a vào nh ng m i quan h toán ữ ữ ữ ệ ế ầ ơ ố

h c c a các đ i t ọ ủ ố ượ ố ng toán h c trong bài toán. M t s ví d có ngu n g c ộ ố ụ ồ ọ

phát sinh t các bài toán hình h c mà b n ch t th c s c a nó là các bài ừ ự ự ủ ấ ả ọ

toán v lí thuy t grap. ề ế

Ví d 1:ụ

Có ba cái nhà và ba cái gi ng. M i nhà có ba đ ng đi t nó t i ba cái ế ỗ ườ ừ ớ

ng đi nh v y sao cho không có gi ng đó. H i có th làm nh ng con đ ể ữ ế ỏ ườ ư ậ

hai con đ ng nào c t nhau hay không? ườ ắ

Đ gi i quy t bài toán này, chúng ta có th gi ể ả ể ả ử s là ế

1, A2, A3 trên m t ph ng và các ặ

các nhà là các đi m Aể ẳ

1, B2, B3 nào đó. Các con đ

ồ ị ể

gi ng là các đi m B ng đi là ể ế ườ

i v i các đ nh B

Hình 1.2. Đ th bi u di n ví d 1

ụ

ễ

các đ ườ ng (liên t c) n i các đ nh A ố ụ ỉ ớ ỉ

Khi đó, câu h i c a bài toán là li u có nh ng đi m A ỏ ủ ữ ể ệ

i trên m t ph ng sao cho không có hai con đ

i các đi m B t ớ ể ặ ẳ ườ ắ ng nào c t

nhau hay không? B ng cách thi t l p mô hình này, chúng ta đã thi ằ ế ậ ế ậ t l p

m t graph có 6 đ nh và 9 c nh. ạ ộ ỉ

Chúng ta th y r ng đ gi ấ ằ ể ả i bài toán này, các ki n th c hình h c không ế ứ ọ

còn giúp gì đ c cho chúng ta n a. Bài toán đòi h i ph i có ki n th c sâu ượ ữ ứ ế ả ỏ

s c h n v m i quan h nào đó c a quan h các đ nh và các c nh. [1] ủ ắ ơ ề ố ệ ệ ạ ỉ

ọ Nh ng không ph i ch v i m t s bài toán ho c m t s v n đ toán h c ộ ố ấ ộ ố ỉ ớ ư ề ả ặ

có ngu n g c hình h c m i có th đ a v mô hình đ nh – c nh nh trên. ể ư ư ề ạ ọ ớ ố ồ ỉ

Mô hình đ nh – c nh c a chúng ta t ạ ủ ỉ ỏ ắ ra là mô hình r t hi u qu đ n m b t ệ ả ể ắ ấ

đ c chính xác b n ch t toán h c th t s c a nhi u đ i t ượ ậ ự ủ ố ượ ề ả ấ ọ ọ ng toán h c.

c bi u di n cho các đ i l ng tham gia và các c nh n i chúng Các đ nh đ ỉ ượ ạ ượ ễ ể ạ ố

bi u di n m i quan h đi l ố ễ ệ ể ạ ủ i c a chúng theo m t tiêu chu n nào đó đ ộ ẩ ượ c

đ a ra. ư

Ví d 2:ụ

Hãy bi u th graph quan h không nguyên t ệ ể ị ố cùng nhau c a các s trong ủ ố

t p h p { 1, 2, 3, 4, 5, 6 }. ậ ợ

Bài toán này đ c gi ng pháp graph nh sau: Tr ượ ả i quy t b ng ph ế ằ ươ ư ướ c

h t ta ch n 6 đi m trên m t ph ng bi u di n cho 6 s 1, 2, 3, 4, 5 và 6. Các ể ế ễ ể ặ ẳ ọ ố

đi m này đ c tô đ m đ phân bi t v i giao đi m c a các c nh c a graph. ể ượ ể ậ ệ ớ ủ ủ ể ạ

Chúng ta n i hai đ nh c a graph b i m t đ ng n i ( ộ ườ ủ ố ở ỉ ố hình 1.3) n u hai s ế ố

cùng t ươ ng ng v i hai đ nh c a chúng không nguyên t ủ ứ ớ ỉ ố

nhau. Trong bi u di n graph nh v y, chúng ta có th ư ậ ể ễ ể

cùng nh n ra ngay r ng có 3 s đôi m t không nguyên t ố ằ ậ ộ ố

Hình 1.3. Đ th bi u ồ ị ể di n ví d 2

ụ

ễ

nhau.

ng ta xét r t có th còn là M i quan h gi a các đ i l ệ ữ ạ ượ ố ể ấ

ể các m i quan h trong đ i s ng. Ch ng h n, cũng graph trong hình 2 bi u ẳ ờ ố ệ ạ ố

th các m i quan h quen bi t c a 6 ng i, đ c đánh s t ệ ố ị ế ủ ườ ượ ố ừ ế 1 đ n 6, n u ế

cho bi t h quen nhau khi s th t t ng ng c a h không nguyên t ế ọ ố ứ ự ươ ứ ủ ọ ố

cùng nhau.

Trong các ví d trên, các đ nh c a graph đ c n i b i các c nh cũng có ủ ụ ỉ ượ ố ở ạ

th có h ng và ch n i các đ nh khác nhau v i nhau. Trong lý thuy t graph ể ướ ỉ ố ế ớ ỉ

các c nh cũng có th có h ng. ể ạ ướ

Ví d 3:ụ

ấ Có m t tr n đ u bóng bàn có m t s đ u th cùng tham gia. Hai đ u ộ ố ấ ủ ậ ấ ộ

th b t kì ph i đ u v i nhau đúng m t hi p. Đi m đ ả ấ ủ ấ ệ ể ớ ộ ượ c cho m i hi p là ỗ ệ

th ng 1 đi m, thua 0 đi m (không có hòa). H i có khi nào tr n đ u k t thúc ế ể ể ắ ậ ấ ỏ

t c các đ u th đ u b ng đi m nhau hay không? v i k t qu là t ớ ế ả ấ ả ủ ề ể ấ ằ

Ta bi u di n các đ u th t ủ ươ ứ ng ng thành các đ nh c a m t graph ỉ ủ ể ễ ấ ộ

Hai đ nh x và y c a graph đ c n i b i m t c nh có h ng đi t x t ủ ỉ ượ ố ở ộ ạ ướ ừ ớ i y

Hình 1.4. Đ th ồ ị bi u di n ví d 3 ụ ễ

ể

n u nh đ u th x th ng đ u th y. Bài toán đ ế ư ấ ủ ủ ắ ấ ượ c

đ t ra là có th có graph t ặ ể ươ ng ng v i n đ u th sao cho các đ nh có s ủ ứ ấ ớ ỉ ố

c nh xu t phát t ấ ạ ừ chúng b ng nhau. ằ

Trong hình 1.4 là m t graph th a mãn yêu c u c a bài toán v i n=5. ầ ủ ộ ớ ỏ

Trong nhi u tr ề ườ ng h p, chúng ta ch p nh n nh ng c nh n i m t đ nh ậ ộ ỉ ữ ạ ấ ợ ố

đã cho v i chính nó. Lo i này đ c g i là c nh khuyên trong graph. ạ ớ ượ ọ ạ

ạ Trong lý thuy t graph có cho phép gi a hai đ nh có th có nhi u c nh ữ ề ể ế ỉ

n i. Trong tr ố ườ ng h p có nhi u c nh (ít nh t là hai) n i 2 đ nh khác nhau ấ ề ạ ợ ố ỉ

nào đó c a m t graph, thì ta g i c nh đó là c nh kép. ọ ạ ủ ạ ộ

1.1.2. Đ nh nghĩa graph và các khái ni m c b n ơ ả ệ ị

Thông th ườ ầ ng chúng ta hay kí hi u m t graph b i ch G (ch cái đ u ữ ữ ệ ộ ở

t cu n sách đ u tiên c a t ủ ừ “Graph” trong ti ng Đ c, ngôn ng dùng đ vi ứ ể ế ữ ế ầ ố

ng đ c kí hi u b i ch V (là ch v lí thuy t graph). Còn t p đ nh th ề ế ậ ỉ ườ ượ ữ ệ ở ữ

cái đ u tiên c a t ủ ừ ầ ầ ủ “Vertices”) và t p c nh b i ch cái E (ch cái đ u c a ở ữ ữ ậ ạ

“Edges”). Graph không có c nh có h ng th ng đ c kí hi u là t ừ ạ ướ ườ ượ ệ

G=(V,E), còn graph có các c nh có h ng đ ạ ướ ượ ệ c kí hi u là G=[V,E]. Vi c ệ

dùng kí hi u này không b t bu c, mà ch là m t thói quen mà thôi. ệ ắ ộ ộ ỉ

Đ nh nghĩa đ th : ồ ị M t đ th G = (V, E) bao g m m t t p h u h n V ộ ồ ị ạ ồ ị

= {v1, v2,…vn} các đ nh (nút) và 1 t p h u h n E = {(v ộ ậ ữ i, vj), vi, vj ˛ ậ ỉ ạ

i, vj) khác cung (vj, vi) thì G là đ th có h

c p đ nh g i là cung (hay c nh). N u (v ặ ế ạ ọ ỉ ộ

ng, ng vi v i vớ j. N u cung (v ế V} các ữ i, vj) ˛ E thì ta nói có m t cung n i ố ượ c ồ ị ướ

l i là không h ng. ạ ướ

M t graph đ ộ ượ c g i là ph ng n u nó có th v đ ế ể ẽ ượ ẳ ọ ặ c trên m t m t ộ

ph ng mà không có c nh nào c t nhau ( ạ ẳ ắ ở ộ ể m t đi m không ph i là đi m ể ả

mút c a các c nh). Hình v nh th đ ư ế ượ ủ ẽ ạ ủ c g i là m t bi u di n ph ng c a ễ ể ẳ ọ ộ

ể

Hình 1.5. Bi u di n ễ ph ng c a Graph ủ

ẳ

graph.

Nh chúng ta đã th y trong các ví d trên, graph th ng đ ụ ư ấ ườ ượ ễ c bi u di n ể

trên m t ph ng: các đ nh đ ẳ ặ ỉ ượ ạ c tô đ m và các c nh n i các đ nh là các đo n ố ạ ậ ỉ

th ng ho c là các đ ặ ẳ ườ ng cong n i các đ nh này v i nhau. Ngoài ra, chúng ta ớ ố ỉ

ph i l u ý r ng m t graph có th có nhi u bi u di n trên m t ph ng khác ả ư ể ề ể ễ ằ ặ ẳ ộ

nhau. Trong hình 1.5 chúng ta có hai bi u di n trên m t ph ng khác nhau ể ễ ặ ẳ

c a m t graph. ộ ủ

Graph đ c phân lo i theo tính ch t c nh c a chúng. Trong m i graph ượ ấ ạ ủ ạ ỗ

các c nh c a graph th ng hay cong, dài hay ng n, các đ nh ủ ạ ẳ ắ ỉ ở ị ề v trí nào, đ u

không ph i là đi u quan tr ng. Mà đi u quan tr ng là graph có bao nhiêu ề ề ả ọ ọ

c n i v i đ nh nào. c nh và đ nh nào đ ỉ ạ ượ ố ớ ỉ

M t graph đ c g i là graph vô h ộ ượ ọ ngướ n u t ế ấ ả ề t c các c nh c a nó đ u ủ ạ

là c nh vô h ng. Graph đ graph có h ạ ướ ượ c g i là ọ ngướ n u t ế ấ ả ạ t c các c nh

ng. Đ nh xu t phát c a m t c nh có h ng đ c a nó đ u là c nh có h ủ ề ạ ướ ộ ạ ủ ấ ỉ ướ ượ c

c g i là đ nh cu i c a nó. g i là đ nh đ u, và đ nh k t thúc c a c nh đ ỉ ọ ủ ạ ế ầ ỉ ượ ố ủ ọ ỉ

Trong tr ng h p graph có c c nh vô h ng cũng nh c nh có h ng thì ườ ả ạ ợ ướ ư ạ ướ

graph đ c g i là c g i là ượ ọ graph h n h p. ỗ ợ M t graph đ ộ ượ ọ graph đ nơ n u nó ế

không có khuyên và không có c nh kép. Ngoài ra, ta g i graph đi m là graph ể ạ ọ

có đúng m t đ nh và không có c nh nào. Graph r ng dùng đ g i m t graph ể ọ ộ ỉ ạ ộ ỗ

không có đ nh và c nh nào c . ả ạ ỉ

1.1.3. Graph con và graph thành ph nầ

Cho tr ướ ạ c m t graph G v i t p đ nh X và t p c nh ớ ậ ậ ộ ỉ

M t graph G’ v i t p đ nh X’ và t p c nh E’ đ ỉ ớ ậ ộ ượ ọ c g i

(cid:204) là graph con c a graph G n u X’ E. Trong ậ ạ X và E’ (cid:204) ủ ế

ể

ễ

tr ườ ng h p X’ là t p con c a X v E’ là t p h p t ủ ợ ấ t ậ ả ậ ợ

Hình 1.6. Bi u di n Graph con và Graph thành ph nầ

c các c nh c a G n i hai đ nh c a X’, thì G’ đ ả ủ ủ ạ ố ỉ ượ c

g i là ọ graph thành ph nầ c a G và còn đ ủ ượ ở ậ c g i là graph sinh b i t p ọ

đ nh X’. ỉ

Graph trong hình 1.6 có các c nh đ c tô đ m là graph con c a graph ạ ượ ủ ậ

đ c bi u di n trong hình. N u thêm vào nó hai c nh a và b thì ta đ ượ ế ể ễ ạ ượ c

ọ m t graph thành ph n đã cho. Graph r ng là graph thành ph n c a m i ủ ầ ầ ộ ỗ

graph cho tr c.ướ

1.2. Phân lo i gra ph ạ

1.2.1. Graph vô h ngướ

1.2.1.1. B c c a đ nh ậ ủ ỉ

Trong ph n này chúng ta ch xét nh ng graph vô ữ ầ ỉ

h ng, t c là nh ng graph mà các c nh c a chúng ướ ủ ữ ứ ạ

không có h ướ ố ạ ng. Ta g i b c c a m t đ nh là s c nh ọ ậ ộ ỉ ủ

xu t phát t đ nh đó (các khuyên đ ấ ừ ỉ ượ c tính g p đôi). ấ

Hình 1.7. Bi u ể di n b c c a đ nh ậ ủ ỉ ễ

B c c a m t đ nh là m t s không âm. M t đ nh đ ộ ố ậ ủ ộ ỉ ộ ỉ ượ c

g i là ọ đ nh cô l p ỉ ậ n u nó không có c nh nào c , t c là ả ứ ế ạ

. khi đ nh có b c là 0. Đ nh có b c b ng 1 là ỉ ậ ằ ậ ỉ đ nh treo ỉ

Graph trong hình 1.7 có A là đ nh cô l p, D là đ nh treo. Đ nh B có b c là ậ ậ ỉ ỉ ỉ

3, đ nh C có b c là 2. ậ ỉ

L u ý r ng ằ : trong m t graph đ n vô h ư ộ ơ ướ ộ ng v i n đ nh thì b c c a m t ậ ủ ớ ỉ

đ nh b t kì luôn là m t s nguyên không âm không ỉ ộ ố ấ

v t n-1. ượ

1.2.1.2. Dãy c nh k ti p ế ế ạ

Cho tr ướ ậ ạ c m t graph G v i t p đ nh V và t p c nh ớ ậ ộ ỉ

E. Hai c nh c a m t graph cho tr ủ ạ ộ ướ ạ c g i là hai c nh ọ

Hình 1.8. Dãy c nh k ti p ế ế ạ

k nhau n u nh chúng có m t đ nh chung. M t dãy m ề ộ ỉ ư ế ộ

i = (Ai, Ai+1) v i i=1, 2,…,m đ ớ

c g i là m t dãy c nh e ạ ượ ọ ộ

1, e1, A2, e2 ,…, ek ,Ak+1)

ng đ c kí hi u là: H = (A c nh n i ti p và th ố ế ạ ườ ượ ệ

Trong tr ng h p G là m t graph đ n thì ta có th bi u di n m t dãy ườ ể ể ễ ợ ơ ộ ộ

c nh k ti p qua các đ nh c a chúng, ch ng h n dãy c nh k ti p c a H ạ ế ế ế ế ủ ủ ạ ẳ ạ ỉ

1, A2, A3,…,Ak+1)

trên đ c kí hi u đ n gi n là: H = (A c a ta ủ ở ượ ệ ả ơ

Theo đ nh nghĩa thì m t dãy các c nh liên ti p k nhau (m i c nh k ạ ỗ ạ ế ề ộ ị ề

v i c nh ti p theo) ch a h n đã là dãy c nh k ti p. M t dãy các c nh liên ớ ạ ư ẳ ế ế ế ạ ạ ộ

ộ ạ ti p k nhau là m t dãy các c nh k ti p ch khi đ nh chung c a m t c nh ế ế ủ ề ế ạ ộ ỉ ỉ

c nó và c nh đ ng sau nó b t kì (không ph i là ấ ả khuyên) v i c nh đ ng tr ớ ạ ứ ướ ứ ạ

ấ khác nhau. Trong m t dãy c nh k ti p, m t c nh c a graph có th xu t ế ế ộ ạ ủ ể ạ ộ

hi n nhi u l n. S m các c nh đ ề ầ ệ ạ ố ượ ọ ế ế c g i là là đ dài c a dãy c nh k ti p. ủ ạ ộ

1 đ

1, e1, A2, e2 ,…, ek ,Ak+1), đ nh Aỉ

Cho tr c dãy c nh k ti p H = (A ướ ế ế ạ ượ ọ c g i

k+1 đ

là đ nh đ u v đ nh A c g i là đ nh cu i c a H. H còn đ ả ỉ ầ ỉ ượ ố ủ ọ ỉ ượ c g i là ọ

k+1. Trong tr

1 ≠ Ak, dãy c nh k

1 v i Aớ

dãy c nh k ti p n i A ế ế ạ ố ườ ng h p A ợ ạ ế

1 = Ak thì H

ti p H đ c g i là dãy c nh k ti p không khép kín. Còn khi A ế ượ ế ế ạ ọ

đ c g i là dãy c nh k ti p khép kín [1]. ượ ọ ế ế ạ

1, e2,…, ek v i eớ i ≠ ej cho m i i ≠ j đ

M t dãy c nh k ti p e ạ ế ế ộ ọ ượ c g i là ọ

c g i là m t xích đ n. M t xích đ n v i đ nh đ u là A và đ nh cu i là B đ ớ ỉ ầ ơ ộ ộ ơ ố ỉ ượ ọ

m t xích đ n n i A v i B. ơ ớ ộ ố

1.2.1.3. Ch s liên thông ỉ ố

Khi bi u di n m t graph trên m t ph ng, chúng ta đã th y r ng có ặ ễ ể ấ ẳ ằ ộ

nhi u khi hình bi u di n c a chúng là nh ng c m tách r i nhau không ủ ụ ữ ể ễ ề ờ

đ c n i v i nhau. T ng ng v i m i hình r i nhau nh v y là m t graph ượ ố ớ ươ ứ ư ậ ộ ỗ ờ ớ

thành ph n c a graph đã cho mà ta s g i là m t ph n liên thông c a graph ẽ ọ ầ ủ ủ ầ ộ

cho tr c.ướ

Đ chính xác hóa khái ni m liên thông, tr c h t chúng ta nói hai đ nh ệ ể ướ ế ỉ

c là liên thông v i nhau n u có m t dãy c nh k c a m t graph cho tr ủ ộ ướ ế ạ ộ ớ ế

ti p n i chúng v i nhau trong graph đã cho. M t đ nh cho tr c luôn đ ộ ỉ ế ố ớ ướ ượ c

coi là liên thông v i chính nó (đ c n i v i chính nó b i m t dãy c nh k ớ ượ ố ớ ạ ở ộ ế

ti p có đ dài 0). M t graph đ ế ộ ộ ượ ủ c g i là liên thông n u hai đ nh b t kì c a ế ấ ọ ỉ

nó liên thông v i nhau. Quan h “liên thông” có nh ng tính ch t c b n sau ấ ơ ả ữ ệ ớ

[1]:

a) M i đ nh a c a graph liên thông v i chính nó. ỗ ỉ ủ ớ

b) N u a liên thông v i b thì b liên thông v i a. ế ớ ớ

c) N u a liên thông v i b và b liên thông v i c, thì a liên thông v i c. ế ớ ớ ớ

Th c ch t đây là m t quan h t ng đ ệ ươ ự ấ ộ ươ ủ ng trong t p h p các đ nh c a ợ ậ ỉ

graph. Quan h t ng đ ệ ươ ươ ng này chia t p đ nh c a graph thành các l p có ủ ậ ớ ỉ

hai tính ch t sau: ấ

1) Các đ nh thu c cùng m t l p thì liên thông v i nhau. ộ ớ ộ ớ ỉ

2) Các đ nh không cùng thu c m t l p không liên thông v i nhau. ộ ớ ộ ớ ỉ

Các l p đ nh này là đ nh c a graph thành ph n liên thông trong graph cho ủ ầ ớ ỉ ỉ

tr c, đ c g i là thành ph n liên thông c a graph đã cho. ướ ượ ọ ầ ủ

1.2.1.4. Đ ng đi trong graph ườ

Trong th c t ng d ng c a cu c s ng, ta th ự ế ứ ộ ố ủ ụ ườ ệ ng g p m t khái ni m ộ ặ

khác c a dãy c nh k ti p là nh ng dãy c nh k ti p đ ế ế ượ ế ế ữ ủ ạ ạ c tuân th nguyên ủ

i u là chúng không đi qua đ nh nào c a graph quá m t l n. M t dãy t c t ắ ố ư ộ ầ ủ ộ ỉ

c đ c g i là m t đ c nh k ti p trong m t graph cho tr ạ ế ế ộ ướ ượ ộ ườ ọ ế ng đi n u

chúng không đi qua đ nh nào c a graph quá 1 l n. Cũng t ng t ủ ầ ỉ ươ ự ư ớ nh v i

ủ dãy c nh k ti p, n u a và b là hai đ nh đ u tiên và đ nh cu i cùng c a ế ế ế ạ ầ ố ỉ ỉ

đ ng W, thì ta nói r ng W n i a v i b. Chúng đ ườ ằ ố ớ ượ c g i là đ nh đ u và ỉ ầ ọ

ng và đ đ nh cu i c a con đ ố ủ ỉ ườ ượ c xem là ph i khác nhau. ả

1, e1, p2, e2, p3, e3,…, ek-1, Pk)

Thông th ng, đ ng đi đ ườ ườ ượ ạ c bi u di n thông qua các đ nh và các c nh ể ễ ỉ

n i chúng, ch ng h n: W = (p ẳ ố ạ

i là các c nh c a W. Đ c bi ủ

t, khi graph cho tr c là v i pớ i là các đ nh và e ỉ ạ ặ ệ ướ

graph đ n, thì ta có th bi u di n m t đ ng đi thông qua t p đ nh c a nó, ể ể ộ ườ ễ ơ ủ ậ ỉ

1 , p2 , p3 ,…, Pk)

ch ng h n: W = (p ạ ẳ

S c nh c a m t đ ng đi đ ố ạ ộ ườ ủ ượ ọ c g i là đ dài c a nó. ộ ủ

1.2.1.5. Chu trình c a graph ủ

Khi đ nh nghĩa đ ng đi n i hai đ nh a và b c a m t graph, ta luôn gi ị ườ ủ ộ ố ỉ ả

thi t r ng các đ nh a và b này ph i khác nhau. Trong tr ng h p a và b ế ằ ả ỉ ườ ợ

đ c n i v i nhau b i m t c nh, thì khi thêm c nh (a, b) vào, ta thu đ ượ ố ớ ộ ạ ạ ở ượ c

con đ t ừ ườ ng đã cho m t chu trình. Nh v y chu trình là m t dãy c nh k ư ậ ạ ộ ộ ế

ti p khép kín sao cho m i đ nh c a graph đ c đi qua không quá m t l n. ỗ ỉ ủ ế ượ ộ ầ

Chu trình đ ượ ế c kí hi u b i vi c đ a ra các c nh và các đ nh liên ti p ư ệ ệ ạ ở ỉ

1, p2, …, pk

nhau trên chu trình. Ch ng h n, n u chu trình C đi qua các đ nh p ế ẳ ạ ỉ

1, e2, …, ek thì ta vi

1 , e1 , p2 , e2 , …, pk , ek , p1)

và các c nh e t: C = (p ạ ế

Trong tr ng h p graph là m t đ n graph, thì thay vì vi t rõ các c nh và ườ ộ ơ ợ ế ạ

các đ nh, chu trình đ c xác đ nh duy nh t qua vi c g i tên các đ nh nó đi ỉ ượ ệ ấ ọ ỉ ị

1 , p2 ,…, pk ,

trên có th vi t thành: C = (p qua. Ch ng h n chu trình C ạ ẳ ở ể ế

p1).

c g i là đ dài c a chu trình và thông th S c nh c a chu trình đ ủ ố ạ ượ ủ ộ ọ ườ ng

hay đ ượ c kí hi u b i ệ ở l(C). M t khuyên l p thành m t chu trình có đ dài 1. ậ ộ ộ ộ

M t graph cho tr c ch có chu trình có đ dài 2 n u nh nó có c nh kép. ộ ướ ư ế ạ ộ ỉ

Trong m t graph đ n m i chu trình có đ dài ít nh t là 3. ấ ộ ơ ỗ ộ

M t graph không đ n hi n nhiên luôn có ít nh t m t chu trình (có đ dài ể ấ ộ ơ ộ ộ

ộ 1 ho c 2). Trong graph đ n không ph i lúc nào ta cũng có th tìm th y m t ả ể ặ ấ ơ

chu trình. Ch ng h n các graph bi u di n s đ c p đi n, ho c các s đ ễ ơ ồ ấ ơ ồ ể ệ ẳ ạ ặ

c ch ng h n. c p n ấ ướ ẳ ạ

1.2.2. Graph có h ngướ

1.2.2.1. Khái ni m c s c a graph có h ng ơ ở ủ ệ ướ

M t graph đ ộ ượ c g i là ọ graph (h u h n) có ữ ạ

h ng mà ta còn ngướ khi nó ch có các c nh có h ỉ ạ ướ

g i là các cung. ọ

ễ ạ h

Hình 1.9. Bi u ể di n c nh có ngướ

M t cung u đ c xác đ nh nh đi m đ u ộ ượ ờ ể ầ x và ị

đi m cu i ng kí hi u ố y, mà ta th ể ườ ệ u = [x, y], trong

đó x đ và y đ ượ c g i là ọ đ nh xu t phát ấ ỉ ượ c g i là ọ đ nh đích ỉ c a ủ u. Chúng ta

u liên h p v i đ nh x và đ nh y. cũng nói r ng ằ ớ ỉ ợ ỉ

Graph có h ng G v i t p đ nh X và t p c nh E th ng đ ướ ớ ậ ậ ạ ỉ ườ ượ ệ c kí hi u

ng cũng đ b i G = [X, E]. M t graph có h ở ộ ướ ượ ẳ c bi u di n trên m t ph ng ễ ể ặ

c bi u di n thành các đi m tô đ m, các b i m t hình, trong đó các đ nh đ ở ộ ỉ ượ ễ ể ể ậ

ng và các cung là các đ c b sung b i mũi c nh có h ạ ướ ườ ng liên t c và đ ụ ượ ở ổ

tên th hi n chi u đi t i đ nh đích. Các cung có cùng đ nh ể ệ ề ừ ỉ đ nh xu t phát t ấ ớ ỉ ỉ

xu t phát và đ nh đích đ các cung song song. N u đ nh xu t phát ấ ỉ ượ c g i là ọ ế ấ ỉ

và đ nh đích có cùng m t cung u trùng nhau thì cung u này đ ộ ỉ ượ c g i là ọ

khuyên có h ngướ . M t graph không có cung song song và khuyên có h ộ ướ ng

nào c đ graph có h ng đ n ả ượ c g i là ọ ướ ơ . Ta nói r ng cung ằ u liên h pợ v iớ

x, n u nh đ nh ỉ ư x là đ nh xu t phát ho c là đ nh đích c a cung ặ ủ ế ấ ỉ ỉ u. N u cung ế

u liên h p v i đ nh x, thì cung u đ c g i là liên h p h ng ra ngoài (liên ớ ỉ ợ ượ ợ ọ ướ

ng vào trong) đ i v i đ nh x là đ nh xu t phát (đ nh đích) c a cung h p h ợ ướ ố ớ ỉ ủ ấ ỉ ỉ

1.3. K t lu n ch ng 1 ế ậ ươ

Trong ch ươ ề ề ng này chúng ta đã tìm hi u t ng quan m t s v n đ v lý ộ ố ấ ể ổ

ư thuy t đ th : Đ a ra m t s bài và v n đ d n đ n khái ni m Graph, đ a ấ ế ồ ị ộ ố ề ẫ ư ệ ế

ra khái ni m c b n v Graph, Phân lo i Graph, Lý thuy t v Graph vô ế ề ơ ả ề ệ ạ

h ng, Graph có h ng… Trong đó có các khái ni m v b c c a đ nh, ch ướ ướ ề ậ ủ ỉ ệ ỉ

ng đi và chu trình trong Graph… s liên thông, khái ni m v đ ố ề ườ ệ

Ch ng 2 ươ

M T S THU T TOÁN C B N TRÊN GRAPH Ộ Ố Ơ Ả Ậ

2.1. Bi u di n graph trên máy tính ễ ể

Đ gi ể ả ả i quy t các bài toán v graph b ng máy tính, chúng ta c n ph i ằ ề ế ầ

graph trong b nh . Có nhi u bi u di n c u trúc đ c s d ng đ l u gi ư ữ ễ ấ ề ể ộ ớ ượ ử ụ ể

ụ bi u di n graph. Vi c l a ch n c u trúc nào là tùy thu c vào các ng d ng ệ ự ứ ễ ể ấ ộ ọ

và các phép x lý c n tác đ ng lên graph trong ng d ng y. Có hai cách ụ ứ ử ầ ấ ộ

bi u di n graph th ễ ể ườ ng dùng: Dùng ma tr n k và dùng danh sách k . ề ề ậ

2.1.1. Bi u di n b ng ma tr n lân c n ằ ậ [6] ễ ể ậ

Gi s G=(V, E) là m t graph đ n có s đ nh (Ký hi u |V|) là n, không ả ử ố ỉ ệ ộ ơ

m t tính t ng quát có th coi các đ nh đ c đánh s t 1, 2,…, n. Khi đó ta ể ấ ổ ỉ ượ ố ừ

ij] c p n. Trong đó:

có th bi u di n đ th b ng m t ma tr n vuông A = [a ồ ị ằ ể ể ễ ậ ộ ấ

•

˛ E aij = 1 n u (i, j) ế

•

• Quy

ˇ E aij = 0 n u (i, j) ế

c a i; ướ ij = 0 v i ớ "

Đ i v i đa đ th thì vi c bi u di n cũng t ng t ố ớ ồ ị ể ễ ệ ươ ự ế trên, ch có đi u n u ề ỉ

nh (i, j) là c nh thì không ph i ta ghi s 1 vào ư ạ ả ố v trí a ị ố ạ ij mà là ghi s c nh

n i đ nh i v i j. ố ỉ ớ

Hình 2.1. Ma tr n k đ th vô h

ướ

ng không

ướ

ọ

ậ ề ồ ị không tr ng s và đ th có h ồ ị ố tr ng s . ố

ọ

Ví d :ụ

1. Đ i v i graph vô h

Các tính ch t c a ma tr n lân c n ấ ủ ậ [6]: ậ

ij = aji), đi u này không đúng v i đ th có h

ng G, thì ma tr n lân c n t ố ớ ướ ậ ươ ậ ậ ng ng là ma tr n ứ

ng. đ i x ng (a ố ứ ớ ồ ị ề ướ

2. N u G là graph vô h ng và A là ma tr n lân c n t ng ng thì trên ế ướ ậ ươ ậ ứ

ma tr n A: ậ

T ng các s trên hàng i = t ng các s trên c t i dG(i) ộ = B c c a đ nh i = ậ ủ ỉ ố ổ ố ổ

Trong tr ng h p G là graph đ n, ta có th bi u di n ma tr n lân c n A ườ ể ể ễ ậ ậ ợ ơ

ij = 1 n u (i, j) ế

˛ ˇ ng ng là các ph n t logic. a E và aij = 0 n u (i, j) E. t ươ ứ ầ ử ế

Trong r t nhi u v n đ ng d ng c a lý thuy t graph, m i c nh e =(i, j) ủ ỗ ạ ề ứ ụ ế ề ấ ấ

c gán v i m t con s c(e) (còn vi c a graph đ ủ ượ ớ ố ộ ế t là c(i, j)) g i là tr ng s ọ ọ ố

tr c a c nh e. Graph trong ủ ạ ườ ng h p đó đ ợ ượ ố c g i là graph có tr ng s . Đ i ố ọ ọ

ử ụ v i graph có tr ng s , thay vì ma tr n k , đ bi u di n graph ta s d ng ậ ớ ề ể ể ễ ố ọ

ma tr n tr ng s : Thay c[i, j] là tr ng s c(i ,j) c a cung (i, j) n u có cung. ủ ế ậ ố ọ ố ọ

N u không có cung (i, j) thì ng i ta đ t a t nào ế ườ ặ ij b ng m t giá tr đ c bi ộ ị ặ ằ ệ

+∞, ho c -∞ tùy t ng tr

đó, có th là 0, ể ừ ặ ườ ng h p c th . ợ ụ ể

ậ ủ ậ

ự ễ ả ặ ơ

* u đi m c a ma tr n lân c n: Ư ể • Đ n gi n, tr c quan, d cài đ t trên máy tính. • Đ ki m tra xem hai đ nh (u, v) c a đ th có k nhau hay không, ta ủ ồ ị ể ể ề ỉ

ij ≠ 0.

ch vi c ki m tra b ng m t phép so sánh a ỉ ệ ể ằ ộ

• B t k s c nh c a graph là nhi u hay ít, ma tr n lân c n luôn đòi ề

*Nh c đi m c a ma tr n lân c n: ượ ủ ể ậ ậ

ấ ể ố ạ ủ ậ ậ

c a ma tr n, đi u đó gây lãng phí b nh hỏi n2 ô nh đ l u các ph n t ớ ể ư ầ ử ủ ề ậ ộ ớ

i vi c không th bi u di n đ c đ th v i s l ng đ nh l n. d n t ẫ ớ ể ể ễ ượ ồ ị ớ ố ượ ệ ớ ỉ

V i m t đ nh u b t kỳ c a đ th , nhi u khi ta ph i xem xét t t c các ủ ồ ị ộ ỉ ề ấ ả ớ ấ ả

t c các c nh liên thu c v i nó. Trên ma đ nh v khác k v i nó, ho c xét t ề ớ ỉ ặ ấ ả ạ ộ ớ

t c các đ nh v và tr n lân c n vi c đó đ ậ ệ ậ ượ c th c hi n b ng cách xét t ằ ự ệ ấ ả ỉ

ki m tra đi u ki n a ể ệ ề ậ uv ≠ 0. Nh v y ngay c khi đ nh u là đ nh cô l p ư ậ ả ỉ ỉ

ộ (không k v i đ nh nào) ho c đ nh treo (ch k v i 1 đ nh) ta cũng bu c ề ớ ỉ ỉ ề ớ ặ ỉ ỉ

ph i xét t t c các đ nh và ki m tra đi u ki n trên d n t ả ấ ả ẫ ớ ể ề ệ ỉ ờ i lãng phí th i

gian.

Ch ng trình ươ sau bi u di n graph vô h ễ ể ướ ng b ng ma tr n k trên ngôn ậ ề ằ

• Input: Nh p t

ng Pascal: ữ

ậ ừ ậ bàn phím s đ nh, s c nh, v i m i c nh (i, j) ta nh p ỗ ạ ố ạ ố ỉ ớ

đ nh đ u i và đ nh cu i j. ỉ ầ ố ỉ

ij =

• Output: Ma tr n lân c n A v i a ậ

i thì a ớ ij = 1 n u i k v i j, ng ề ớ ế ậ c l ượ ạ

uses crt;

const fo='MATRANKE.INP';

var f:text;

a:array[1..100,1..100] of byte;

i,j,n,m:integer;

procedure init;

var x,y:integer;

begin

writeln('Nhap so dinh va so canh cua do thi: ');

readln(n,m);

for i:= 1 to m do

begin

writeln(' Nhap dinh dau va dinh cuoi canh ',i,' : ');

readln(x,y);

a[x,y]:=1;

a[y,x]:=1;

end;

procedure process;

begin

assign(f,fo); rewrite(f);

for i:=1 to n do

begin

for j:=1 to n do

write(f,a[i,j],' ');

Ch ng trình ươ

writeln(f);

end;

close(f);

end;

begin

clrscr;

init;

process;

readln

end.

[6] 2.1.2. Bi u di n b ng danh sách c nh ằ ể ễ ạ

Trong tr ng h p graph có n đ nh, m c nh, ta có th bi u di n graph d ườ ể ể ễ ạ ợ ỉ ướ i

i ta li t kê t t c các d ng danh sách c nh, trong cách bi u di n này, ng ạ ể ễ ạ ườ ệ ấ ả

c nh c a graph trong m t danh sách, m i ph n t ộ ạ ầ ử ủ ộ ặ c a danh sách là m t c p ủ ỗ

(u, v) t ng ng v i m t c nh c a graph. (Trong tr ng h p graph có h ươ ứ ộ ạ ủ ớ ườ ợ ướ ng

thì m i c p (u, v) t ỗ ặ ươ ứ ố ủ ng ng v i m t cung, u là đ nh đ u và v là đ nh cu i c a ỉ ầ ớ ộ ỉ

cung). Danh sách đ c l u trong b nh d i d ng m ng ho c danh sách ượ ư ớ ướ ạ ả ặ ộ

ễ

ể

ạ

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.

ả

ố

móc n i.ố

u đi m: Ư ể

• Trong tr

ườ ng h p graph th a (có s c nh t ư ố ạ ợ ươ ạ ng đ i nh : ch ng h n ẳ ỏ ố

c không gian m < 6n), cách bi u di n b ng danh sách c nh s ti ằ ẽ ế ễ ể ạ t ki m đ ệ ượ

• Trong m t s tr

l u tr , b i nó ch c n 2m ô nh đ l u danh sách c nh. ư ớ ể ư ữ ở ỉ ầ ạ

ng h p, ta ph i xét t t c các c nh c a graph thì ộ ố ườ ả ợ ấ ả ủ ạ

ơ cài đ t trên danh sách c nh làm cho vi c duy t các c nh d dàng h n. ệ ệ ễ ặ ạ ạ

(Thu t toán Kruskal ch ng h n). ậ ẳ ạ

• Nh

Nh ượ c đi m: ể

c đi m c b n c a danh sách c nh là khi ta c n duy t t t c ượ ơ ả ệ ấ ả ủ ể ầ ạ

ả các đ nh k v i đ nh v nào đó c a graph, thì ch ng có cách nào khác là ph i ề ớ ỉ ủ ẳ ỉ

duy t t t c các c nh, l c ra nh ng c nh có ch a đ nh v và xét đ nh còn l ệ ấ ả ứ ỉ ữ ạ ạ ọ ỉ ạ . i

Đi u đó khá t n th i gian trong tr ng h p graph dày (nhi u c nh). ề ố ờ ườ ề ạ ợ

Ch ng trình sau bi u di n graph vô h ng ươ ễ ể ướ ố b ng danh sách móc n i ằ

•

trên ngôn ng Pascal: ữ

Input: Nh p t bàn phím s đ nh, s c nh, v i m i c nh (i, j) ta ậ ừ ỗ ạ ố ạ ố ỉ ớ

• Output: Danh sách các c nh c a graph.

nh p đ nh đ u i và đ nh cu i j. ầ ậ ố ỉ ỉ

ủ ạ

uses crt;

type ds=^node;

node =record

dau,cuoi:integer;

next:ds;

end;

var canh,list:ds;

i,m:integer;

procedure init;

var x,y:integer;

begin

list:=nil;

write('Nhap so canh cua do thi: ');

readln(m);

for i:=1 to m do

Ch ng trình: ươ

begin

write('Nhap thong tin dinh dau va dinh cuoi canh ',i);

readln(x,y);

new(canh);

canh^.dau:=x;

canh^.cuoi:=y;

canh^.next:=list;

list:=canh;

end;

procedure xuatds;

var k:byte;

begin

k:=1;

while (list<>nil) do

begin

writeln('Dinh dau va dinh cuoi canh ',k,' :

',list^.dau,' ',list^.cuoi);

list:=list^.next;

end;

begin

clrscr;

init;

xuatds;

readln

end.

2.1.3. Bi u di n danh sách lân c n ậ [6] ể ễ

Đ kh c ph c nh c đi m c a ph ng pháp ma tr n lân c n ụ ể ắ ượ ủ ể ươ ậ (k ) vàề ậ

danh sách c nh, ng i ta đ xu t ph ng pháp bi u di n graph b ng danh ạ ườ ề ấ ươ ể ễ ằ

sách k . Trong cách bi u di n này, v i m i đ nh v c a graph, ta cho t ỗ ỉ ủ ể ễ ề ớ ươ ng

ng v i nó m t danh sách các đ nh k v i v. ứ ề ớ ớ ộ ỉ

V i graph G = (V, E). V g m n đ nh và E g m m c nh. Có hai cách cài ớ ạ ồ ồ ỉ

Hình 2.3. Đ th vô ướ

ng không tr ng s . ố

ồ ị ọ

đ t danh sách k ph bi n: ặ ổ ế ề

Cách 1: (Forward Star) Dùng m t m ng các đ nh, m ng đó chia làm n ả ả ộ ỉ

đo n, đo n th i trong m ng l u danh sách các đ nh k v i đ nh i: Ví d ề ớ ỉ ư ứ ạ ả ạ ỉ ụ

[6]: v i đ th trên, danh sách k s là m t m ng A g m 12 ph n t ớ ồ ị ề ẽ ầ ử ả ộ ồ

1 2 2 3 3 5 4 1 6 1 5 3 7 2 8 4 9 3 10 5 11 1 12 4

1 2 3 4 5

Đ bi ể ế t m t đo n n m t ạ ằ ộ ừ ả ch s nào đ n ch s nào, ta có m t m ng ỉ ố ỉ ố ế ộ

ẽ ằ l u v trí riêng. Ta g i m ng l u v trí đó là m ng Head. Head[i] s b ng ư ư ả ả ọ ị ị

ch s đ ng li n tr ỉ ố ứ ề ướ c đo n th i. Quy ứ ạ ướ ớ c Head[n + 1] s b ng m. V i ẽ ằ

graph trên thì m ng Head[1..6] s là: (0, 3, 5, 8, 10, 12). Nh v y đo n t v ư ậ ạ ừ ị ẽ ả

trí Head[i]+1 đ n Head[i+1] trong m ng A s ch a các đ nh k v i đ nh i. ả ề ớ ỉ ẽ ứ ế ỉ

L u ý r ng v i graph có h ớ ư ằ ướ ầ ng g m m cung thì c u trúc Forward Star c n ấ ồ

ph i đ ch a m ph n t , v i graph vô h ả ủ ứ ầ ử ớ ướ ng m c nh thì c u trúc Forward ấ ạ

Star c n ph i đ ch a 2m ph n t ả ủ ứ . ầ ử ầ

Ch ng trình sau bi u di n graph vô h ng ươ ể ễ ướ b ng danh sách k trên ằ ề

• Input: Nh p t

ngôn ng Pascal: ữ

bàn phím s đ nh, s c nh, v i m i c nh (i, j) nh p đ nh ậ ừ ỗ ạ ố ạ ố ỉ ậ ớ ỉ

• Output: V i m i đ nh i, in ra danh sách các đ nh k v i i, v i danh sách

đ u i và đ nh cu i j. ỉ ầ ố

ề ớ ỗ ỉ ớ ớ ỉ

c l u tr theo cách 1. các đ nh đ ỉ ượ ư ữ

uses crt;

var i,j:byte;

n,m,k:integer;

head,dau,cuoi:array[1..100] of byte;

a:array[1..200] of integer;

procedure init;

begin

write('Nhap so dinh va so canh cua do thi: ');

readln(n,m);

for i:=1 to m do

begin

write('Nhap thong dinh dau va dinh cuoi cua canh

',i,' : ');

readln(dau[i],cuoi[i]); end; end; procedure process; begin k:=1; for i:=1 to n do begin for j:=1 to m do begin if (i=dau[j]) then begin a[k]:=cuoi[j]; k:=k+1; end; if (i=cuoi[j]) then begin a[k]:=dau[j]; k:=k+1; end; end; head[i]:=k-1; end;

Ch ng trình: ươ

for i:=n+1 downto 2 do head[i]:=head[i-1]; head[1]:=0; end; procedure xuatdanhsach; begin for i:=1 to n do begin write('Danh sach cac dinh ke voi dinh ',i,' : '); for j:= head[i]+1 to head[i+1] do write(a[j],' '); writeln; end; end; begin clrscr; init; process; xuatdanhsach; readln end.

Cách 2: Dùng các danh sách móc n i: V i m i đ nh i c a graph, ta cho ố ỗ ỉ ủ ớ

ng ng v i nó m t danh sách móc n i các đ nh k v i i, có nghĩa là t ươ ề ớ ứ ộ ớ ố ỉ

ng ng v i m t đ nh i, ta ph i l u l i list[i] là ch t c a m t danh sách t ươ ả ư ạ ộ ỉ ứ ớ ố ủ ộ

Hình 2.4. Bi u di n graph b ng danh sách k

ể

ễ

ằ

ề

ố ẽ ụ ớ ố móc n i. Ví d v i graph trên, danh sách móc n i s là [6]:

Ch ng trình sau bi u di n graph vô h ng b ng danh sách k trên ươ ể ễ ướ ề ằ

ngôn ng Pascal: ữ

• Input: Nh p t

bàn phím s đ nh, s c nh, v i m i c nh (i, j) nh p đ nh ậ ừ ỗ ạ ố ạ ố ỉ ậ ớ ỉ

• Output: V i m i đ nh i, in ra danh sách các đ nh k v i i, v i danh sách

đ u i và đ nh cu i j. ỉ ầ ố

ề ớ ỗ ỉ ớ ớ ỉ

c l u tr theo cách 2. các đ nh đ ỉ ượ ư ữ

uses crt;

Const maxV=100;

Type link=^node;

node=record

v:integer;

next:link;

End;

Var j,x,y,m,n,u,v:integer;

t:link;

list:array[1..maxV] of link;

Begin

clrscr;

Write('Nhap so canh va dinh cua do thi:'); readln(m,n);

{thoi tao}

for j:=1 to n do list[j]:=nil;

for j:=1 to m do

begin

write('Nhap dinh dau va cuoi cua canh ',j,' : ');

readln(x,y);

new(t); t^.v:=x; t^.next:=list[y]; list[y]:=t;

new(t); t^.v:=y; t^.next:=list[x]; list[x]:=t;

end;

writeln('Danh sach ke cua cac dinh cua do thi:');

for j:=1 to n do

begin

write('Danh sach cac dinh ke cua dinh ',j,' : ');

t:=list[j];

while t<>nil do

begin

write(t^.v:4);

Ch ng trình: ươ

t:=t^.next;

end;

writeln;

end;

readln

End.

u đi m: Ư ể Đ i v i danh sách k , vi c duy t t ố ớ ệ ấ ả ộ t c các đ nh k v i m t ề ớ ề ệ ỉ

c là h t s c d dàng, cái tên “Danh sách k ” đã cho th y rõ đ nh v cho tr ỉ ướ ế ứ ễ ề ấ

đi u này. Vi c duy t t ệ ấ ả t c các c nh cũng đ n gi n vì m t c nh th c ra là ả ộ ạ ự ệ ề ạ ơ

n i m t đ nh v i m t đ nh khác k nó. ố ộ ỉ ộ ỉ ề ớ

Nh c đi m: ng pháp bi u di n trên, danh ượ ể V lý thuy t, so v i hai ph ế ề ớ ươ ễ ể

sách k t t h n h n. Ch có đi u, trong tr ng h p c th mà ma tr n lân ề ố ơ ề ẳ ỉ ườ ợ ụ ể ậ

không th hi n nh c đi m c n hay danh sách c nh ậ ạ ể ệ ượ ể thì ta nên dùng ma tr nậ

lân c n (hay danh sách c nh) b i cài đ t danh sách k có ph n dài dòng ề ậ ặ ạ ầ ở

h n.ơ

2.2. Phép duy t m t graph ệ ộ

Khi bi t g c c a m t cây ta có th th c hi n phép duy t cây đó đ thăm ế ố ủ ể ự ệ ể ệ ộ

các nút c a cây theo th t nào đ y. ứ ự ủ ấ

V i đ th v n đ đ t ra cũng t ng t . Xét m t graph vô h ng G =(V, ớ ồ ị ấ ề ặ ươ ự ộ ướ

E) và m t đ nh v trong V(G), ta c n thăm ộ ỉ ầ

t t c các đ nh thu c G mà có th “v i t ấ ả ể ớ ớ i” ộ ỉ

đ đ nh v (nghĩa là thăm m i nút liên c t ượ ừ ỉ ọ

thông v i v). ớ

Ta chú ý t i hai cách gi ớ ả i quy t trên ế

đây:

theo chi u sâu Phép tìm ki m ế ề

Hình 2.5. Đ th vô h

ồ ị

ướ

(Depth first search)

Phép tìm ki m ế ộ theo chi u r ng ề

(Breadth first search)

2.2.1. Tìm ki m theo chi u sâu ế ề

Tìm ki m theo chi u r ng đ i v i m t graph vô h ng đ ề ộ ố ớ ế ộ ướ ượ ệ c th c hi n ự

nh sau: ư

c thăm. Ti p theo đó m t đ nh ω ch a đ c thăm, Đ nh xu t phát v đ ấ ỉ ượ ộ ỉ ư ượ ế

mà là lân c n c a v, s đ c ch n và m t phép tìm ki m theo chi u sâu ẽ ượ ủ ậ ế ề ọ ộ

xu t phát t ω l c th c hi n. ấ ừ i đ ạ ượ ự ệ

Khi m t đ nh u đã đ c “v i t i” mà m i đ nh lân c n c a nó đ u đã đ ộ ỉ ượ ớ ớ ậ ủ ọ ỉ ề ượ c

thăm r i, thì ta s quay ng c thăm (mà còn ẽ ồ c l ượ ạ i lên đ nh cu i cùng v a đ ố ừ ượ ỉ

có đ nh ω lân c n v i nó mà ch a đ c thăm), và m t phép tìm ki m theo ư ượ ậ ớ ỉ ế ộ

chi u sâu xu t phát t ω l c th c hi n. Phép tìm ki m s k t thúc khi ề ấ ừ i đ ạ ượ ẽ ế ự ệ ế

không còn m t nút nào ch a đ c t nút đã ư ượ ộ c thăm mà v n có th v i t ẫ i đ ể ớ ớ ượ ừ

thăm.

N u đ th G có d ng nh hình 2.5 và đ nh xu t phát là 1 thì dãy các ồ ị ư ế ạ ấ ỉ

c thăm nh sau: đ nh s đ ỉ ẽ ượ ư

Tho t đ u là đ nh 1, r i t i đ nh 2( t i các đ nh ạ ầ ồ ớ ỉ ỉ ấ t nhiên có th là 3) r i t ể ồ ớ ỉ

4, 8, 5. Do đ nh 5 ch a có lân c n nào ch a đ c thăm nên quay l i đ nh 8 ư ượ ư ậ ỉ ạ ỉ

đ thăm ti p các đ nh 6, 3, 7. ể ế ỉ

Gi i thu t c a phép duy t này [3]: ả ậ ủ ệ

Procedure DFS(v)

{Cho m t đ th vô h ng G=(V, E) v i n đ nh và m t vect Visited(n) ộ ồ ị ướ ớ ộ ỉ ơ

, tho t đ u có giá tr b ng 0. Gi g m n ph n t ồ ầ ử ạ ầ ị ằ ả i thu t này đ ậ ượ ệ c th c hi n ự

vi c thăm m i đ nh “v i t i” đ đ nh v. Đ i v i th t c này G và ọ ỉ ớ ớ ệ c t ượ ừ ỉ ố ớ ủ ụ

1) Visited(v) := 1;{ đây Visited dùng đ đánh d u các đ nh đã đ

Visited không ph i là c c b } ụ ộ ả

2) for m i đ nh ω lân c n c a v

c thăm} ể ấ ở ỉ ượ

do ậ ủ ỗ ỉ

if Visited(ω) = 0 then call DFS(ω);

3) return

*Ta th y:ấ

Trong tr ườ ng h p G đ ợ ượ c bi u di n b i m t danh sách lân c n ộ ậ (k ) thì ề ễ ể ở

c xác đ nh b ng cách d a vào danh sách móc đ nh ω lân c n c a v s đ ậ ỉ ẽ ượ ủ ự ằ ị

i thu t DFS ch xem xét m i nút trong danh sách n i ng v i v. Vì v y gi ố ứ ậ ớ ả ậ ỗ ỉ

lân c n nhi u nh t m t l n thôi mà l ộ ầ ề ấ ậ ạ ớ i có 2e nút danh sách ( ng v i e ứ

cung), nên th i gian đ hoàn thành phép tìm ki m ch là O(e). ế ể ờ ỉ

c bi u di n b i ma tr n lân c n thì th i gian đ xác đ nh Còn n u G đ ế ượ ể ễ ể ậ ậ ở ờ ị

i đa có n đ nh đ c thăm, nên th i gian m i đ nh lân c n c a v là O(n). Vì t ậ ủ ọ ỉ ố ỉ ượ ờ

2).

tìm ki m t ng quát s là O(n ế ẽ ổ

1) s đ m b o thăm m i đ nh liên thông v i v

Gi i thu t DFS(v ả ậ ẽ ả ọ ỉ ớ 1. T t cấ ả ả

c thăm cùng v i các cung liên quan t các đ nh đ ỉ ượ ớ ớ ộ i các đ nh đó g i là m t ọ ỉ

c a G (connected component of G). V i phép duy t DFS b ph n liên thông ộ ậ ủ ệ ớ

ta có th xác đ nh đ c G có liên thông hay không, ho c tìm đ c các b ể ị ượ ặ ượ ộ

ph n liên thông c a G n u G không liên thông. ế ủ ậ

procedure DFS(v:integer);

var j:integer;

begin

write(v,' ');

visited[v]:=1;

for j:=1 to n do

if (visited[j]=0) and (a[v,j]=1) then DFS(j);

end;

Sau đây là th t c DFS theo đ quy cài đ t trên ngôn ng Pascal: ủ ụ ữ ệ ặ

2.2.2. Tìm ki m theo chi u r ng ề ộ ế

đây cũng đ Đ nh xu t phát v ấ ỉ ở ượ ớ c thăm đ u tiên, nh ng có s khác v i ư ự ầ

DFS ch là: sau đó các đ nh ch a đ c thăm mà là lân c n c a v s đ ở ỗ ư ượ ỉ ậ ủ ẽ ượ c

thăm k ti p nhau, r i m i đ n thăm các đ nh ch a đ ớ ế ế ế ư ồ ỉ ượ ậ c thăm là lân c n

t c a các đ nh này và c t ng t nh v y. l n l ầ ượ ủ ứ ươ ỉ ự ư ậ

Ví d v i đ th hình 2.5 thì đ nh 1 đ ụ ớ ồ ị ỉ ượ ế c thăm r i đ n đ nh 2, 3…ti p ồ ế ỉ

theo là đ nh 4, 5 và 6, 7 cu i cùng là đ nh 8. ố ỉ ỉ

Gi i thu t c a phép duy t này [3]: ả ậ ủ ệ

Procedure BFS(v)

{Phép tìm ki m theo chi u r ng đ i v i G đ c th c hi n b t đ u t ề ộ ố ơ ế ượ ắ ầ ừ ự ệ

c thăm s đ đ nh v. M i đ nh i đ ỉ ọ ỉ ượ ẽ ượ ạ c đánh d u v i VISITED(i) := 1. Tho t ấ ớ

đ u VISITED(i) có giá tr đ u b ng 0. Đ i v i th t c này thì G và ầ ủ ụ ị ề ằ ớ ố

VISITED không ph i là c c b . gi i thu t này ng ộ Ở ả ụ ả ậ ườ ộ i ta còn dùng m t

queue k ti p có kích th c n, v i F và R tr t i tr i l c và l i sau. Th ế ế ướ ỏ ớ ố ướ ớ ố ủ

c s d ng đ b sung ho c lo i b t c CQINSERT, CQDELETE s đ ụ ẽ ượ ử ụ ể ổ ạ ỏ ặ

1) VISITED(v) := 1;

2) Kh i t o queue v i v đã đ

ph n t }. ầ ử

3) while Q không r ng do begin

c n p vào; ở ạ ớ ượ ạ

ỗ

call CQDELETE(v, Q); {l y đ nh v ra kh i Q} ấ ỏ ỉ

for m i đ nh w lân c n v i v do ỗ ỉ ậ ớ

if VISITED(w) = 0 then

begin

call CQINSERT(w, Q);

VISITED(w) := 1;

end;

4) return

end;

c thăm s đ c n p vào queue M i đ nh đ ỗ ỉ ượ ẽ ượ ạ ệ ch m t l n vì câu l nh ỉ ộ ầ

while l p l i nhi u nh t n l n. ặ ạ ề ấ ầ

for s chi phí N u G đ ế ượ c bi u di n b i ma tr n lân c n thì câu l nh ậ ệ ể ễ ậ ở ẽ

O(n) th i gian đ i v i m i đ nh, do đó th i gian chi phí toàn b s là O(n ố ớ ỗ ỉ ộ ẽ ờ ờ

[2].

Tr c bi u di n v i danh sách lân c n thì chi phí t ng quát ườ ng h p G đ ợ ượ ể ễ ậ ớ ổ

chung là O(e).

Sau đây là th t củ ụ BFS theo đ quy cài đ t trên ngôn ng Pascal: ệ ữ ặ

procedure BFS(v:integer);

var j:integer;

begin

visited[v]:=1;

queue[1]:=v;

while (queue[1]<>0) do

begin

write(queue[1],' ');

for j:=1 to n do

if (a[queue[1],j]=1) and (visited[j]=0)

then

begin

visited[j]:=1;

k:=k+1;

queue[k]:=j;

end;

for j:=1 to k do

queue[j]:=queue[j+1];

k:=k-1;

end;

2.2.3. Tìm đ ườ ng đi và ki m tra tính liên thông c a đ th ủ ồ ị ể

Trong m c này ta xét các ng d ng các phép tìm ki m mô t trong các ứ ụ ụ ế ả

c vào vi c gi i hai bài toán c b n trên đ th : bài toán tìm đ m c tr ụ ướ ệ ả ơ ả ồ ị ườ ng

đi và bài toán xác đ nh các thành ph n liên thông c a đ th . ủ ồ ị ầ ị

2.2.3.1. Bài toán tìm đ ng đi gi a hai đ nh: Gi s s và t là hai đ nh nào đó ườ ữ ỉ ả ử ỉ

ng đi t c a đ th . Hãy tìm đ ủ ồ ị ườ ừ s đ n t. ế

Nh đã phân tích trên, th t c DFS(s), BFS(s) s cho phép thăm t ư ở ủ ụ ẽ ấ ả t c

ự các đ nh thu c cùng m t thành ph n liên thông v i s. Vì v y, sau khi th c ậ ầ ộ ộ ớ ỉ

hi n xong th t c, n u visited[t] = 0, thì đi u đó có nghĩa là không có ủ ụ ế ề ệ

đ ng đi t s đ n t, n u visited[t] = 1 thì t thu c cùng m t thành ph n liên ườ ừ ế ế ầ ộ ộ

thông v i s, hay nói m t cách khác: t n t i đ ng đi t s đ n t. Trong ồ ạ ườ ộ ớ ừ ế

tr ng h p t n t i đ ng đi đ ghi nh n đ ườ ợ ồ ạ ườ ể ậ ườ ế ng đi, ta dùng thêm bi n

Truoc[v] đ ghi nh n đ nh đi tr c đ nh v trong đ ng đi t s đ n v. Khi ể ậ ỉ ướ ỉ ườ ừ ế

if (visited[u]= 0) then

begin

Truoc[u]:=v

DFS(u);

end;

đó, đ i v i th t c DFS(v) c n s a đ i câu l nh if trong nó nh sau: ầ ử ổ ố ớ ủ ụ ư ệ

if (a[queue[1],u]=1) and (visited[u]=0) then

begin

visited[u]:=1;

k:=k+1;

queue[k]:=u;

Truoc[u]:=queue[1];

end;

Còn đ i v i th t c BFS(v) c n s a đ i câu l nh if trong nó nh sau: ầ ử ổ ố ớ ủ ụ ệ ư

Đ ng đi c n tìm đ c khôi ph c theo quy t c [6] sau: ườ ầ ượ ụ ắ

t ← p1 = Truoc[t] ← p2 = Truoc[p1] ← …← s.

: Hãy cho bi t đ th có 2.2.3.2. Tìm các thành ph n liên thông c a đ thi ầ ủ ồ ế ồ ị

bao nhiêu thành ph n liên thông và t ng thành ph n liên thông c a nó là ừ ủ ầ ầ

g m nh ng đ nh nào. ồ ữ ỉ

Do th t c DFS(s) (BFS(s) cho phép thăm t t c các đ nh thu c cùng ủ ụ ấ ả ộ ỉ

m t thành ph n liên thông v i s, nên s thành ph n liên thông c a đ th ồ ị ủ ầ ầ ộ ố ớ

chính b ng s l n g i đ n th t c này. V n đ còn l i là cách ghi nh n các ọ ế ủ ụ ố ầ ề ằ ấ ạ ậ

đ nh trong t ng thành ph n liên thông. Ta dùng thêm bi n ỉ ế Index[v] đ ghi ừ ể ầ

ế nh n ch s c a thành ph n liên thông ch a đ nh v, ta dùng thêm bi n ỉ ố ủ ứ ậ ầ ỉ

Inconnect đ đ m s thành ph n liên thông (bi n này c n đ ầ ể ế ế ầ ố ượ ở ạ c kh i t o

giá tr là 0). Th t c Thăm_đ nh(v) trong các th t c DFS(v) và BFS(v) có ủ ụ ủ ụ ỉ ị

nhi m v gán if trong các ch ng trình ụ ệ : Index[v] :=Inconnect, còn câu l nh ệ ươ

Inconnect=0;

chính g i đ n các th t c này c n đ c ch nh s a l i nh sau [6]: ọ ế ầ ượ ủ ụ ử ạ ỉ ư

if (visited[u] = 0) then

begin

Inconect := Inconect + 1 ;

DFS(v); (*BFS(v)*)

end;

ng trình chính, Inconect cho s K t thúc vòng l p th hai trong ch ặ ứ ế ươ

thành ph n liên thông c a đ th , còn bi n m ồ ị ủ ế ầ ố ảng Index[v], v˛ V cho phép

li t kê các đ nh thu c cùng m t thành ph n liên thông. ệ ầ ộ ộ ỉ

2.3. Đ th tr ng s ồ ị ọ ố

2.3.1. Khái ni mệ

c gán cho t Đ th mà m i c nh c a nó đ ỗ ạ ủ ồ ị ượ ươ ng ng v i m t s ớ ộ ố ứ

(nguyên ho c th c) đ ặ ự ượ ủ c g i là đ th tr ng s . S gán cho m i c nh c a ố ố ồ ị ọ ỗ ạ ọ

đ th đ ồ ị ượ c g i là tr ng s c a c nh. Đ ng đi, chu trình trong đ th có ườ ố ủ ạ ồ ị ọ ọ

tr ng s cũng đ ố ọ ượ ị c đ nh nghĩa gi ng nh trong tr ố ư ườ ố ng h p không tr ng s , ợ ọ

ch có khác là đ dài đ ộ ỉ ườ ng đi không ph i tính b ng s c nh đi qua, mà ằ ố ạ ả

qua.

đ c tính b ng t ng tr ng s c a các c nh đi ng đi ch xét ượ ố ủ ằ ạ ổ ọ đ Ở ườ ỉ ở ồ đ

th có tr ng s không âm. ố ọ ị

2.3.2. Bi u di n đ th tr ng s ễ ồ ị ọ ể ố

ệ Có th bi u di n đ th b ng nhi u c u trúc d li u khác nhau, vi c ề ồ ị ằ ể ể ữ ệ ễ ấ

ch n c u trúc d li u nào tùy thu c vào ng d ng và nh ng phép x lí tác ữ ệ ứ ụ ữ ử ấ ọ ộ

d ng lên nó. ụ

*Bi u di n b ng ma tr n k : ậ ề ằ ễ ể

‡ Xét đ th G = (V, E) có n đ nh và n ồ ị ỉ 1. Đánh s các đ nh t ố ỉ ừ ộ theo m t

quy đ nh nào đó, s d ng ma tr n 2 chi u A c p n đ bi u di n G. ể ể ử ụ ề ễ ậ ấ ị

˛ E

- V i đ th có tr ng s : ố ớ ồ ị ọ

g n u g là tr ng s c a cung (i, j) ế ố ủ ọ

A[i, j] = 0 n u i = j ế

ˇ E, ∞ là m t h ng s đ l n ố ủ ớ ộ ằ

∞ n u (i, j) ế

Ví d :ụ

ướ ng

Hình 2.6. Ma tr n k đ th tr ng s vô h ậ ề ồ ị ọ và đ th tr ng s có h

ố ng.

ồ ị ọ

ướ

ố

0 3 0 3 ∞ 3 5 2 ∞ 5 2 3 4 0 0 4

Chú ý: Ma tr n bi u di n các đ th vô h ng là đ i x ng. ồ ị ễ ể ậ ướ ố ứ

- Khai báo b ng pascal đ i v i đ th có tr ng s : ố ố ớ ồ ị ằ ọ

ủ ố ồ ị ỉ const n = …;{S đ nh c a đ th }

type graph = array[1..n,1..n] of data{Ki u dể ữ

ư ụ ệ ể ẳ ạ li u c th ch ng h n nh integer, real…};

var A,B : graph;

*Bi u di n đ th tr ng s b ng danh sách lân c n k . ề ố ằ ồ ị ọ ể ễ ậ

.

ng.

Hình 2.7a. Đ thồ ị tr ng s có h ố

ướ

ọ

Hình 2.7b. Bi u di n đ th tr ng s b ng danh sách lân c n k

ồ ị ọ

ố ằ

ậ ề

ễ

ể

Khai báo:

ủ ố ồ ị ỉ const n= …;{S đ nh c a đ th }

type graph = ^Node;

Node = record

ID: 1..n;

ụ ữ ể ể ệ ẳ Info: data{ki u d li u c th ch ng h n ạ

ư nh integer, real…};

Next:Graph;

end;

2.4. Đ ng đi trên đ th tr ng s ồ ị ọ ườ ố

m t đ nh đ n t t c các 2.4.1. Thu t toán tìm đ ậ ườ ng đi ng n nh t t ắ ấ ừ ộ ỉ ế ấ ả

đ nh khác ỉ

Trong tr ườ ậ ng h p đ th có tr ng s trên các cung là không âm thu t ồ ị ợ ọ ố

toán do Dijkstra đ ngh đ gi i quy t bài toán tìm đ ị ể ả ề ế ườ ng đi ng n nh t t ắ ấ ừ

s đ n t i c a đ th . Nhãn c a m i đ nh cho bi đ nh ỉ ế ấ ả t c các đ nh còn l ỉ ạ ủ ồ ị ỗ ỉ ủ ế t

c n trên c a đ dài đ ậ ủ ộ ườ ng đi ng n nh t t ắ ấ ừ s đ n nó. Các nhãn này s đ ẽ ượ c ế

bi n đ i theo th t c l p, mà m i b c l p có m t nhãn t m th i tr ủ ụ ặ ế ổ ở ỗ ướ ặ ạ ộ ờ ở

thành nhãn c đ nh. N u nhãn c a m t đ nh nào đó tr thành c đ nh thì s ộ ỉ ố ị ố ị ủ ế ở ẽ

cho ta không ph i là c n trên mà là đ dài c a đ ủ ườ ả ậ ộ ng đi ng n nh t t ắ ấ ừ s đ nế

c mô t c th nh sau [2] : nó. Thu t toán đ ậ ượ ả ụ ể ư

Procedure Dijkstra ;

{ Đ u vào: ng G=(V, E) v i n đ nh ầ ướ ớ ỉ

˛ V, ma tr n tr ng s ậ

Đ th có h ồ ị s ˛ V là đ nh xu t phát, a[u,v], u, v ấ ọ ố ;

ỉ 0, u, v ˛ V. Gi thi t: ả ế a[u,v] ‡

˛ s đ n t i d[v], v ừ ả ế ấ ả t c các đ nh còn l ỉ ạ

Đ u ra: Kho ng cách t ầ V.Truoc[v], v ˛ V, ghi nh n đ nh đi tr c v trong đ ậ ỉ ướ ườ ng đi ng n nh t t ắ ấ ừ s

} đ n v.ế

begin

V do

{ Kh i t o } ở ạ for v ˛ begin

d[v] := a[s,v] ;

Truoc[v] :=s ;

end ;

d[s] :=0 ; T :=V\{s}; {T là t p đ nh có nhãn t m th i} ậ ạ ờ ỉ

{ B c l p } ướ ặ

while T ≠ Ø do

begin

˛ T};

Tìm đ nh u nh nh t th a mãn d[u] = min {d[z]: z ấ ỏ ỏ ỉ

ố ị ỉ

T:= T\{u}; {c đ nh nhãn cho đ nh u} for v ˛ T do {Gán nhãn l ạ i cho các đ nh trong T} ỉ

if d[v] > d[u] + a[u,v] then

begin

d[v] = d[u] + a[u,v];

Truoc[v]:=u;

end;

Đ ph c t p c a gi i thu t: ứ ạ ủ ộ ả ậ Thu t toán Dijkstra tìm đ ậ c đ ượ ườ ắ ng đi ng n

2). [2]

nh t trên đ th sau th i gian c O(n ồ ị ấ ờ ỡ

ng có tr ng s G trong hình 2.8 d i đ y. Tìm Ví d 4:ụ Cho đ th vô h ồ ị ướ ố ọ ướ ấ

đ đ nh 1 đ n t t c các đ nh khác trong G. ườ ng đi ng n nh t t ắ ấ ừ ỉ ế ấ ả ỉ

Ma tr n tr ng s c a đ th có d ng: ố ủ ồ ị ậ ạ ọ

0 10 6 2

10 0 5 3

ố

6 5 0 1

Hình 2.8. Đ th vô ồ ị ng có tr ng s ví h ọ ướ d 4ụ

2 3 1 0

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 : d[v], Truoc[v]. Đ nh ướ ế t hai thành ph n c a nhãn theo th t ủ ứ ự ầ ỉ

đ c đánh d u ‘*’ là đ nh đ c l p đang xét, b ượ ấ ỉ ượ c ch n đ c đ nh nhãn ể ố ị ọ ở ướ ặ

nhãn c a nó không bi n đ i các b ổ ở ủ ế ướ c ti p theo, vì th ta đánh d u -. ế ế ấ

B ng 2.1. B ng k t qu tính toán theo thu t toán Dijkstra

ế

ả

ậ

ả

B c l p ướ ặ Kh i t o ở ạ 1 2 Đ nh 1 ỉ 0, 1 - - Đ nh 2 ỉ 10, 1 5, 4 5, 4 * Đ nh 3 ỉ 6, 1 3, 4 * - Đ nh 4 ỉ 2, 1* - -

Nh n xét: T b ng k t qu ta có th truy xu t ra đ ng đi t đ nh ừ ả ể ế ậ ấ ả c đ ượ ườ ừ ỉ

1 t i t i trong đ th nh sau: ớ ấ ả t c các đ nh còn l ỉ ạ ồ ị ư

Đ ng đi t đ nh 1 t i đ nh 2: ườ ừ ỉ ớ ỉ

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. ườ

Tr c đ nh 4 là Truoc[4] = 1 v y 1 là đ nh tr c đ nh 4 trên đ ng đi ướ ậ ỉ ỉ ướ ỉ ườ

này.

D ng, ta thu đ đ nh 1 t i đ nh 2 là: ừ c đ ượ ườ ng đi ng n nh t t ắ ấ ừ ỉ ớ ỉ

1 – 4 – 2 v i đ dài đ ớ ộ ườ ng đi ng n nh t là d[2] = 5. ấ ắ

T ta có các đ ng đi sau: ươ ự ườ

ng t • Đ 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. ấ ắ

• Đ 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. ườ ắ ấ

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ỉ

Rõ ràng ta có th gi i bài toán tìm đ ng đi ng n nh t gi a t t c các ể ả ườ ữ ấ ả ắ ấ

trên, trong c p đ nh c a đ th b ng cách s d ng n l n thu t toán mô t ặ ủ ồ ị ằ ử ụ ầ ậ ỉ ả ở

t là các đ nh c a đ th . Thu t toán Floyd đ c mô đó ta s ch n ẽ ọ s l n l ầ ượ ủ ồ ị ậ ỉ ượ

t trong th t c d i đây. ả ủ ụ ướ

Procedure Floyd;

{Đ u vào: ầ Đ th cho b i ma tr n tr ng s a[i,j], i, j= 1,2,…,n ọ ồ ị ậ ở ố

Đ u ra: ầ

Ma tr n đ ậ ườ ng đi ng n nh t gi a các c p đ nh d[i,j], i, j= 1,2,…,n. ặ ữ ắ ấ ỉ

Trong đó d[i,j] cho đ dài đ ộ ườ ng đi ng n nh t t ắ ấ ừ i đ n j. ế

Ma tr n ghi nh n đ ậ ậ ườ ậ ng đi p[i,j], i, j= 1,2,…,n. Trong đo p[i,j] ghi nh n

c đ nh đi t i j, n u p[i,j]=0 thì là đ ng đi tr c ti p đi t đ nh đi tr ỉ ướ ỉ i t ừ ớ ế ườ ự ế ừ

i đ nh j}. đ nh i t ỉ ớ ỉ

begin { Kh i t o } ở ạ

for i:= 1 to n do

for j:= 1 to n do

begin

d[i,j]:=a[i,j];

p[i,j]:=0;

end;

{ B c l p } ướ ặ

for k:= 1 to n do

for i:= 1 to n do

for j:= 1 to n do

if d[i,j] > d[i,k] + d[k,j] then

begin

d[i,j] := d[i,k] + d[k,j];

p[i,j] := k;

end;

3)[3].

Đ ph c t p c a thu t toán là O(n ộ ứ ạ ủ ậ

ng có tr ng s G trong hình 2.8 trên , tính và Ví d :ụ Cho đ th vô h ồ ị ướ ọ ố ở

i đ n j đ a ra ma tr n d và p v i d[i,j] cho đ dài đ ư ậ ớ ộ ườ ng đi ng n nh t t ắ ấ ừ ế và

c đ nh j trong đ p[i,j] ghi nh n đ nh đi tr ậ ỉ ướ ỉ ườ ng đi ng n nh t t ắ ấ ừ ế . i đ n j

- Kh i t o: ở ạ 0 0 0 0 0 10 6 2

0 0 0 0 10 0 5 3

0 0 0 0 6 5 0 1

K = 2

K = 1

2 3 1 0 Ma tr n dậ 0 0 0 0 Ma tr n pậ

0 0 0 0 0 10 6 2 0 0 0 0 0 10 6 2

0 0 0 0 10 0 5 3 0 0 0 0 10 0 5 3

0 0 0 0 6 5 0 1 0 0 0 0 6 5 0 1

K = 3

K = 4

2 3 1 0 Ma tr n dậ 0 0 0 0 Ma tr n pậ 2 3 1 0 Ma tr n dậ 0 0 0 0 Ma tr n pậ

0 4 4 0 0 5 3 2 0 0 0 0 0 10 6 2

4 0 4 0 5 0 4 3 0 0 0 0 10 0 5 3

4 4 0 0 3 4 0 1 0 0 0 0 6 5 0 1

2 3 1 0 Ma tr n dậ 0 0 0 0 Ma tr n pậ

đ nh 1 t 2 3 1 0 Ma tr n dậ Nh n xét: Đ ng đi t ậ 0 0 0 0 Ma tr n pậ ừ ỉ ườ ớ i các đ nh còn l ỉ ạ i trong đ th : ồ ị

ừ ỉ đ nh 1 đ n đ nh 2: ế ỉ

Đ ng đi t ườ • Tr c 2 là p[1,2]=4 v y 4 là đ nh tr c 2 trên đ ng đi này. ướ ậ ỉ ướ ườ

• Tr c đ nh 4 trên đ ng đi ướ c 4 là p[1,4]=0, v y đ nh 1 đ ng tr ậ ứ ỉ ướ ỉ ườ

ng đi thu đ c là: 1 – 4 – 2 v i đ dài đ ng đi là d[1,2] ườ ượ ớ ộ ườ này. • D ng, đ ừ

= 5.

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. ớ ộ

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. ớ ộ

Đ tìm đ ng đi gi a t ể ườ ữ ấ ả ặ t c c p đ nh còn l ỉ ạ i trong đ th ta làm t ồ ị ươ ng

.ự t

2.5. Cây khung và cây khung v i giá tr c c ti u ị ự ể ớ

ặ Khi m t graph G liên thông thì m t phép tìm ki m theo chi u sâu ho c ế ề ộ ộ

theo chi u r ng, s xu t phát t m t đ nh b t kỳ nào, cũng cho phép thăm ề ộ ẽ ấ ừ ộ ỉ ấ

đ c m i đ nh trong G. Trong tr ng h p này các cung c a G s đ ượ ọ ỉ ườ ẽ ượ c ủ ợ

phân làm hai t p: T p T bao g m các cung đ c dùng t i ho c đ ậ ậ ồ ượ ớ ặ ượ ệ c duy t

i. qua trong phép tìm ki m và t p B bao g m các cung còn l ậ ế ồ ạ

T t c các cung trong T cùng v i các đ nh t ấ ả ớ ỉ ươ ộ ng ng s t o thành m t ẽ ạ ứ

cây bao g m m t đ nh (nút) c a G. M t cây nh v y g i là ủ ư ậ ộ ỉ ồ ộ ọ cây khung c aủ

G. Tùy theo phép DFS ho c BFS đ c s d ng mà cây khung t ng ng s ặ ượ ử ụ ươ ứ ẽ

đ c g i là “cây khung theo chi u sâu” hay “cây khung theo chi u r ng”. ượ ề ộ ề ọ

V i đ th hình 2. 9 d i đây, ta có: ớ ồ ị ở ướ

a) Cây khung theo chi u sâu DFS(1) ề

b) Cây khung theo chi u r ng BFS(1) ề ộ

Hình 2.9. Cây khung DFS(1) và cây khung BFS(1)

Sau đây là th t c DFS và th t c BFS đ đánh d u các c nh trong cây ủ ụ ủ ụ ể ấ ạ

khung đ i v i đ th vô h ng trên Pascal: ố ớ ồ ị ướ

procedure DFS(v:integer);

var j:integer;

begin

visited[v]:=1;

for j:=1 to n do

if (visited[j]=0) and (a[v,j]=1) then

begin

trave[j]:=v;

DFS(j);

end;

*Th t c DFS(v): ủ ụ

: ủ ụ

end; *Th t c BFS(v) procedure BFS(v:integer);

var j:integer;

begin

visited[v]:=1;

queue[1]:=v;

while (queue[1]<>0) do

begin

for j:=1 to n do

if (a[queue[1],j]=1) and (visited[j]=0) then

begin

visited[j]:=1;

trave[j]:=queue[1];

k:=k+1;

queue[k]:=j;

end;

for j:=1 to k do

queue[j]:=queue[j+1];

k:=k-1;

end;

*Cây khung v i giá tr c c ti u: ị ự ể ớ

Cho G = (V, E) là graph vô h ng liên thông có tr ng s , v i cây khung ướ ố ớ ọ

T c a G, ta g i tr ng s c a cây T là t ng tr ng s các c nh trong T. Bài ọ ọ ố ủ ủ ạ ọ ố ổ

toán đ t ra là trong s các cây khung c a G, ch ra cây khung có tr ng s ủ ặ ố ọ ỉ ố

nh nh t, cây khung nh v y đ c g i là cây khung nh nh t c a graph và ư ậ ượ ọ ấ ủ ấ ỏ ỏ

bài toán đó là bài toán cây khung nh nh t. ấ ỏ

Có nhi u gi ề ả ị ự i thu t khác nhau đ xây d ng cây khung v i giá tr c c ự ể ậ ớ

i đây ta s trình bày thu t toán KRUSKAL và PRIM. ti u, d ể ướ ẽ ậ

**Thu t toán KRUSKAL [6] ậ

ậ Thu t toán Kruskal d a trên mô hình xây d ng cây khung b ng thu t ự ự ậ ằ

toán h p nh t: Tr c h t, đ t T = (V, Ø); T không ch a c nh nào thì có th ấ ợ ướ ế ứ ạ ặ ể

coi T g m g m n cây r i r c, m i cây ch có m t đ nh. Sau đó xét l n l ờ ạ ộ ỉ ầ ượ t ồ ồ ỗ ỉ

các c nh c a G, n u c nh đang xét n i hai cây khác nhau trong T thì thêm ố ủ ế ạ ạ

, đ ng th i h p nh t hai cây đó l i thành m t cây. C làm nh c nh đó vào T ạ ờ ợ ấ ồ ạ ứ ộ ư

i khi k t n p đ n – 1 c nh vào T thì ta đ c T là cây khung c a đ v y cho t ậ ớ ế ạ ủ ạ ượ ủ ồ

th . Ch có đi u thu t toán không ph i xét các c nh v i th t tùy ý mà xét các ớ ứ ự ề ậ ạ ả ị ỉ

đã s p x p: V i đ th vô h c nh theo th t ạ ứ ự ớ ồ ị ắ ế ướ ở ng G = (V, E) có n đ nh. Kh i ỉ

t c các c nh c a đ th t t o cây T ban đ u không có c nh nào. Xét t ạ ầ ạ ấ ả ủ ồ ị ừ ạ c nh ạ

có tr ng s nh đ n c nh có tr ng s l n, n u vi c thêm c nh đó vào T ỏ ế ố ớ ế ệ ạ ạ ố ọ ọ

không t o thành chu trình đ n trong T thì k t n p thêm c nh đó vào T. C làm ế ạ ứ ạ ạ ơ

nh v y cho t ư ậ ớ

i khi: • Ho c đã k t n p đ c n – 1 c nh vào trong T thì ta thu đ c T là ế ạ ặ ượ ạ ượ

• Ho c ch a k t n p đ n – 1 c nh nh ng h c k t n p thêm m t ộ ạ

cây khung nh nh t. ấ ỏ

ễ ứ ế ạ ư ế ạ ư ủ ặ

i thì s t o thành chu c nh vào b t kỳ vào trong s các c nh còn l ạ ấ ạ ố ạ ẽ ạ

trình đ n. Trong tr ơ ườ ệ ng h p này đ th G là không liên thông, vi c ồ ị ợ

tìm ki m cây khung th t b i. ấ ạ ế

*Thu t toán đ c mô t thông qua th t c Kruskal nh sau [2]: ậ ượ ả ủ ụ ư

procedure Kruskal;

begin

T = Ø;

while(| T | < (n-1) and (E≠ Ø )) do

E là c nh có đ dài nh nh t trong E; begin Ch nọ e ˛ ấ ạ ỏ ộ

E = E\ {e};

if (T ∪ {e} không ch a chu trình ứ ) then T = T ∪ {e};

end;

if (| T |

end;

2e) v i e là các cung thu c E(G)

Đ ph c t p c a thu t toán là: O(elog ứ ạ ủ ậ ộ ớ ộ

[3].

ng G trong hình 2.10 d i đây. Tìm Ví dụ 5: Cho đ th tr ng s vô h ồ ị ọ ố ướ ướ

cây khung nh nh t c a đ th G theo thu t toán Kruskal. ấ ủ ồ ị ậ ỏ

ồ ị

ướ

ng có tr ng s ví d ọ

ố

ụ

Hình 2.10. Đ th vô h 5

B c kh i t o ướ ở ạ . Đ t T = Ø; s p x p các c nh c a đ th theo th t ồ ị ứ ự ủ ế ặ ạ ắ

không gi m c a đ dài ta có dãy: ủ ộ ả

(3, 5), (5, 6), (4, 6), (4, 5), (3, 4), (1, 3), (2, 3), (2, 4), (1, 2)

Dãy đ dài t ộ ươ ứ ng ng c a chúng: ủ

4 7 8 9 16 17 18 22 33

t b su Ở ầ ặ ba l n l p đ u tiên ta l n l ầ ầ ượ ổ ng vào t p T các c nh (3, 5), (5, ậ ạ

ớ 6), (4, 6). Rõ ràng n u ta thêm c nh (4, 5) vào T thì nó s t o thành v i 2 ẽ ạ ế ạ

ng t cũng x y ra c nh (4, 6), (5, 6) đã có trong T chu trình. Tình hu ng t ạ ố ươ ự ả

ạ đ i v i c nh (3, 4) là c nh ti p theo trong dãy. Ti p theo ta b sung c nh ố ớ ạ ế ế ạ ổ

(1, 3), (2, 3) vào trong T và thu đ c T g m 5 c nh: ượ ạ ồ

ạ T = {(3, 5), (4, 6), (5, 6), (1, 3), (2, 3)} chính là t p c nh ậ

c a cây khung nh nh t c n tìm. ủ ấ ầ ỏ

* *Thu t toán PRIM [2] ậ

Thu t toán Kruskal ho t đ ng ch m trong tr ng ạ ộ ậ ậ ườ h p đ th dày (có ợ ồ ị

nhi u c nh). Trong tr ng h p đó ng i ta th ng pháp ề ạ ườ ợ ườ ườ ng s d ng ph ử ụ ươ

lân c n g n nh t. Trong ph ng pháp này, b t đ u t ấ ầ ậ ươ ắ ầ ừ ộ ỉ ủ m t đ nh tùy ý c a

ồ ị s, đ u tiên ta n i đ th ố s v i đ nh lân c n g n nó nh t, ch ng h n là đ nh i. ớ ỉ ầ ấ ạ ậ ầ ẳ ỉ

Nghĩa là trong s các c nh k c a đ nh ề ủ ạ ố ỉ ấ s, c nh (s, i) có đ dài nh nh t. ạ ỏ ộ

Ti p theo, trong s các c nh k v i hai đ nh s ho c i ta tìm c nh có đ dài ề ớ ế ạ ặ ạ ộ ố ỉ

nh nh t, c nh này d n đ n đ nh th 3 z, và ta thu đ ế ứ ạ ấ ẫ ỏ ỉ ượ ồ c cây b ph n g m ậ ộ

3 đ nh và 2 c nh. Quá trình này s đ c ti p t c cho đ n khi ta thu đ ẽ ượ ạ ỉ ế ụ ế ượ c

cây g m n đ nh và n - 1 c nh s chính là cây khung nh nh t c n tìm. ấ ầ ẽ ạ ồ ỏ ỉ

Gi ả ử ồ ị s đ th cho b ma tr n tr ng s C = {c[i, j], i, j =1, 2,…,n}. Trong ố ậ ở ọ

quá trình th c hi n thu t toán, ự ệ ậ m i b ở ỗ ướ ọ c đ có th nhanh chóng ch n ể ể

c gán đ nh và c nh c n b sung vào cây khung, các đ nh c a đ th s đ ỉ ủ ồ ị ẽ ượ ạ ầ ổ ỉ

cho các nhãn. Nhãn c a m i đ nh v s g m 2 ph n và có d ng [d[v], ẽ ồ ủ ầ ạ ỗ ỉ

near[v]], trong đó d[v] dùng đ ghi nh n đ dài c a c nh có đ dài nh ủ ể ạ ậ ộ ộ ỏ

nh t trong s các c nh n i đ nh v v i các đ nh c a cây khung đang xây ớ ố ỉ ủ ạ ấ ố ỉ

đ nh v đ n t p đ nh c a cây khung), nói d ng (ta s g i là kho ng cách t ự ẽ ọ ả ừ ỉ ế ậ ủ ỉ

m t cách chính xác.

ộ d[v] : = min{c[v, w] : w ˛ VH }(= c[v, z]);

Còn near[v] ghi nh n đ nh c a cây khung g n v nh t ( near[v]:=z). ủ ậ ầ ấ ỉ

prim đ c mô t thông qua th t c sau [2]: * Thu t toán ậ ượ ả ủ ụ

Procedure Prim;

begin

{Kh i t o} ở ạ

Ch n s là m t đ nh nào đó c a đ th ; ủ ồ ị ộ ỉ ọ

VH := {s}; T = Ø;

d[s] := 0; near[s] := s; for v ˛ V \ VH do

begin

d[v] := c[s,v];

near[v] := s;

end;

{B c l p} ướ ặ

stop:=false;

while not stop do

begin

˛ V \ VH};

V \ VH th a mãn : d[u] = min {d[v] : u

Tìm u ˛ VH := VH ¨ ỏ {u}; T := T ¨ {u, near[u]} ;

if |VH |= n then

begin

H = (VH ,T) là cây khung nh nh t c a đ th ấ ủ ồ ị ; ỏ

stop := true;

end

else for v ˛ V \ VH do

if d[v] > c[u, v] then

begin

d[v]:=c[u,v];

near[v]:=u;

end;

2) v i n là s đ nh [2].

Đ ph c t p c a thu t toán là O(n ộ ứ ạ ủ ậ ố ỉ ớ

0 33 17 ∞ ∞ ∞

Ví d : Tìm cây khung nh nh t cho đ th tr ng s vô h ng G trong ồ ị ọ ụ ấ ỏ ố ướ

33 0 18 22 ∞ ∞

hình 2.10 theo thu t toán Prim. ậ

17 18 0 16 4 ∞

∞ 22 16 0 9 8

∞ ∞ 4 9 0 7

∞ ∞ ∞ 8 7 0

Ma tr n tr ng s c a đ th có d ng: ố ủ ồ ị ậ ạ ọ

B ng d i đây ghi nhãn c a các đ nh trong các b c l p c a thu t toán, ả ướ ủ ỉ ướ ặ ủ ậ

c ch n đ b sung vào cây khung (khi đó nhãn đ nh đánh d u * là đ nh đ ấ ỉ ỉ ượ ể ổ ọ

c l p ti p theo, vì v y ta đánh c a nó không còn b bi n đ i trong các b ủ ị ế ổ ướ ặ ế ậ

Bướ

Đ nh 1

Đ nh 2

Đ nh 3

Đ nh 4

Đ nh 5

Đ nh 6

ỉ

c l pặ Kh iở

[0, 1]

[33, 1]

[17, 1]*

[∞, 1]

- - -

[18, 3] [18, 3] [18, 3]

- - -

[16, 3] [9, 5] [8, 6]*

[4, 3]* - -

[∞, 1] [7, 5]* -

t oạ 1 2 3

1, 3 1, 3, 5 1, 3, 5, 6 1, 3, 5, 6,

(3,1) (3,1), (5,3) (3,1), (5,3), (6,5) (3,1), (5,3), (6,5),

[18, 3]*

4 1, 3, 5, 6,

(4,6) (3,1), (5,3), (6,5),

4, 2

(4,6), (2,3)

d u – đ ghi nh n đi u đó): ấ ề ể ậ

Nh n xét: Đ tìm đ ể ậ ượ ầ c cây khung nh nh t v i đ nh xu t phát là 1, đ u ấ ớ ỉ ấ ỏ

tiên ta đ a đ nh 1 vào t p c nh trong cây khung. Sau đó ta k t n p đ ế ạ ư ậ ạ ỉ ượ c

đ nh 3 vào trong cây vì d[3] = 17 là nh nh t trong các d[v] v i v là các đ nh ỏ ỉ ấ ớ ỉ

ngoài cây. Sau khi k t n p n u d[v]>c[3,v] thì d[v] = c[3, v]. Ti p theo ta ế ạ ế ế

c đ nh 5 vào cây vì d[5] = 3 là nh nh t k t n p đ ế ạ ượ ỉ ấ trong các đ nh ngoài cây ỉ ỏ

ng t và d[v] cũng thay đ i n u d[v]>c[5,v]. C t ổ ế ứ ươ ự ế ạ nh v y ta k t n p ư ậ

đ c thêm các đ nh 6, 4 và 2. Sau khi k t n p đ n đ nh ta thu đ ượ ế ạ ủ ỉ ỉ ượ ậ c t p

c nh c a cây khung là: (3,1), (3,1), (5,3), (6,5), (4,6), (2,3). ạ ủ

*Cài đ t thu t toán prim: ậ ặ

Input: D li u v graph vô h ng đ ữ ệ ề ướ ượ c nh p t ậ ừ ả file văn b n

MINTREE.INP trong đó dòng 1 ch a 2 s nguyên d ng n và m là s đ nh ứ ố ươ ố ỉ

và s c nh c a graph, m i dòng i trong m dòng ti p theo ch a 3 nguyên ố ạ ứ ủ ế ỗ

d ng g m x, y là hai đ nh và z là tr ng s c a c nh i. ươ ố ủ ạ ồ ọ ỉ

Output: Xu t ra file MINTREE.OUT danh sách các c nh và t ng tr ng s ấ ạ ổ ọ ố

các c nh trong cây khung nh nh t c a graph. ấ ủ ạ ỏ

uses crt;

const fo='MINTREE.INP';

f1='MINTREE.OUT';

Emax=1000;

var f:text;

a:array[1..100,1..100] of integer;

b,d,pre:array[1..100] of integer;

n,m:integer;

procedure khoitao;

var i,j:byte;

x,y,z:integer;

begin

assign(f,fo);

reset(f); readln(f,n,m);

for i:=1 to n do

for j:=1 to n do

a[i,j]:=Emax;

Ch ng trình d i đây v i đ nh b t đ u là 1: ươ ướ ắ ầ ớ ỉ

for i:=1 to m do

begin

read(f,x,y,z); a[x,y]:=z; a[y,x]:=z;

end;

close(f);

end;

procedure Prim;

var i,j,k,min,u,t:integer;

begin

for i:= 2 to n do

begin

b[i]:=0;

d[i]:=a[1,i];

pre[i]:=1;

end;

d[1]:=0; b[1]:=1; u:=0; k:=1;

while (k<=n) do

begin

min:=Emax;

for i:=1 to n do

if (b[i]=0) and (min>d[i]) then

begin

min:=d[i];

u:=i;

end;

if (min=Emax) and (k

else

begin

b[u]:=1; k:=k+1;

for i:=1 to n do

if (b[i]=0) and (d[i]>a[u,i]) then

begin

d[i]:=a[u,i]; pre[i]:=u;

end;

t:=0;

if (k

else begin

writeln('Danh sach canh trong cay khung nho nhat:');

for i:=2 to n do

begin

writeln(pre[i],' ',i,' trong so: ',a[pre[i],i]);

t:=t+1;

end; end;

writeln('Tong trong so cac canh cua cay khung: ',t);

end;

begin

khoitao;

Prim;

end. 2.6. K t lu n ch

ng 2 ế ậ ươ

Trong ch ng này chúng ta đã đ a ra và cài đ t đ c m t s thu t toán ươ ặ ượ ư ộ ố ậ

c b n trên đ th liên quan đ n các bài toán c b n: Bi u di n đ th trên ở ả ơ ả ồ ị ồ ị ế ễ ể

ể máy tính đ i v i đ th không tr ng s và có tr ng s v i các cách bi u ố ớ ồ ị ố ớ ố ọ ọ

di n khác nhau nh bi u di n b ng danh sách c nh, danh sách lân c n… ư ể ễ ễ ậ ằ ạ

ệ Phép duy t đ th trong đó đ a ra phép duy t theo chi u sâu, phép duy t ệ ồ ị ư ề ệ

theo chi u r ng. Bên c nh đó còn có các thu t toán liên quan đ n đ ng đi ề ộ ế ạ ậ ườ

và ki m tra tính liên thông c a đ th , bài toán cây và cây khung v i giá tr ủ ồ ị ể ớ ị

ng này chúng ta đã c c ti u. Đ i v i đ th tr ng s trình bày trong ch ự ố ớ ồ ị ọ ể ố ươ

c khái ni m, cách bi u di n, bên c nh đó đ a ra hai thu t toán đ a ra đ ư ượ ư ễ ệ ể ậ ạ

ng đi ng n nh t đó là thu t toán Dijkstra tìm liên quan đ n bài toán đ ế ườ ắ ấ ậ

đ m t đ nh t ườ ng đi ng n nh t t ắ ấ ừ ộ ỉ ớ i m i đ nh và thu t toán Floyd tìm ậ ọ ỉ

đ ườ ng đi ng n nh t gi a m i c p đ nh trên đ th . ồ ị ọ ặ ữ ắ ấ ỉ

Ch ng 3 ươ

NG D NG GRAPH GI I M T S BÀI TOÁN TRONG Ứ Ụ Ả Ộ Ố

CH ƯƠ NG TRÌNH TIN H C PH THÔNG Ọ Ổ

Trong ch i quy t m t s bài toán c th theo ươ ng này s đ a ra và gi ẽ ư ả ụ ể ộ ố ế

t ng d ng c th d a trên lý thuy t v Graph và m t s thu t toán trên ế ề ừ ụ ể ự ộ ố ạ ậ

Graph các ch ng tr ở ươ ướ ậ c, bên c nh đó v i m i d ng đ a ra các bài t p ỗ ạ ư ạ ớ

cùng d ng. Các ch ng trình trong ch ng này đ c cài đ t trên ngôn ng ạ ươ ươ ượ ặ ữ

l p trình Pascal. ậ

3.1. Gi i thi u ng trình ớ ệ m t sộ ố bài toán v ề đ th trong ch ồ ị ươ tin h cọ

trung h c ph thông ọ ổ

Các bài toán v đ th các tr ng trung h c ph thông ngoài chuyên ề ồ ị ở ườ ọ ổ

h u nh ít g p, t p trung ch y u trong ch ầ ủ ế ư ặ ậ ươ ọ ng trình tin h c 10 và tin h c ọ

11 c a các tr ủ ườ ề ng trung h c ph thông chuyên. M t s n i dung v lý ộ ố ộ ọ ổ

thuy t đ th trong ch ế ồ ị ươ ng trình tin h c 10 c a tr ọ ủ ườ ng trung h c ph thông ọ ổ

chuyên nh : ư

Mô hình đ th có và không có tr ng s , bài toán tìm đ ồ ị ọ ố ườ ắ ng đi ng n

nh t, bài toán tìm cây khung nh nh t. Yêu c u h c sinh c n n m đ c các ấ ấ ầ ầ ắ ỏ ọ ượ

khái ni m c b n liên quan đ n mô hình đ th : Đ nh, c nh (cung), đ ơ ả ồ ị ệ ế ạ ỉ ườ ng

đi, chu trình, tính liên thông, thành ph n liên thông, cây khung, tr ng s … ầ ọ ố

Bi c hai thu t toán tiêu bi u v đ ng đi ng n nh t đó là ế t và n m đ ắ ượ ề ườ ể ậ ắ ấ

ể Dijkstra và Floyd, hai thu t toán tiêu bi u v cây khung v i giá tr c c ti u ị ự ể ề ậ ớ

đó là Kruskal và Prim.

ng trình tin h c 11 c a trung h c ph thông chuyên t p trung sâu ch Ở ươ ủ ậ ọ ọ ổ

vào các bài toán v đ th nh : Bi u di n đ th , duy t đ th và m t s bài ề ồ ị ư ệ ồ ị ộ ố ồ ị ể ễ

toán trong đ tài ch a đ c p t ề ậ ớ ư ề ự i các bài toán sau: Bài toán v lu ng c c ề ồ

ng tăng lu ng, đ nh lí Ford – Fulkerson, Thu t toán Ford – đ i, lát c t, đ ạ ắ ườ ậ ồ ị

ổ Fulkerson tìm lu ng c c đ i trong m ng, m t s bài toán v lu ng t ng ạ ề ồ ộ ố ự ạ ồ

quát…

3.2. M t s bài toán v phép duy t đ th ệ ồ ị ộ ố ề

3.2.1. Bài toán 1- Đ m s thành ph n liên thông [4] ố ế ầ

Vi t ch ng trình đ m s thành ph n tính liên thông c a m t đ th vô ế ươ ộ ồ ị ủ ế ầ ố

h ng đ c bi u di n b i ma tr n k a v i: ướ ượ ề ể ễ ậ ở ớ

a[i, j] = 1 n u có đ ng đi t i j ế ườ i t ừ ớ

ng đi t i j a[i, j] = 0 n u không có đ ế ườ i t ừ ớ

• D li u trong file L THONG.INP • Dòng đ u ghi s n là s đ nh c a đ th (0 < n < 100) ố ỉ

ữ ệ

• Dòng i + 1 (1 £

ủ ồ ị ầ ố

i £ n) ch a n s a[i, 1] a[i, 2]… a[i. n] ứ ố

ầ

K t qu : ả ế Đ th có 1 thành ph n liên ồ ị thông.

LTHONG.INP 8 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0

Thông báo k t qu ra màn hình. ế ả

H ng d n gi i thu t: ướ ẫ ả ậ Đ i v i bài toán này ta có th s d ng phép ể ử ụ ố ớ

ệ ớ duy t đ th theo chi u sâu hay theo chi u r ng. Ta s g i phép duy t v i ệ ồ ị ề ộ ẽ ọ ề

c đánh d u, v i m i l n phép duy t DFS(v) đ nh đ u tiên g p mà ch a đ ỉ ư ượ ặ ầ ỗ ầ ệ ấ ớ

hay BFS(v) v i đ nh v là đ nh ch a đ ớ ỉ ư ỉ ượ c đánh d u thì bi n đ m s thành ế ế ấ ố

ph n liên thông tăng lên 1. Ch ng trình d i đây có th t c ầ ươ ướ ủ ụ Process

th c hi n công vi c đ m và thông báo ra màn hình s thành ph n liên thông ệ ế ự ệ ầ ố

c a đ th , th t c ủ ồ ị ờ ọ i g i th t c duy t đ th theo chi u sâu ệ ồ ị ủ ụ ề ủ ụ Process có l

uses crt;

const fo='LIENTHONG.INP';

var fr:text;

a:array[1..100,1..100] of integer;

visited:array[1..100] of integer;

DFS(v) v i DFS(v) duy t v i v là đ nh ch a đ c đánh d u. ệ ớ ư ượ ớ ỉ ấ

n,v,i,Inconect:integer;

procedure Khoitao;

var j:integer;

begin

assign(fr,fo);

reset(fr);

readln(fr,n);

for i:=1 to n do visited[i]:=0;

for i:=1 to n do

for j:=1 to n do

read(fr,a[i,j]);

writeln(n);

writeln('Ma tran ke cua do thi: ');

for i:=1 to n do

begin

for j:=1 to n do write(a[i,j],' ');

writeln;

end;

close(fr);

end;

procedure DFS(v:integer);

var j:integer;

begin

visited[v]:=1;

Index[v]:=Inconect;

for j:=1 to n do

if (visited[j]=0) and (a[v,j]=1) then DFS(j);

end;

procedure Process;

var j: integer;

begin

Inconect:=0;

for i:=1 to n do

if visited[i]=0 then

begin

Inconect:=Inconect + 1;

DFS(i);

end;

writeln('Do thi co ',Inconect,' thanh phan lien

thong!');

end;

begin

clrscr;

Khoitao;

Process;

readln

end.

3.2.2. Bài toán 2 - D ti c ự ệ

Có N ng i khách (N<100) mang s hi u t ườ ố ệ ừ 1 đ n N, đ ế ượ c m i đ n d ờ ế ự

i quen bi t nhau. D li u v m i quan h ti c. Gi a h có m t s ng ọ ộ ố ữ ệ ườ ế ề ố ữ ệ ệ

quen bi t này đ ế ượ c cho trong m t file văn b n có tên là KHACH.INP có ả ộ

c u trúc nh sau: Dòng đ u tiên c a nó ch a s l ầ ấ ứ ố ượ ủ ư ỗ ng khách m i N. M i ờ

dòng th i trong s N dòng ti p theo ch a s hi u c a các ng ế ứ ố ệ ủ ứ ố ườ ủ i quen c a

khách i, các s hi u đ ố ệ ượ ế c ghi cách nhau b i ít nh t m t d u cách. N u ộ ấ ấ ở

i th i không quen m t ai dòng th i ch a duy nh t m t s 0 th hi n ng ấ ể ệ ộ ố ứ ứ ườ ứ ộ

i khách cũng đ trong s nh ng ng ố ữ ườ ượ c m i đ n d ti c. ờ ế ự ệ

Ng i ta mu n x p các khách này vào các phòng ti c, sao cho hai khách ườ ệ ế ố

trrong cùng m t phòng ho c là quen bi t nhau ho c là có th làm quen ở ặ ộ ế ể ặ

nhau thông qua nh ng ng i quen bi ữ ườ ế t trung gian c a h . ủ ọ

Vi t ch ng trình nh p d li u vào t file, sau đó tìm cách phân khách ế ươ ữ ệ ậ ừ

vào các phòng ti c sao cho s phòng ph i đ c s d ng là ít nh t. K t qu ả ượ ử ụ ệ ế ấ ố ả

phân công đ ượ ư ầ c đ a ra m t file văn b n có tên là KHACH.OUT, dòng đ u ả ộ

tiên ch a s phòng ti c c n s d ng K, m i dòng th i trong s K dòng ầ ử ụ ứ ố ứ ệ ố ỗ

ti p theo ghi s hi u c a khách x p vào phòng ti c i. ố ệ ủ ệ ế ế

KHACH.OUT 3 1 2 3 4 5

KHACH.INP 5 2 3 1 3 1 2 0 0

Ví d :ụ

H ng d n gi i thu t: ướ ẫ ả ể ử ụ ậ Đ i v i bài toán trên chúng ta có th s d ng ố ớ

cách duy t đ th theo chi u r ng ho c theo chi u sâu, đ i v i bài toán này ặ ệ ồ ị ề ộ ố ớ ề

thì s hi u c a m i khách i trong n khách t ng ng v i m t đ nh i trong ố ệ ủ ỗ ươ ộ ỉ ứ ớ

đ th g m n đ nh. Th c ch t vi c đi tìm s phòng ti c c n s d ng K và ồ ị ồ ệ ầ ử ụ ự ệ ấ ố ỉ

s hi u c a khách trong t ng phòng trong K phòng c n s d ng theo yêu ố ệ ầ ử ụ ừ ủ

ng ng v i vi c đi tìm s thành ph n liên thông c a đ c u c a bài toán t ầ ủ ươ ứ ủ ồ ệ ầ ố ớ

th và các đ nh thu c cùng m t thành ph n liên thông. ầ ộ ộ ị ỉ

Th t c ướ i đây th c hi n công vi c tìm s phòng ti c K và ệ ự ệ ệ ố ủ ụ Process d

s hi u các khách trong t ng phòng i trong K phòng, th t c ố ệ ừ ủ ụ Process có

l ờ ọ i g i th t c duy t đ th theo chi u sâu ệ ồ ị ủ ụ ề DFS(v) v i ớ DFS(v)đ tìmể

nh ng khách quen bi t v i t ữ ể ặ ữ ế ớ v ho c có th quen bi ế v qua nh ng khách

procedure DFS(v:integer);

var j:integer;

begin

visited[v]:=1;

Index[v]:=Inconect;

for j:=1 to n do

if (visited[j]=0) and (a[v,j]=1) then DFS(j);

end;

procedure Process;

var j: integer;

begin

trung gian:

assign(fw,f1);

rewrite(fw);

Inconect:=0;

for i:=1 to n do

if visited[i]=0 then

begin

Inconect:=Inconect + 1;

DFS(i);

end;

writeln(fw,Inconect);

for i:=1 to Inconect do

begin

for j:=1 to n do

if Index[j]=i then write(fw,j,' ');

writeln(fw);

end;

close(fw);

end;

3.2.3. Bài toán 3 - B n đ [2] ả ồ

B n đ giao thông đ c cho b i n nút giao thông đánh s là 1,2,…,n và ả ồ ượ ở ố

1, E2,…, Em m i đo n n i 2 trong s n nút

ng E h th ng g m m đo n đ ồ ệ ố ạ ườ ạ ỗ ố ố

giao thông nói trên. B n đ giao thông đ ả ồ ượ ữ c g i là liên thông đ n n u gi a ế ơ ọ

2 nút giao thông b t kì ch có đúng m t đ ng đi n i chúng. D li u cho ộ ườ ấ ỉ ữ ệ ố

trong file văn b n có tên MAP.INP, dòng đ u tiên có ch a các s n, m, hai ứ ả ầ ố

ứ s ghi cách nhau b i d u cách. M i dòng i trong s m dòng ti p theo ch a ố ở ấ ế ố ỗ

c n i b i đo n đ ng E s hi u hai nút giao thông đ ố ệ ượ ố ở ạ ườ

Vi t ch ng trình nh p d li u vào t file sau đó thông báo xem b n đ ế ươ ậ ữ ệ ừ ả ồ

có ph i là liên thông đ n hay không. ả ơ

K T QU : Ả B n đ không liên thông đ n ơ

Ế ả

ồ

MAP.INP 5 4 1 2 4 1 3 5 2 3 1 4 5 5

Ví d :ụ

H ng d n gi i thu t: ướ ẫ ả ậ Đ i v i yêu c u c a bài toán t ầ ố ớ ủ ươ ớ ng ng v i ứ

vi c duy t đ th xem đ th có liên thông đ n hay không? Đ i v i bài toán ệ ồ ị ố ớ ồ ị ệ ơ

trên ta đi tìm n u đ th t ng ng m i nút giao thông là m t đ nh mà có ồ ị ươ ế ộ ỉ ứ ỗ

đúng m t thành ph n liên thông thì thông báo b n đ liên thông đ n, ng ầ ả ộ ơ ồ ượ c

l i thông báo không liên thông đ n. ạ ơ

Th t c i đây ki m tra và thông báo b n đ có liên thông ướ ể ả ồ ủ ụ Process d

i g i th t c duy t đ th theo đ n hay không, th t c ơ ờ ọ ệ ồ ị ủ ụ ủ ụ Process có l

procedure DFS(v:integer);

var j:integer;

begin

visited[v]:=1;

for j:=1 to n do

if (visited[j]=0) and (a[v,j]<>0) then DFS(j);

end;

procedure Process;

var j: integer;

begin

Inconect:=0;

for i:=1 to n do

if visited[i]=0 then

begin

Inconect:=Inconect + 1;

DFS(i);

end;

if (Inconect>1) then write('Ban do khong lien thong don')

else write('Ban do lien thong don!');

end;

chi u sâu ề ữ ể ỉ DFS(v) v i ớ DFS(v)đ duy t nh ng đ nh mà liên thông v i ệ ớ v:

3.3. M t s bài toán v đ ộ ố ề ườ ng đi trong đ th ồ ị

3.3.1. Bài toán 1 - Đ ng đi [4] ườ

Có N thành ph . Bi t r ng đ ng đi gi a hai thành ph b t kì (n u có) ố ế ằ ườ ố ấ ữ ế

ng đi hai chi u. S đ m ng l đ u là đ ề ườ ơ ồ ạ ề ướ i giao thông c a N thành ph ủ ố

này cho b i ma tr n k A[i,j] trong đó: ề ậ ở

- A[i,j] là đ dài đ ng đi t ộ ườ ừ thành ph i đ n thành ph j ế ố ố

ng đi t - A[i,j]= 0 n u không có đ ế ườ ừ thành ph i đ n thành ph j ế ố ố

- A[i,j]= A[j,i]

- A[i,j] nguyên, không âm

Hãy xác đ nh đ ng đi ng n nh t gi a hai thành ph P và Q hay thông ị ườ ữ ấ ắ ố

báo không t n t i l i gi i. ồ ạ ờ ả

D li u: ữ ệ Cho trong file DUONGDI.INP g m N+2 dòng ồ

£ 50)

- Dòng đ u ch a s N (N nguyên d ứ ố

ng, N ầ ươ

ố

- Dòng hai ch a 2 s P và Q ứ - Dòng i+1 (1 £ i £ N) ghi N s A[i,1] A[i,2]…A[i,N] ố

Các s ghi trên cùng m t dòng ghi cách nhau ít nh t m t d u cách. ộ ấ ấ ộ ố

K t qu : ả Xu t ra màn hình. ế ấ

Ế

K T QU : Ả 1 → 2 → 3 → 4 Đ dài đ

ng đi là 6

ườ

ộ

DUONGDI.INP 4 1 4 0 3 0 10 3 0 1 0 0 1 0 2 10 0 2 0

Ví d :ụ

H ng d n gi i thu t: ướ ẫ ả ậ Yêu c u c a bài toán trên t ầ ủ ươ ệ ng ng v i vi c ứ ớ

đi tìm đ ườ ng đi ng n nh t trong đ th t ấ ồ ị ươ ứ ộ ng ng v i m i thành ph là m t ắ ỗ ố ớ

ng đi t đ nh c a đ th , vì A[i, j] là đ dài đ ỉ ủ ồ ị ộ ườ ừ ố thành ph i đ n thành ph j ế ố

thành nên các giá tr A[i, j] luôn d ị ươ ng. Vi c tìm đ ệ ườ ng đi ng n nh t t ắ ấ ừ

ph i đ n thành ph j b t kỳ t ng ng v i vi c tìm đ ế ấ ố ố ươ ứ ệ ớ ườ ấ ng đi ng n nh t ắ

trên đ th . ồ ị

Th t c i đây cài đ t cài đ t theo thu t toán Dijkstra ướ ặ ặ ậ ủ ụ Process(p) d

ch ng tr c v i P là đ nh xu t phát, thông báo không t n t i l i gi ở ươ ướ ồ ạ ờ ấ ớ ỉ ả i

ng đi t P t i Q, ng i xu t ra màn hình đ ng đi n u không có đ ế ườ ừ ớ c l ượ ạ ấ ườ

procedure Process(p: integer);

var i,j,u,min,w,v,k:integer;

Trave:array[1..100] of integer;

begin

for i:=1 to n do

begin

b[i]:=0;

d[i]:=a[p,i];

pre[i]:=p;

end;

d[p]:=0; b[p]:=1;

k:=1;

while (k

begin

min:=Emax;

for i:=1 to n do

if (b[i]=0) and (min>d[i]) then

begin

min:=d[i];

u:=i;

end;

b[u]:=1; k:=k+1;

for v:= 1 to n do

if (b[v]=0) and (d[v]>d[u]+a[u,v]) then

begin

pre[v]:=u;

d[v]:= d[u] + a[u,v];

end;

Trave[1]:=q; k:=2; w:=q;

while(q<>p) do

begin

Trave[k]:=pre[q];

q:=pre[q];

k:=k+1;

ng n nh t t P t i Q và đ dài c a nó: ấ ừ ắ ớ ủ ộ

end;

k:=k-1; Trave[k]:=p;

if (d[q]=Emax) then

writeln('Khong ton tai loi giai!')

else

begin

for i:= k downto 2 do write(Trave[i],' -> ');

writeln(Trave[1]);

writeln('Do dai duong di la: ',d[w]);

end;

end; 3.3.2. Bài toán 2 - Du l ch [4]

ị

i khách du l ch mu n đi thăm n thành ph đ c đánh s t M t ng ộ ườ ố ượ ố ị ố ừ 1

i giao thông gi a n thành ph này là 2 chi u và đ c cho đ n n. M ng l ế ạ ướ ữ ề ố ượ

ó A[i, j] = 1 n u có đ ng đi gi a thành ph i và b i ma tr n A[i,j] trong đ ở ậ ế ườ ữ ố

thành ph j, A[i,j] = 0 trong tr i. Hãy thi trình ố ườ ng h p ng ợ c l ượ ạ t l p l ế ậ ộ

cho ng i khách hay thông báo không t n t i l i gi i. ườ ồ ạ ờ ả

D li u: ữ ệ Cho trong file BROAD.INP g m n+1 dòng ồ

• Dòng 1: Ghi s nguyên d

• Dòng i + 1(1 £

£ ng n( n 20) ươ

n): Ghi n s nguyên không âm ố i £ ố

A[i,1], A[i,2], …, A[i,n]

K t qu : . ả Xu t ra màn hình ế ấ

Ví d :ụ

Ế

Ả:

K T QU Chu trình HAMILTON 1 → 3 → 2 → 4 → 5 → 1

BROAD.INP 5 0 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0

H ng d n gi i thu t: trình cho ng i khách, t ướ ẫ ả ậ Đ thi ể t l p l ế ậ ộ ườ ươ ng

ng v i vi c ta đi tìm đ th có t n t i chu trình Hamilton hay không. Ta ch ứ ồ ị ồ ạ ệ ớ ỉ

vi c tìm h t m i kh năng đ ng đi và ki m tra đ ế ệ ả ọ ườ ể ườ ủ ng đi này có qua đ n

đ nh c a đ th hay không. ỉ ủ ồ ị

Th t c i đây có l i g i th t c đ quy ướ ờ ủ ụ ệ ọ ủ ụ Process d Try(i:

ủ ụ ẽ ể ử ứ ọ integer) đ th các cách ch n đ nh th i trong hành trình. Th t c s ỉ

trình cho ng i khách n u t n t i chu trình Hamilton và ng đ a ra l ư ộ ườ ế ồ ạ ượ ạ i c l

procedure Try(i:integer);

var j:byte;

begin

for j:=1 to n do

if (free[j]=1) and (a[x[i-1],j]=1) then

begin

x[i]:=j;

if (i

begin

Free[j]:=0;

Try(i+1);

Free[j]:=1;

end

else

if (ok=0) then

begin

Result;

ok:=1;

break;

end;

procedure Process;

var i:byte;

thì thông báo không t n t i l i gi i. ồ ạ ờ ả

begin

x[1]:=1; Free[1]:=0;

Try(2);

if (ok=1) then

begin

write('Chu trinh Hamilton: ');

for i:=1 to n do

write(p[i],' -> '); write(p[n+1]);

end

else writeln('Khong ton tai loi giai!');

end;

3.3.3. Bài toán 3 - Đ n tr ng [7] ế ườ

Ngày 04/07 t i là ngày t ch c thi tuy n sinh đ i h c tr ng ĐHBK. ớ ổ ứ ạ ọ ở ườ ể

Là h c sinh l n đ u ra thành ph đi thi, Hi u không mu n vì đi mu n mà ế ầ ầ ọ ố ộ ố

phòng thi nên đã chu n b khá k càng. Ch còn l g p tr c tr c ụ ặ ặ ở ẩ ỹ ị ỉ ạ ộ i m t

công vi c khá gay go là Hi u không bi t đi đ ng nào t ệ ế ế ườ i tr ớ ườ ắ ng là ng n

nh t.ấ

B n đ thành ph là g m có N nút giao thông và M con đ ả ồ ố ồ ườ ng n i các ố

nút giao thông này. Có 2 lo i con đ ng là đ ng 2 ạ ườ ườ ng 1 chi u và đ ề ườ

chi u. Đ dài c a m i con đ ng. ủ ề ỗ ộ ườ ng là m t s nguyên d ộ ố ươ

nút giao thông 1 còn tr ng ĐHBK nút giao thông N. Ch Hi u tr ế ọ ở ỗ ườ ở

B n hãy l p trình giúp Hi u tìm đ ng đi t ế ậ ạ ườ ừ ỗ ọ ế ị ắ ch tr đ n đ a đi m thi là ng n ể

nh t.ấ

ữ ệ ồ

ứ ấ ố

ng K, U, V, L. Trong Input: D li u ghi trong file SCHOOL.INP g m: • Dòng th nh t ghi hai s nguyên N và M. • M dòng ti p theo, m i dòng ghi 4 s nguyên d ỗ ế ố ươ

đó:

K = 1 có nghĩa là có đ U đ n V v i đ dài L. ườ ng đi m t chi u t ộ ề ừ ớ ộ ế

K = 2 có nghĩa là có đ ng đi hai chi u gi a U và V v i đ dài L. ườ ớ ộ ữ ề

ồ Output: Ghi k t qu vào file SCHOOL.OUT g m hai s dòng là đ u g m ế ả ầ ồ ố

m t s là kho ng cách ng n nh t t ộ ố ấ ừ ỗ ứ ch Hi u tr đ n n i thi. Dòng th 2 ọ ế ế ả ắ ơ

ghi l n l ầ ượ t các đi m mà Hi u đi qua trên con đ ế ể ườ ng đ n đ a đi m thi. ị ế ể

Ví dụ

SCHOOL.OUT 4 1 → 2→ 3

SCHOOL.INP 3 2 1 1 2 3 2 2 3 1

• 1 ≤ N ≤ 100

• 1 ≤ M ≤ 500 • Đ dài các con đ

Gi i h n: ớ ạ

ng ≤ 32000 ộ ườ

H ng d n gi i thu t: ướ ẫ ả ậ

Bài toán yêu c u tìm đ ầ ườ ng đi ng n nh t t ắ ấ ừ ỗ ể ch Hi u tr đ n đ a đi m ọ ế ế ị

thi t ng ng v i bài toán tìm đ ng đi ng n nh t. Đ gi i quy t bài toán ươ ứ ớ ườ ể ả ắ ấ ế

này ta xây d ng m t th t c ự ặ ậ ộ ủ ụ Process cài đ t theo thu t toán Dijkstra trình

bày ng tr c v i 1 là đ nh xu t phát vì ch Hi u tr n m nút giao ch ở ươ ướ ớ ọ ằ ở ế ấ ỗ ỉ

thông 1.

D i đây là ch ng trình cài đ t trên ngôn ng pascal: ươ ữ ặ

const fo='SCHOOL.INP';

f1='SCHOOL.OUT';

Emax=32000;

var f,fw:text;

a:array[1..100,1..100] of integer;

b,d,pre:array[1..100] of integer;

n,m:integer;

procedure khoitao;

var i,j:byte;

k,l,u,v:integer;

begin

assign(f,fo);

ướ uses crt;

reset(f);

readln(f,n,m);

for i:=1 to n do

for j:=1 to n do

a[i,j]:=Emax;

for i:=1 to m do

begin

read(f,k,u,v,l);

if k=1 then

begin

a[v,u]:=Emax;

a[u,v]:=l;

end

else a[u,v]:=l;

end;

close(f);

end;

procedure Process;

var i,j,u,min,w,v,k:integer;

Truoc:array[1..100] of integer;

begin

assign(fw,f1);

rewrite(fw);

for i:=1 to n do

begin

b[i]:=0;

d[i]:=a[1,i];

pre[i]:=1;

end;

d[1]:=0; b[1]:=1;

k:=1;

while (k

begin

min:=Emax;

for i:=1 to n do

if (b[i]=0) and (min>d[i]) then

begin

min:=d[i];

u:=i;

end;

b[u]:=1; k:=k+1;

for v:= 1 to n do

if (b[v]=0) and (d[v]>d[u]+a[u,v]) then

begin

pre[v]:=u;

d[v]:= d[u] + a[u,v];

end;

Truoc[1]:=n; k:=2; w:=n;

while(n<>1) do

begin

Truoc[k]:=pre[n];

n:=pre[n];

k:=k+1;

end;

k:=k-1; Truoc[k]:=1;

writeln(fw,d[w]);

for i:= k downto 2 do write(fw,Truoc[i],' -> ');

write(fw,Truoc[1]);

close(fw);

end;

begin

clrscr;

khoitao;

process;

readln

end. 3.4. M t s bài toán v cây khung đ th ồ ị

ộ ố ề

3.4.1. Bài toán 1 - D ánự

ủ M t công ty l p m t d án m c đi n tho i cho n (n<100) nhân viên c a ệ ộ ự ậ ạ ắ ộ

mình b ng ằ m t l ộ ướ i các đo n n i t ạ ố ừ máy c a m t ng ủ ộ ườ ế ộ i đ n máy c a m t ủ

i khác (không ph i là hai ng i nào cũng đ s ng ố ườ ả ườ ượ ố ớ ự c n i v i nhau). D án

ph i đ m b o yêu c u sau (g i là yêu c u v tính thông su t c a m ng): Trên ầ ề ả ả ố ủ ả ầ ạ ọ

i đi n tho i đó m i nhân viên c a công ty đ u có th nh n tin cho b t c l ướ ể ắ ấ ứ ủ ệ ề ạ ỗ

m t nhân viên khác ho c tr c ti p ho c thông qua m t s nhân viên trung ộ ố ự ế ặ ặ ộ

gian. D li u v d án đ ữ ệ ề ự ượ ấ c ghi trong file văn b n có tên NETW.INP có c u ả

trúc nh sau: ư

- Dòng đ u tiên ch a hai s n, m t ng ng v i s máy và s đ ứ ầ ố ươ ớ ố ố ườ ng ứ

n i;ố

- Trong m dòng ti p theo ch a các đ ế ứ ườ ồ ng n i c a d án: m i dòng g m ố ủ ự ỗ

3 s nguyên theo th t là ch s c a hai máy đ ứ ự ố ỉ ố ủ ượ ố c n i và chi phí n i ố

hai máy này.

Hãy l p trình nh p d li u t file, sau đó: ậ ữ ệ ừ ậ

b) Ki m tra xem d án có đáp ng yêu c u v tính thông su t hay ứ ự ề ể ầ ố

không?

c) Trong tr ng h p d án đáp ng yêu c u thông su t, hãy tìm ườ ự ứ ầ ợ ố

cách lo i b m t s đ ạ ỏ ộ ố ườ ờ ng n i sao cho m ng v n là thông su t đ ng th i ẫ ố ồ ạ ố

i thi u chi phí n i m ng. gi m đ n m c t ế ứ ố ả ể ạ ố

K t qu đ a ra file văn b n có tên NETW.OUT n u d án không đáp ả ư ự ế ế ả

ứ ầ ng yêu c u v tính thông su t thì thông báo d án không đáp ng yêu c u, ự ứ ề ầ ố

ng i ghi l i thông tin các đ c l ượ ạ ạ ườ ng n i còn l ố ạ ủ ự ạ i c a d án sau khi đã lo i

b m t s đ ỏ ộ ố ườ ố ệ ủ ng n i sao cho m ng v n đáp ng yêu c u b ng s hi u c a ứ ạ ẫ ầ ằ ố

máy thu c đ ng đó trên m i dòng. ộ ườ ỗ

Ví d :ụ

NETW.OUT 3 2 4 3 1 4

NETW.INP 4 5 1 2 3 1 3 2 1 4 1 2 3 1 3 4 1

H ng d n gi i thu t: ướ ẫ ả ậ

Đ ki m tra d án có đáp ng yêu c u thông su t hay không t ể ể ứ ự ầ ố ươ ứ ng ng

v i vi c ki m tra đ th bao g m các máy là các đ nh và các đ ồ ớ ồ ị ệ ể ỉ ườ ữ ng n i gi a ố

hai máy i, j khác nhau là các c nh c a đ th t ng ng có liên thông hay ồ ị ươ ủ ạ ứ

không.

N u đ th liên thông t ng ng v i vi c d án đáp ng yêu c u thông ồ ị ế ươ ệ ự ứ ứ ầ ớ

su t thì vi c tìm cách lo i b m t s đ ạ ỏ ộ ố ườ ệ ố ng n i sao cho m ng v n là thông ạ ẫ ố

su t đ ng th i gi m đ n m c t i thi u chi phí n i m ng t ố ồ ứ ố ế ả ờ ể ạ ố ươ ớ ng ng v i ứ

vi c tìm cây khung nh nh t c a đ th . Vì v y đ gi i quy t bài toán này ấ ủ ồ ị ể ả ệ ậ ỏ ế

ta đi tìm cây khung nh nh t c a đ th t ng ng, n u không t n t i cây ấ ủ ồ ị ươ ỏ ồ ạ ứ ế

khung nh nh t thì đ th không liên thông và đ a ra k t qu là d án không ồ ị ư ự ế ấ ả ỏ

i đ a ra thông tin các đ c l đáp ng yêu c u thông su t, ng ầ ứ ố ượ ạ ư ườ ng n i sau ố

khi đã lo i b m t s đ ạ ỏ ộ ố ườ ng n i sao cho m ng v n đáp ng yêu c u chính ẫ ứ ạ ầ ố

là thông tin các c nh c a cây khung nh nh t. ủ ạ ấ ỏ

Th t c ướ ả i ki m tra và đ a k t qu ra file văn b n ế ư ể ả ủ ụ Process d

NETW.OUT, vi c cài đ t th t c này t ng t nh thu t toán Prim ủ ụ ệ ặ ươ ự ư ậ ở

procedure Process;

var i,j,k,min,u,t:integer;

begin

assign(fw,f1);

rewrite(fw);

for i:= 2 to n do

begin

b[i]:=0;

d[i]:=a[1,i];

pre[i]:=1;

end;

d[1]:=0; b[1]:=1;

u:=0; k:=1;

while (k<=n) do

begin

min:=Emax;

ch ng tr ươ ướ ể ể c đ ki m tra và tìm cây khung nh nh t c a đ th : ấ ủ ồ ị ỏ

for i:=1 to n do

if (b[i]=0) and (min>d[i]) then

begin

min:=d[i];

u:=i;

end;

if (min=Emax) and (k

else

begin

b[u]:=1; k:=k+1;

for i:=1 to n do

if (b[i]=0) and (d[i]>a[u,i]) then

begin

d[i]:=a[u,i];

pre[i]:=u;

end;

t:=0;

if (k

cau!')

else

begin

for i:=2 to n do

begin

writeln(fw,pre[i],' ',i);

t:=t+1;

end;

close(fw);

end; 3.4.2. Bài toán 2 - Thay h th ng [4]

ệ ố

ệ M t công ty c n thay toàn b h th ng dây đi n cho n phòng làm vi c. ộ ệ ố ệ ầ ộ

Cho bi t s đ m ng l i đi n hi n có c a n căn phòng này đ ế ơ ồ ạ ướ ủ ệ ệ ượ ể c bi u

ố di n b ng ma tr n A[i,j] trong đó A[i,j] chính là đ dài c a dây đi n n i ủ ệ ễ ậ ằ ộ

ữ li n hai phòng i, j (A[i,j] = A[j,i], A[i,j] = 0 n u không có dây đi n n i gi a ế ệ ề ố

phòng i và phòng j). Hãy l p trình tính đ dài c a dây d n c n s d ng sao ầ ử ụ ủ ậ ẫ ộ

ng này là ít nh t. cho c n phòng đ u có đi n và s l ề ố ượ ệ ả ấ

D li u: ữ ệ Cho trong file BLO.INP g m n+1 dòng ồ

- Dòng đ u ghi s n; ầ ố

- Dòng i+1 (1 ≤ i ≤ n) ghi n s A[i,1], A[i,2], A[i,3]…A[i,n], các s ghi ố ố

trên cùng m t dòng các nhau ít nh t m t d u cách. ộ ấ ấ ộ

K t qu : ả Xu t ra màn hình. ế ấ

Ví d :ụ

Ế

K T QU : Ả Tong do dai day dan can su dung: 3

BLO.INP 4 0 3 2 1 3 0 1 0 2 1 0 1 1 0 1 0

H ng d n gi i thu t: i d ng đ ướ ẫ ả ậ Ta th y bài toán có th bi u di n d ể ể ễ ấ ướ ạ ồ

th , t ị ươ ạ ng ng v i m i đ nh c a đ th chính là m t căn phòng và các c nh ủ ồ ị ỗ ỉ ứ ớ ộ

ng dây đi n n i gi a phòng i và c a đ th n i đ nh i v i đ nh j chính là đ ủ ồ ị ố ỉ ớ ỉ ườ ữ ệ ố

phòng j.

Vi c đ a ra đ dài c a dây d n c n s d ng sao cho c n phòng đ u có ầ ử ụ ệ ư ủ ề ẫ ả ộ

đi n và s l ng này là ít nh t t ng ng v i vi c xác đ nh t ng giá tr các ố ượ ệ ấ ươ ứ ệ ổ ớ ị ị

c nh c a cây khung nh nh t c a đ th t ạ ồ ị ươ ấ ủ ủ ỏ ng ng các đ nh là các căn ỉ ứ

phòng và tr ng s các c nh chính là đ dài dây đi n n i gi a hai căn phòng ộ ữ ệ ạ ố ọ ố

i, j v i nhau. ớ

Th t c i đây cài đ t theo thu t toán Prim ch ướ ậ ặ ở ươ ng ủ ụ Process d

tr ướ ư c đ a ra k t qu t ng giá tr các c nh c a cây khung nh nh t c a đ ạ ấ ủ ồ ả ổ ủ ế ỏ ị

th t ng ng m ng l i các phòng trong công ty chính là đ dài c a dây ị ươ ứ ạ ướ ủ ộ

ng này là ít d n c n s d ng sao cho c n phòng đ u có đi n và s l ả ẫ ử ụ ố ượ ề ệ ầ

nh t:ấ

procedure Process;

var i,j,k,min,u,t:integer;

begin

for i:= 2 to n do

begin

b[i]:=0;

d[i]:=a[1,i];

pre[i]:=1;

end;

d[1]:=0; b[1]:=1;

u:=0; k:=1;

while (k<=n) do

begin

min:=Emax;

for i:=1 to n do

if (b[i]=0) and (min>d[i]) then

begin

min:=d[i];

u:=i;

end;

if (min=Emax) and (k

else

begin

b[u]:=1; k:=k+1;

for i:=1 to n do

if (b[i]=0) and (d[i]>a[u,i]) then

begin

d[i]:=a[u,i];

pre[i]:=u;

end;

t:=0;

for i:=2 to n do t:=t+a[pre[i],i];

writeln('Tong do dai day dan can su dung: ',t);

end;

3.4.3. Bài toán 3 – Bão S n Tinh ơ

ng b Sau c n ơ bão S n ơ Tinh, m t s tuy n đ ộ ố ế ườ ng đ a ph ị ươ ị phá h y, đủ ể

ữ kh c ph c h u qu sau bão, c n ph i đ m b o giao thông thông su t gi a ả ả ụ ậ ả ắ ầ ả ố

ng. Ngành giao thông c n l p ra ph ng án xây d ng l i các các đ a ph ị ươ ầ ậ ươ ự ạ

ng sao cho chi phí ph i b ra là ít nh t. Có n đ a ph tuy n đ ế ườ ả ỏ ấ ị ươ ị ả ng b nh

h ng b i c n bão, chi phí v vi c kh c ph c tuy n đ ưở ề ệ ở ơ ụ ế ắ ườ ị ng gi a các đ a ữ

ph ng đ c cho tr c. ươ ượ ướ

Yêu c u: Hãy giúp ngành giao thông xác đ nh xem n đ a ph ng trên b ầ ị ị ươ ị

chia c t thành bao nhiêu mi n, và cho bi t ph i b ra ít nh t là bao nhiêu ề ắ ế ả ỏ ấ

ti n đ xây d ng l i các tuy n đ ự ể ề ạ ế ườ ố ng đ đ m b o giao thông thông su t ể ả ả

gi a n đ a ph ng. Trong đó ta hi u m i mi n là 1 t p h p các đ a ph ữ ị ươ ề ể ậ ỗ ợ ị ươ ng

mà trong đó có th đi l i thông su t gi a 2 đ a ph ể ạ ữ ố ị ươ ng b t kỳ. ấ

Input:

D li u trong file sontinh.inp g m n+1 dòng, dòng đ u ghi s ữ ệ ầ ồ ố n

i các tuy n đ xây d ng l ự ạ ế ườ ế ng. Trong đó n u a[i, j]=0 có nghĩa là g a tuy n ữ ế

đ ng gi a 2 đ a ph ườ ữ ị ươ ng i, j không c n s a ch a, n u a[i, j]>0 thì đó là s ữ ầ ử ế ố

chi phí ph i b ra đ xây d ng l i tuy n đ ng i, j. ả ỏ ự ể ạ ế ườ ng n i gi a 2 đ a ph ữ ố ị ươ

Output:

ắ Ghi vào file sontinh.out dòng đ u g m 2 s , s th 1 là s mi n chia c t, ồ ố ố ứ ề ầ ố

i thi u đ xây d ng l i các tuy n đ s th 2 là s ti n t ố ứ ố ề ố ự ể ể ạ ế ườ ả ng đ m b o ả

ủ giao thông thông su t. Các dòng ti p theo m i dòng ghi ch s 2 đ u c a ỉ ố ế ầ ố ỗ

các tuy n đ ng c n xây d ng l i. ế ườ ự ầ ạ

Ví dụ:

0 0 2 8

Sontinh.inp 4 Sontinh.out 2 2

0 0 5 0

2 5 0 7

8 0 7 0

1 3

H ng d n gi i ướ ẫ ả thu tậ : Ta th y yêu c u c a bài toán dòng đ u ghi hai ầ ủ ấ ầ

s , s th 1 là s mi n chia c t t ố ố ố ứ ắ ươ ề ề ng ng v i yêu c u ta đi tìm s mi n ầ ứ ớ ố

i thi u đ xây d ng l i các liên thông c a đ th , s th 2 là s ti n t ồ ị ố ứ ố ề ố ủ ự ể ể ạ

tuy n đ ế ườ ổ ng đ m b o giao thông thông su t chính là ta ph i đi tính t ng ả ả ả ố

giá tr các c nh trong cây khung nh nh t mà c nh đó bi u di n cho các ỏ ể ễ ạ ạ ấ ị

đo n đ ạ ườ ầ ử ng c n s a.

Các dòng ti p theo ghi ch s 2 đ u chính là 2 đ nh c a các c nh trong ỉ ố ủ ế ầ ạ ỉ

cây khung nh nh t mà các c nh này bi u di n cho các đo n c n s a l ầ ử ạ i. ể ễ ấ ạ ạ ỏ

Đ tính s mi n chia c t ta dùng phép duy t theo chi u sâu đ đ m s ể ế ề ệ ề ể ắ ố ố

ộ thành ph n liên thông c a đ th chính là s mi n chia c t. Ta s d ng m t ủ ồ ị ử ụ ề ầ ắ ố

m ng d[i,j] đ ghi l ng c n s a, đ bi c ch ể ả ạ ộ i đ dài nh ng đo n đ ữ ạ ườ ầ ử t đ ể ế ượ ỉ

ng c n s a thì ta ch c n ki m tra d[i, j] khác 0 hay s 2 đ u c a đo n đ ố ầ ủ ạ ườ ầ ử ỉ ầ ể

không. N u d[i, j]<>0 thì i, j chính là ch s 2 đ u c a đo n c n s a. ạ ầ ử ầ ủ ỉ ố ế

Ch ng trình d i đây đ ươ ướ ượ c cài đ t trên ngôn ng l p trình pascal, trong ữ ậ ặ

đó có th t c c cài đ t t ng t nh thu t toán prim đ ượ ặ ươ ự ư ậ ượ c ủ ụ process đ

trình bày ng tr c, bên c nh đó có ch a l i g i th t c ch ở ươ ướ ứ ờ ọ ạ ủ ụ DFS(i) để

đ m s mi n chia c t. ề ế ắ ố

uses crt;

const fo='sontinh.inp';

f1='sontinh.out';

var fr,fw:text;

n,k,dem,sum,min:integer;

a,d:array[1..71,1..71] of integer;

visited,b,c:array[1..71] of byte;

procedure khoitao;

var i,j:integer;

begin

Ch ng trình: ươ

assign(fr,fo);

reset(fr);

read(fr,n);

for i:=1 to n do

for j:=1 to n do

read(fr,a[i,j]);

for i:=1 to n do visited[i]:=1;

close(fr)

end;

procedure DFS(x:integer);

begin

visited[x]:=0;

for i:=1 to n do

if ((x<>i)and(a[x,i]=0)and(visited[i]=1)) then DFS(i);

end;

procedure process;

var i,j,x,y:integer;

begin

assign(fw,f1);

rewrite(fw);

for i:=1 to n do

if visited[i]<>0 then

begin

DFS(i);

dem:=dem+1;

end;

b[1]:=1; c[1]:=1;

while (k

begin

min:=1000;

k:=k+1;

for i:=1 to n do

if (b[i]=1) then

for j:=1 to n do

if (c[j]=0) then

if (min>a[i,j]) then

begin

min:=a[i,j];

x:=i;

y:=j;

end;

sum:=sum+min;

d[x,y]:=min;

b[y]:=1; c[y]:=1;

end;

writeln(fw,dem,' ',sum);

for i:=1 to n do

for j:=1 to n do

if d[i,j]<>0 then writeln(fw,i,' ',j);

close(fw);

end;

begin

clrscr;

khoitao;

process;

readln

end.

3.5. K t lu n ch ng 3 ế ậ ươ

Trong ch ng này chúng ta đã v n d ng lý thuy t và các thu t toán ươ ụ ế ậ ậ ở

các ch ng tr c nh các ph ng pháp duy t đ th , tìm ki m các thành ươ ướ ư ươ ệ ồ ị ế

ph n liên thông, đ ng đi ng n nh t trên đ th tr ng s …Đ gi i m t s ầ ườ ồ ị ọ ể ả ấ ắ ố ộ ố

bài toán trong ch ng trình tin h c ph thông, c th g m các bài toán v ươ ụ ể ồ ọ ổ ề

duy t đ th , các bài toán v đ ng đi trên đ th , bài toán v cây khung . ệ ồ ị ề ườ ồ ị ề

V n d ng các m t s thu t toán nh duy t đ th , thu t toán tìm đ ng đi ệ ồ ị ộ ố ư ụ ậ ậ ậ ườ

i quy t nh ng bài toán đó, v i m i d ng đ a ra m t s ng n nh t… Đ gi ấ ể ả ắ ữ ế ớ ỗ ạ ộ ố ư

bài toán và h i ướ ng d n gi ẫ ả c thụ ể.

K T LU N Ậ Ế

1. K t qu đã th c hi n ự ệ ế ả

Trong quá trình th c hi n đ tài em đã tìm hi u và th c hi n đ ệ ượ ự ự ệ ề ể ữ c nh ng

n i dung sau: ộ

Tìm hi u t ng quan m t s v n đ v lý thuy t đ th : Đ nh nghĩa và các ề ề ế ồ ị ộ ố ấ ể ổ ị

khái ni m c b n v Graph trong đó g m các khái ni m v b c c a đ nh, ề ậ ủ ơ ả ệ ề ệ ồ ỉ

ng đi, chu trình…Bên c nh đó tìm hi u và phân lo i Graph: Graph vô đ ườ ể ạ ạ

ng, Graph có h ng, Graph có tr ng s … h ướ ướ ọ ố

Tìm hi u và cài đ t m t s thu t toán trên Graph bao g m các bài toán: ộ ố ể ặ ậ ồ

Bi u di n đ th trên máy tính, bài toán duy t m t Graph, bài toán tìm đ ễ ồ ị ệ ể ộ ườ ng

đi và ki m tra tính liên thông c a Graph, bài toán v cây khung và cây khung ủ ề ể

v i giá tr c c ti u. ớ ị ự ể

Đ a ra m t s d ng bài toán v Graph, h ng d n v n d ng lý thuy t v ộ ố ạ ư ề ướ ẫ ậ ụ ế ề

Graph đ gi i quy t các bài toán đó. ể ả ế

2. H ng phát tri n ướ ể

ế Em s ti p t c nghiên c u, phát tri n đ tài và tìm hi u sâu h n lý thuy t ẽ ế ụ ứ ể ề ể ơ

i các d ng bài t p trong ch v Graph và ng d ng đ gi ứ ề ể ả ụ ạ ậ ươ ọ ng trình trung h c

ph thông. ổ

Cài đ t các bài toán v Graph theo h ề ặ ướ ng thu n ti n h n: T o các giao ơ ệ ậ ạ

di n b ng ng d ng trên Window Form đ ng ệ ằ ứ ể ườ ọ ắ ơ i đ c hi u và n m ch c h n ụ ể ắ

các thu t toán v Graph… ề ậ

ữ Do trình đ và th i gian còn h n ch nên đ tài không tránh kh i nh ng ế ề ạ ộ ờ ỏ

c s ch b o, giúp đ thi u sót c n b sung và s a ch a, em mong nh n đ ử ậ ượ ự ỉ ả ữ ế ầ ổ ỡ

c hoàn thi n h n. c a th y, cô và các b n đ đ tài đ ủ ạ ể ề ầ ượ ệ ơ

Em xin chân thành c m n! ả ơ

TÀI LI U THAM KH O Ả Ệ

[1] Vũ Đình Hòa, M t s ki n th c c s v Graph h u h n, ứ ơ ở ề ộ ố ế ữ ạ NXB Giáo

D c, 2000 ụ

[2] Nguy n Đ c Nghĩa - Nguy n Tô Thành, Toán r i r c ứ ễ ễ ạ ọ ờ ạ , NXB Đ i H c

Qu c Gia Hà N i, 2003 ố ộ

[3] Đ Xuân Lôi, C u trúc d li u và gi i thu t ỗ ữ ệ ấ ả ậ , NXB Đ i H c Qu c Gia ạ ọ ố

Hà N i, 2007 ộ

Ph ng pháp gi i các bài toán trong tin h c [4] Tr n Đ c Huyên, ứ ầ ươ ả ọ , NXB

Giáo D c, 1996 ụ

[5] Nguy n H u Ng , ự Lý thuy t đ th ế ồ ị, NXB Đ i H c Qu c Gia Hà N i ộ ạ ọ ữ ễ ố

[6] http://www.tailieu.vn, Lê Minh Hoàng, Gi i thu t & l p trình ả ậ ậ ạ ọ , Đ i h c

s ph m Hà N i, 2002 ư ạ ộ

[7] http://vi.scribd.com/doc/84311330/Chuyên-đ -đ -th -trong-l p-trình- ề ồ ị ậ

Pascal-FULL

Graph và một số ứng dụng trong chương trình THPT

M C L C

Ụ

Ụ

Vi Văn S nơ

.

end; *Th t c BFS(v) procedure BFS(v:integer);

end. 2.6. K t lu n ch

end; 3.3.2. Bài toán 2 - Du l ch [4]

Ế

Ả:

K T QU Chu trình HAMILTON 1 → 3 → 2 → 4 → 5 → 1

BROAD.INP 5 0 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0

SCHOOL.OUT 4 1 → 2→ 3

SCHOOL.INP 3 2 1 1 2 3 2 2 3 1

end. 3.4. M t s bài toán v cây khung đ th ồ ị

end; 3.4.2. Bài toán 2 - Thay h th ng [4]

Có thể bạn quan tâm

Tài liêu mới

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok

Graph và một số ứng dụng trong chương trình THPT

M C L C

Ụ

Ụ

Vi Văn S nơ

.

end; *Th t c BFS(v) procedure BFS(v:integer);

end. 2.6. K t lu n ch

end; 3.3.2. Bài toán 2 - Du l ch [4]

Ế

Ả:

K T QU Chu trình HAMILTON 1 → 3 → 2 → 4 → 5 → 1

BROAD.INP 5 0 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0

SCHOOL.OUT 4 1 → 2→ 3

SCHOOL.INP 3 2 1 1 2 3 2 2 3 1

end. 3.4. M t s bài toán v cây khung đ th ồ ị

end; 3.4.2. Bài toán 2 - Thay h th ng [4]

Có thể bạn quan tâm

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok