Bài tập và thực hành môn học Lý thuyết đồ thị

BÀI T P VÀ TH C HÀNH

Ự

Ậ

MÔN H CỌ

Lý thuy t đ th ế ồ ị

2009

MỤC LỤC

CH

NG 1: Đ I C

NG V Đ TH

ƯƠ

Ạ ƯƠ

Ề Ồ Ị ............................................................3

1Xét ví d th c t ụ ự ế.........................................................................................................................3

2Các thu t ng đ th ữ ồ ị..................................................................................................................4 ậ

3Bi u di n các đ th và s đ ng c u đ th ấ ồ ị ........................................................................5 ự ẳ ồ ị ể ễ

4Tính liên thông.............................................................................................................................6

Ồ Ị

NG 2: Đ TH EULER VÀ Đ TH HAMILTON NG

Ồ Ị

CH CH Đ TH CÓ TR NG S VÀ Đ

ƯƠ ƯƠ Ồ Ị

NG ĐI NG N NH T Ắ

...............................9 3 Ấ ..............................13

ƯỜ

Ọ

Ố

.........................................................................................................................................................14

CH

NG 4: CÂY

...............................................................................................17

ƯƠ

Vi t ti u lu n ế ể ậ ..............................................................................................................................24

Đ TÀI 1: ..............................................................................................................................24 Ề

Ị Ể ƯƠ Ồ Ố Ệ Ể Ị NG PHÁP Đ TH Đ TH HI N VI C B TRÍ L CH THI CHO S D NG PH Ệ Ử Ụ SINH VIÊN KHOA TOÁN – TIN H C. Ọ ...............................................................................24

Đ TÀI 2: ..............................................................................................................................25 Ề

NG PHÁP Đ TH Đ GI I BÀI TOÁN DÂN GIAN (BÀI TOÁN 1). . .25 S D NG PH Ử Ụ ƯƠ Ồ Ị Ể Ả

Đ TÀI 3: .............................................................................................................................25 Ề

NG PHÁP Đ TH Đ GI I BÀI TOÁN DÂN GIAN (BÀI TOÁN 2). . .25 S D NG PH Ử Ụ ƯƠ Ồ Ị Ể Ả

Đ TÀI 4: .............................................................................................................................26 Ề

CÁC THU T TOÁN TÌM Đ Ậ ƯỜ NG ĐI NG N NH T TRÊN Đ TH Ấ Ồ Ị................................26 Ắ

Đ TÀI 5: CÁC GI I THU T TÌM CÂY PH T I TI U Ề Ả Ủ Ố Ể .................................................27 Ậ

Đ TÀI 6: BÀI TOÁN T CH C THI CÔNG ....................................................................27 Ổ Ứ Ề

Đ TÀI 7: BÀI TOÁN QU N LÝ D ÁN Ự ............................................................................28 Ả Ề

Đ TÀI 8: BÀI TOÁN “8 QUÂN H U” Ậ ...............................................................................28 Ề

Đ TÀI 9: BÀI TOÁN “QUÂN MÃ ĐI TU N” Ầ ...................................................................29 Ề

Đ TÀI 10: ...........................................................................................................................30 Ề

BÀI TOÁN PHÂN B KÊNH TRUY N HÌNH T I ĐBSCL .................................................30 Ố Ạ Ề

DÙNG THU T TOÁN TÔ MÀU Đ TH Ồ Ị............................................................................30 Ậ

Đ TÀI 11: ...........................................................................................................................30 Ề

BÀI TOÁN PHÂN B KÊNH TRUY N HÌNH T I MI N ĐÔNG NAM B Ề Ố Ạ Ề Ộ......................30

DÙNG THU T TOÁN TÔ MÀU Đ TH Ồ Ị............................................................................30 Ậ

Đ TÀI 12: ...........................................................................................................................31 Ề

Ả Ự Ớ Ữ Ồ ƯỜ Ấ Ồ Ấ Ể NG L N TRONG N I XÂY D NG B N Đ TR C TUY N NH NG CON Đ Ộ Ế Ự Ể THÀNH TP.H CHÍ MINH V I VI C TÍNH CHI PHÍ TH P NH T Đ DI CHUY N Ớ Ệ Ậ ........................................................................................31 GI A TRUNG TÂM CÁC QU N. Ữ

Đ TÀI 13: ...........................................................................................................................32 Ề

Ự Ạ Ọ Ố Ủ XÂY D NG H TH NG K T N I M NG C A CÁC TR Ạ Ế Ố THÀNH PH V I CHI PHÍ TH P NH T NG Đ I H C TRONG ƯỜ Ấ .........................................................................32 Ệ Ố Ớ Ấ

Đ TÀI 14: BÀI TOÁN Đ NG ĐI NG I GIAO HÀNG ..............................................32 Ề ƯỜ ƯỜ

Đ TÀI 15: BÀI TOÁN Đ NG ĐI NG I Đ A TH Ề ƯỜ ƯỜ Ư Ư.................................................33

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ự

CH

NG 1

: Đ I C

ƯƠ

Ạ ƯƠ

NG V Đ TH Ề Ồ Ị

1 Xét ví d th c t

ụ ự ế

ng bay và nói

ẽ

ớ

ợ

ườ

Bài 1.1. V i m i tr rõ v lo i đ th đ

ng h p sau, v các mô hình đ th bi u di n các đ ễ c dùng. Trong đó l ch bay m i ngày nh sau:

ỗ ườ ề ạ ồ ị ượ

ồ ị ể ư

ỗ

ị

ừ

ế

ộ

- T TP.HCM: có m t chuy n đ n Hà N i, m t chuy n đ n Đà N ng, m t chuy n đ n ế ế ẵ Phú Qu c, m t chuy n đ n Ngh An, m t chuy n đ n H i Phòng; ệ

ế ế

ế ả

ộ ế

ộ ộ

ế

ộ

ố

ế

ẵ

ộ

- T Hà N i: có hai chuy n đ n TP.HCM, m t chuy n đ n Đà N ng, m t chuy n đ n ế Ngh An, m t chuy n đ n H i Phòng; ế

ừ ệ

ế ế

ế ả

ộ

ừ

ế

ả

ẵ

ộ

ộ - T Đà N ng: có m t chuy n đ n H i Phòng, hai chuy n bay đ n TP.HCM; m t chuy n đ n Hà N i;

ế ế

ộ

- T Ngh An: có m t chuy n đ n Hà N i, m t chuy n đ n TP.HCM;

ừ

ệ

ế

ộ

ừ ả

ế

ộ

ế - T H i Phòng: có m t chuy n đ n Hà N i, m t chuy n đ n TP.HCM, và m t chuy n ộ đ n Đà N ng; ế

ẵ

- T Phú Qu c: có m t chuy n đ n TP.HCM.

ừ

ế

ố

ộ

a) Đ th bi u di n các thành ph có chuy n bay gi a chúng.

ồ ị ể

ữ

ễ

ế

ố

ồ ị ể

ữ

t ng m c nh thành ph , c t và h cánh t

ớ ộ i Phú Qu c.

b) Đ th bi u di n s chuy n bay ho t đ ng gi a các thành ph , c ng v i m t khuyên ế bi u th chuy n du l ch đ c bi ế

ố ộ ạ

ễ ố ị

ạ ộ ả

ố ấ

ệ

ể

ắ

ạ

ặ

ố

ị

ồ ị ể

ủ

ễ

ề ướ

ng bay và s chuy n bay gi a các thành ế

ữ

ố

c) Đ th bi u di n đ y đ thông tin v h ầ ph .ố

Ph n h

ng d n

ầ ướ

ẫ

a) Đ th vô h ồ ị

ướ

H i Phòng Đà N ngẵ ả

TP. HCM Hà N iộ

b) Đa đ th vô h ồ ị

ướ

Phú Qu cố Ngh Anệ

H i Phòng Đà N ngẵ ả

TP. HCM Hà N iộ

c) Đa đ th có h ồ ị

ướ

Phú Qu cố Ngh Anệ

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ự

H i Phòng Đà N ngẵ ả

TP. HCM Hà N iộ

Phú Qu cố Ngh Anệ

Bài 1.2. Xác đ nh xem đ th nào sau đây là đ th đ n, đa đ th , đ th có h

ng.

ồ ị ồ ị

ồ ị ơ

ồ ị

ị

ướ

ậ

ấ

ộ

ắ ộ ồ ị

ộ ế

ả

ằ

ắ

ộ

c) d)

ộ Bài 1.3. Trong tr n đ u vòng tròn, đ i H th ng đ i G, đ i C, và đ i A; đ i G th ng đ i ắ A và đ i C; đ i C th ng đ i A. Hãy mô hình hóa k t qu này b ng m t đ th có ộ ng…ướ h

2 Các thu t ng đ th ữ ồ ị ậ

ng các đ nh,

ượ

ị

ỉ

treo.

Bài 2.1. Xác đ nh ồ ị sau. Cho bi đ th

s l ạ ố ượ t đ nh nào là đ nh cô l p, đ nh nào là ế ỉ

ng các c nh, và b c c a các đ nh trong các ậ ủ ỉ

s ố l ậ

đ nh ỉ

ỉ

c b b a a

e f e d d c

a) b)

a d b c

i e h g f c)

ồ ị ở

ổ

ứ các Bài 2.1, và ki m ch ng

ể

ự

ậ ủ ạ

ầ ố

ằ

ể ồ ạ

ạ i m t đ th đ n có 15 đ nh, m i đ nh có b c b ng 5 không? T i ỗ ỉ

ộ ồ ị ơ

ậ ằ

ỉ

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị Bài 2.2. Tìm t ng các b c c a các đ nh trong các đ th ỉ r ng nó b ng hai l n s các c nh trong đ th . ồ ị ằ

Bài 2.3. Có th t n t sao?

i đ u b t tay nhau. Ch ng t

r ng t ng s

ộ

ổ

ỏ ằ

ổ

ố

ọ c b t tay là m t s ch n. Gi

ứ b t tay mình.

i đ

Bài 2.4. Trong m t bu i chiêu đãi, m i ng ng ả ử

ườ ượ ắ

ộ ố ẵ

ắ ườ ề s không ai t ự ắ

ị

ố ậ vào và s ố b c ra c a m i đ nh đ i

ỗ ỉ

ố v i đ

ớ ồ thị

ủ

ậ

Bài 2.5. Xác đ nh có h

ng sau.

ướ

s đ nh, s c nh, s b c ố ạ ố ỉ a

ủ ồ ị

ậ

ổ

ỉ

d c

Bài 2.6. Hãy xác đ nh t ng các b c vào và t ng các b c ra các đ nh c a đ th trong bài ổ 2.5 m t cách tr c ti p. Ch ng t

ậ r ng chúng đ u b ng t ng các c nh c a đ th . ủ ồ ị ổ ỏ ằ

ị ự ế

ề ằ

ứ

ạ

ộ

ẽ ộ ồ ị

ồ ị ẽ

ế

ậ

ạ

ỉ

Bài 2.7. Đ th s có bao nhiêu c nh n u nó có các đ nh b c 4, 3, 3, 2, 2. V m t đ th nh v y. ư ậ

i đ th đ n ch a năm đ nh v i các b c sau đây? N u có hãy v đ th

ồ ạ ồ ị ơ

ẽ ồ ị

ứ

ế

ậ

ớ

ỉ

Bài 2.8. Có t n t đó.

a) 3, 3, 3, 3, 2.

b) 1, 2, 3, 4, 5.

c) 1, 2, 3, 4, 4.

a b

Bài 2.9. V t

t c các đ th con c a đ th sau.

ẽ ấ ả

ủ ồ ị

ồ ị

d c

Bài 2.10. Tìm h p c a các c p đ th ợ ủ

ồ ị đ n sau ơ

ặ

f a b a a b

f b b f e e

e c d c c g d d a) d b)

ể

ự ẳ

ễ

3 Bi u di n các đ th và s đ ng c u đ th ấ ồ ị ồ ị Bài 3.1. Dùng danh sách k bi u di n các đ th sau.

ề ể

ồ ị

ễ

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ự

b a a b

c d d c a) b)

Bài 3.2. Bi u di n các đ th trong bài 3.1 b ng ma tr n k . ậ ề

ồ ị

ễ

ể

ằ

Bài 3.3. V các

c cho nh sau.

ẽ

đ th ng v i ma tr n k đ ớ ồ ị ứ

ậ ề ượ

0 1 0 � � 1 0 1 � 0 1 0 � � � � � � � 0 0 1 1 � � 0 0 1 0 � 1 1 0 1 � � 1 1 1 0 � � � � � � � 1 1 1 0 � � 0 0 1 0 � 1 0 1 0 � � 1 1 1 0 � � � � � � �

Bài 3.4. Dùng ma tr n liên k t đ bi u di n các đ th trong Bài 3.1.

ế ể ể

ồ ị

ễ

ậ

Bài 3.5. Xác đ nh xem các c p ị

ặ đ thồ ị đã cho có là đ ng c u không.

ẳ

ấ

v v

u u u u u v

a) v v

4 Tính liên thông

ườ

ạ

i hay ướ ng đi này

ng đi trong đ th bên d ồ ị ườ ủ

ườ

ộ

Bài 4.1. Các danh sách đ nh sau đây có t o nên đ ỉ không? Đ ng đi nào là đ n?ơ Đ ng đi nào là chu trình? Đ dài c a các đ ườ là bao nhiêu?

a) (a, e, b, c, b)

b) (a, e, a, d, b, c, a)

c) (e, b, a, d, b, e)

d) (c, b, d, a, e, c)

ườ

ạ

i hay ướ ng đi này

ng đi trong đ th bên d ồ ị ườ ủ

ườ

ộ

ự

a) (a, b, e, c, b)

b) (a, d, a, d, a)

c) (a, d, b, e, a)

d) (a, b, e, c, b, d, a)

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị Bài 4.2. Các danh sách đ nh sau đây có t o nên đ ỉ không? Đ ng đi nào là đ n? Đ ng đi nào là chu trình? Đ dài c a các đ ơ ườ là bao nhiêu?

Bài 4.3. Xác đ nh

liên thông không.

ị

xem các đ th đã cho có ồ ị

các Bài t p 4.3? Tìm các

ồ ị ở

ậ

Bài 4.4. Có bao nhiêu thành ph n liên thông trong các đ th ầ thành ph n liên thông đó.

ầ

Bài 4.5. Tìm t

t ấ c các đ nh c t và c nh c t c a ắ

ắ ủ đ th . ồ ị

ạ

ả

ỉ

Bài th c hành s 1: Bi u di n đ th ễ ồ ị

ố

ể

ự Bài t p 1: ậ

bàn phím và đ c t t p tin). Nh p vào ma tr n k c a m t đ n đ th (t ề ủ ồ ị ừ ộ ơ ậ ậ ọ ừ ậ

c a đ th (giá tr trên đ ng chéo chính đ u b ng 0). ị ườ ề ằ ữ ướ matranke.txt ng? ng hay h u h bàn phím thì xu t ra thành t p tin ấ ậ c đ c t ể ậ t c các đ nh c a đ th (s c nh n i t ố ớ ỉ t c các thành ph n liên thông n u có. a. Ki m tra tính h p l ợ ệ ủ ồ ị b. Ki m tra xem đ th là vô h ướ ồ ị c. N u ma tr n k đ c nh p t ậ ậ ừ ề ượ d. N u ma tr n đ t p tin thì xu t k t qu ma tr n ra màn hình hi n th . ậ ượ ọ ừ ậ ị e. Xu t ra b c c a t ỉ ậ ủ ấ ả f. Ki m tra tính liên thông c a đ th ? Xu t ra t ủ ồ ị ả ấ ế ủ ồ ị ố ạ ấ ả ể ể ế ế ấ ể i đ nh). ầ ế ấ

Bài t p 2: ậ

Nh p vào ma tr n tr ng s c a m t đ n đ th (t bàn phím và đ c t t p tin). ồ ị ừ ộ ơ ố ủ ậ ậ ọ ọ ừ ậ

c a đ th (giá tr trên đ ng chéo chính đ u b ng 0). ườ ề ằ ị ữ ướ trongso.txt ng? ng hay h u h bàn phím thì xu t ra thành t p tin ấ ậ ể ả ậ a. Ki m tra tính h p l ợ ệ ủ ồ ị b. Ki m tra xem đ th là vô h ướ ồ ị c nh p t c. N u ma tr n k đ ậ ừ ề ượ ậ c đ c t d. N u ma tr n đ t p tin thì xu t k t qu ma tr n ra màn hình hi n th . ậ ượ ọ ừ ậ ị e. Xu t ra c nh có tr ng s nh nh t và l n nh t. ỏ ố ọ ạ ể ể ế ế ấ ấ ế ớ ấ ấ

H ng d n: ướ ẫ

Ch ng trình nh p vào ma tr n k c a đ th t bàn phím ươ ề ủ ồ ị ừ ậ ậ

#include

ự Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị main()

{

int n,m,i,j;

int a[100][100];

// Doc n, m tu ban phim

printf(" Nhap n, m ");

scanf("%d %d",&n,&m);

// Doc mang a kich thuoc n*m

for (i=0;i

for (j=0;j

{

printf(" Nhap a[%d][%d]: " ,i,j);

scanf("%d",&a[i][j]);

}

// Xuat mang a ra man hinh

for (i=0;i

{

for (j=0;j

{

fprintf(f,"%3d",a[i][j]);

}

fprintf(f,"\n");

}

getch();

}

Ch ng trình đ c vào ma tr n k c a đ th t t p tin. ươ ề ủ ồ ị ừ ậ ọ ậ

#include

main()

{

int n,m,i,j;

int b[100][100];

FILE* f;

// Doc file D:\matranke.txt

f = fopen("D:\\matranke.txt","rt");

fscanf(f,"%d%d",&n,&m);

for (i=0;i

{

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ự for (j=0;j

{

fscanf(f,"%d",&b[i][j]);

}

fclose(f);

// In mang b

printf(" Mang B co n:%d m:%d\n",n,m);

for (i=0;i

{

for (j=0;j

{

printf("%3d",b[i][j]);

}

printf("\n");

}

getch();

}

CH

NG 2: Đ TH EULER VÀ Đ TH HAMILTON

ƯƠ

Ồ Ị

i chu trình Euler trong các

ồ ạ

ị

đ ồ th sau hay không. V

ẽ chu

ị

Bài 1. Xác đ nh xem có t n t trình đó khi nó t n t

ồ ạ

ng đi Euler không. V các đ

ng đi

ồ ị

ị

ườ

ẽ

ườ

Bài 2. Xác đ nh xem các đ th trong Bài 5.1 có đ đó n u có. ế

ể ẽ

ứ

ề

ấ

ằ

ộ

Bài 3. Xác đ nh xem có th v các b c tranh sau b ng m t nét li n, không nh c bút lên kh i m t gi y không?

ị ấ

ặ

ỏ

i chu trình Euler trong các đ th

ng sau. V

ị

ạ

ồ ị có h

ướ

ẽ các chu trình

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ự

s ự t n ồ t Bài 4. Xác đ nh i.ạ ồ t này n u chúng t n

ế

ng trong Bài 5.4 có đ

ng đi Euler hay không. V các

ị

ướ

ườ

ẽ

Bài 5.Xác đ nh xem đ th có h ồ ị ng đi Euler này n u có. đ ế ườ

ộ đ ồ th đã cho có ch a chu trình Hamilton hay không. N u có hãy tìm m t

ứ

Bài 6. Xác đ nh chu trình nh th . N u không có hãy gi

i thích

lý do vì sao không t n t

ị ị ư ế ế

ả

ế ồ ạ

ng đi Hamilton không? N u có, hãy tìm đ

ế

ườ

ế ng đó. N u

t lý do t

i sao không t n t

i m t đ

ng đi nh v y.

ế

ạ

ồ ạ

ộ ườ

ư ậ

ự ồ ị Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị Bài 7 Đ th trong Bài 5.6 có đ ườ không có, cho bi

Bài th c hành s 2: Duy t đ th ệ ồ ị ố

ự Bài t p 1: ậ

ệ ở ặ t p tin ậ matranke.txt, ch ớ ồ ị ượ ng trình cho phép nh p vào đ nh xu t phát và hi n th k t qu ỉ c cho b i ma tr n k đ c ề ọ ả ề ộ ậ ậ ị ế ươ ể ấ Cài đ t thu t toán duy t theo chi u sâu và chi u r ng v i đ th đ ề t ừ ậ duy t.ệ

Bài t p 2: ậ

ng đi t ủ ồ ị ể ậ ỉ ườ ừ Cài đ t ch ặ x t ươ i y (và ng i) hay không? ớ ng trình cho phép nh p vào 2 đ nh x và y c a đ th , ki m tra xem có đ c l ượ ạ

H ng d n:

ướ

ẫ

4.1.1 Duy t đ th theo chi u sâu (thu t toán DFS) ệ ồ ị ề ậ

Ý t ng chính c a thu t toán có th trình bày nh sau: ậ ể ư

0 nào đó c a đ th .

m t đ nh v ẽ ắ ầ ừ ộ ỉ c duy t. ủ ồ ị ư ượ ệ ặ ạ c đ nh u n a. ưở ủ • Ta s b t đ u tìm ki m t ế • Sau đó ch n u là m t đ nh tuỳ ý k v i v ọ ộ ỉ • L p l ố ớ • Quá trình đ quy k t thúc khi không ch n đ ế ề ớ 0 và ch a đ i quá trình đ i v i u. Đây là th t c đ quy. ủ ụ ệ ọ ượ ỉ ệ ữ

Th t c đ quy đ c vi ủ ụ ệ ượ ế t nh sau: ư

Th t c DFS(v); Duy t toàn b đ th theo chi u sâu: ủ ụ ộ ồ ị ệ ề

(*tim kiem theo chieu sau bat dau tu dinh v; cac bien Chuaxet, Ke la bien toan cuc*) B t đ u ắ ầ B t đ u ắ ầ for v thu c V do Chuaxet[v]:=true; ộ Tham_dinh(v); for v thu c V do ộ Chuaxet[v]:=false; if Chuaxet[v] then DFS(v); For u là Ke(v) do K t thúc ế If Chuaxet[u] then DFS(u);

K t thúc (*dinh v da duyet xong*) ế Đ ph c t p là : O(n+m) ộ ứ ạ

4.1.2 Duy t đ th theo chi u r ng (thu t toán BFS) ệ ồ ị ề ộ ậ

Ý t ư ủ ng chính c a thu t toán nh sau: ậ

c duy t. ử ụ ữ ệ ỉ ầ ư ỉ ệ ế t v i đ nh đó. ưở • S d ng 1 hàng đ i đ l u tr các đ nh s đ ẽ ượ ợ ể ư • Ban đ u đ a đ nh b t đ u duy t u vào hàng đ i. ợ ắ ầ • Th c hi n quá trình l p cho đ n khi hàng đ i r ng. M i b ợ ỗ ặ ệ ỏ ệ ấ ự ỉ c l p làm nh sau: ư ỗ ướ ặ ế ớ ỉ ệ ầ ợ ề ớ ỉ ư ệ ị ư ỉ ự o L y 1 đ nh v ra kh i hàng đ i. Th c hi n các công vi c c n thi o Xác đ nh các đ nh w k v i đ nh v mà ch a duy t. ỉ o Đ a các đ nh w này vào hàng đ i. ợ

Th t c đ c vi ủ ụ ượ ế t nh sau: ư

Th t c BFS(u); Duy t toàn b đ th theo thu t toán BFS: ủ ụ ộ ồ ị ệ ậ

(*Tim kiem theo chieu rong bat dau tu dinh u,

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ự

cac bien Chuaxet, Ke la bien cuc bo*) B t đ u ắ ầ

(*kh i t o ban đ u *) B t đ u ắ ầ ở ạ ầ

QUEUE:= Ø; for m i k thu c V do ọ ộ

Chuaxet[k]:=true; QUEUE  u; (* nap u vao QUEUE*)

for u thu V do ộ Chuaxet[v]:=false;

if Chuaxet[u] then BFS(v); While QUEUE ≠ Ø do

K t thúc ế Begin

v  QUEUE:; (*lay p tu QUEUE:*)

Thu t toán BFS có đ ph c t p: O(n+m) ộ ứ ạ ậ Tham_dinh(v);

For w là Ke(v) do

If Chuaxet[w] them

Begin

QUEUE  w;

Chuaxet[w]:=false;

End;

K t thúc ế

4.1.3 Ứ ng d ng c a thu t toán duy t ệ ụ ủ ậ

ng c a thu t toán duy t là xu t phát t 1 đ nh u, và đi thăm các đ nh v còn l ấ ỉ ỉ ạ i ệ ng đi t ừ đ nh u đ n v. t Ta th y, t ư ưở ấ trong đ th n u nh t n t ồ ị ế ậ ủ i 1 đ ư ồ ạ ế ừ ỉ ườ

i quy t đ c ẽ ả ể ượ 2 bài toán nh sau: ư

ườ ữ ỉ Nh v y ta s gi ư ậ • Tìm 1 đ • Ki m tra tính liên thông c a đ th và tìm các thành ph n liên thông trong đ th . ồ ị ể ng đi gi a 2 đ nh b t kỳ. ấ ủ ồ ị ầ

c 1 đ , ta c n ph i làm nh sau: Đ ể xác đ nh đ ị ỉ ườ ượ ừ ỉ ư ầ ả

ệ ủ ụ ế ạ ng đi t đ nh u đ n đ nh v ế • Dùng th t c duy t theo chi u sâu v i đ nh u. ớ ỉ • Trong quá trình duy t có s d ng m ng các bi n tr ng thái Chuaxet[k] (hay Free[k]) ả ệ ư ượ đ nh t ề ử ụ c duy t ch a. ệ ả ế ư ữ ế ừ ỉ đ ki m tra đ nh k đã đ ỉ ể ể • Đ xác đ nh đ ng đi ta dùng m ng bi n l u tr v t Truoc[k] = t, có nghĩa là t ườ ể s chuy n đ n đ nh k. ỉ ế ẽ ị ể

B sung vào các th t c DFS và BFS nh sau: ủ ụ ư ổ

Đ i v i DFS b sung code nh sau: Đ i v i BFS b sung code nh sau: ố ớ ư ổ ố ớ ư ổ

If Chuaxet[u] then If Chuaxet [u] then

Begin Begin

Truoc[u]:= v; QUEUE  u;

Chuaxet[u] = false; Chuaxet[u]:= false;

DFS(u); Truoc[u]:= p;

End; End;

ng đi t u đ n v nh sau: Xác đ nh đ ị ườ ừ ư ế

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ự

While (v ≠ u) do

Begin

In giá tr v ra ngoài màn hình; ị

v = Truoc[v] ; // gán v b ng đ nh mà t ằ ỉ ừ nó nh y đ n v hi n t ế i ệ ạ ả

End;

In giá tr u ra màn hình; ị

ế ế ồ ị thì ta dùng thêm 1 bi n count đ đ m. ế ị Đ ể xác đ nh s thành ph n liên thông trong đ th ầ Khi đó các b ư ố c ph i làm nh sau: ướ

ả ế ở ạ ớ ọ ỉ ư ượ c duy t thì: ệ ị ủ ị t, và count = 0. ư ỉ ơ ệ ố ớ ỉ ự

i thì giá tr ệ ả ế ồ ị ế ườ ng h p còn l ợ ạ ị ả • Kh i t o các m ng bi n c n thi ế ầ • Xét v i m i đ nh u trong đ th , n u nh đ nh u ch a đ ồ ị ế o Tăng giá tr c a bi n count lên 1 đ n v ế o Th c hi n các thu t toán duy t đ i v i đ nh u. ậ • N u k t qu bi n count = 1 thì đ th liên thông. Trong tr ế c a count chính là s thành ph n liên thông c a đ th . ủ ồ ị ủ ầ ố

Vi ế t thêm code đ xác đ nh s thành ph n liên thông: ố ể ầ ị

Count :=0; Count :=0;

If Chuaxet[u] then If Chuaxet[u] then

Begin Begin

Count := Coutn + 1; Count := Coutn + 1;

DFS(u); BFS(u);

End; End;

NG 3

CH Đ TH CÓ TR NG S VÀ Đ

ƯƠ Ồ Ị

Ọ

Ố

ƯỜ

NG ĐI NG N NH T Ắ

Ấ

ề

ủ ườ

đi ng n nh ắ

ất gi a a ữ

và z trong đ ồ th có tr ng

ọ

ị

s sauố

Bài 1. Tìm chi u dài c a đ đây

ắ

ộ ữ

ườ ỉ

ủ ặ

ấ

ọ

ng đi Bài 2. Tìm đ dài c a đ ng n nh t gi a các c p đ nh sau đây trong các đ th có tr ng s ố ở ồ ị Bài 6.1.

b) a và f

c) c và

a) a và d f

d) b và z

ộ

Bài 3. Tìm đ dài đ nh t t

ườ đ nh A đ n t ế ấ

ấ ừ ỉ

ắ ng đi ng n t các đ nh ỉ

còn l

i trong các đ th sau:

ạ

ồ ị

đ nh A đ n t

i trong các đ th

ộ

ườ

ng đi ng n nh t t ắ

ấ ừ ỉ

ế ấ

t các đ nh còn l ỉ

ạ

ồ ị

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ự

Bài 4. Tìm đ dài đ sau:

i đây. Hãy tìm đ

đ nh A

ố ư

ồ ị

ọ

ướ

ườ

ng đi ng n nh t t ắ

ấ ừ ỉ

Bài 5. Cho đ th có tr ng s nh hình d đ n đ nh N. ỉ ế

Bài th c hành s 3:

ự

ố

Bài t p: ậ

trongso.txt, ch t p tin c cho b i ma tr n ậ ở ị ng trình cho phép nh p vào đ nh xu t phát và hi n th ấ ớ ồ ị ượ ỉ ậ ươ ể Cài đ t thu t toán Ford-Bellman, Dijkstra, Floyd- Warshall v i đ th đ ậ ặ tr ng s đ c t ố ọ ừ ậ ọ k t qu duy t. ệ ả ế

H ng d n: ướ ẫ

4.1.1 Thu t toán tìm đ ậ ườ ng đi ng n nh t Ford-Bellman ấ ắ

ự t c các đ m t đ nh u cho ậ ấ ả ườ ng đi ng n nh t t ắ ấ ừ ộ ỉ Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị xác đ nh t Thu t toán này Ford-Bellman ị ạ trong đ th . i tr ồ ị c đ n các đ nh v còn l ỉ ướ ế

T t ng thu t toán nh sau: ư ưở ư ậ

đ nh u đ n đ nh v. Ban đ u ch • S d ng m ng D[v] là giá tr kho ng cách bé nh t đi t ỉ ỉ ả ầ ả ế ử ụ có D[u] = 0, còn t ấ ừ ỉ i đ u có D[v] = ∞. • Đ t ầ ể ị đây A[k][v] chính là i v i t ng kho ng cách D[k] và A[k][v]. L u ý ở ả ư v). ọ • Nh v y v i m i đ nh trung gian k ta c n ph i t i. H n n a ta có ị t c các đ nh v còn l ạ ề ỉ ấ ả i u các giá tr D[v] thì ta c n ch n các đ nh trung gian k, đ sau đó so sánh giá tr ỉ ọ ị ể ố ư D[v] hi n t ệ ạ ớ ổ tr ng s trên c nh (k ạ ố ỗ ỉ ớ ư ậ ả ố ư ơ ữ ầ ạ ỉ n cách ch n giá tr c a k. Nh v y ta có 2 vòng l p l ng nhau. ư ậ ị ủ ọ th i đi m T1, chúng ta dùng đ nh k1 là đ nh trung gian, và t s i u (n-1) đ nh còn l ặ ồ ỉ ể ỉ ể ờ ọ ỉ c giá tr t i u đ ố ư ượ i có th t ạ ộ ọ ỉ ị c giá tr ể ố ư i u c ch n làm trung gian ụ ọ ỗ ỉ ượ ế ạ ầ ả ơ ể ạ ặ ằ c c a vòng l p ngoài cùng ta ki m tra xem các i u và không thay đ i n a thì ta s • Tuy nhiên đ hi u qu h n, t ổ ổ ữ ố ư ẽ • Gi ả ử ở ờ t i đ nh k2. Đ n th i đi m T2 , chúng ta ch n k2 là đ nh trung gian thì l ạ ỉ ế i đ nh k1. Nh v y vi c ch n 1 đ nh là trung gian ph thu c vào (n-1) đ ư ậ ượ ị ạ ỉ ệ i.Đ vét h t các kh năng, ta cũng cho m i đ nh đ đ nh còn l ả ể ỉ (n-1) l n. Nh v y ta có vòng l p th 3 n m ngoài 2 vòng l p trên. ặ ứ ặ ư ậ i m i b ể ệ ỉ ng trình. ỗ ướ ủ i các đ nh có thay đ i không,n u đã t ế ươ giá tr t ị ạ d ng ch ừ

V c b n thu t toán mô t nh sau: ề ơ ả ậ ả ư

Procedure Ford_Bellman (u)

Begin

for i:=1 to n-1 do // s l n ch n m t đ nh làm trung gian ố ầ ộ ỉ ọ

for k thu c V\{u} do // ch n 1 đ nh là trung gian ọ ộ ỉ

for v thu c V do // t i u v i t ộ ố ư ớ ấ ả t c các đ nh còn l ỉ i ạ

if d[v] > d[k] +a[k][v] then // n u đk t i u x y ra ế ố ư ả

begin

d[v]:=d[k]+a[k][v]; // gán giá tr t ị ố ư i u m i ớ

Truoc[v]:= k; // l u l i v t di chuy n. ư ạ ế ể

end;

End;

M t s chú ý: ộ ố

• Thu t toán trên làm vi c v i đ th có tr ng s không âm,ho c không có chu trình mà ọ ệ ớ ồ ị ặ ậ ố t ng tr ng s là âm. ổ ọ ố

3).

Thu t toán trên làm vi c v i ma tr n k s có đ ph c t p là O(n ộ ứ ạ ệ ớ ề ẽ ậ ậ

ng đi ng n nh t Dijkstra 4.1.2 Thu t toán tìm đ ậ ườ ấ ắ

Thu t toán này ng đi ng n nh t gi a 2 đ nh c th t u đ n v ậ xác đ nh đ ị ườ ụ ể ừ ấ ữ ắ ỉ ế .

ự Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ng c a thu t toán nh sau: T t ư ưở ư ủ ậ

c duy t. Cách đ n gi n nh t phân bi ỉ ữ ượ ộ ậ ấ ả ệ ữ t gi a ư ệ ả ơ ạ ệ ế u đ n k. Ban đ u ta ả • Dùng m t t p S l u tr các đ nh đã đ ư ệ ớ ỉ ụ đ nh đã duy t v i đ nh ch a duy t là dùng m ng bi n tr ng thái Free[k]. ỉ ế ị ừ ắ ả ấ ị ầ ch gán D[u] = 0 và D[k] = ∞ v i v ≠ u. • B t đ u quá trình duy t các đ nh k khác u và quá trình l p ch k t thúc khi : ỉ ắ ầ ỉ ế ệ ặ ạ ế c n a. ể • Dùng m ng ph D[k] xác đ nh giá tr kho ng cách ng n nh t đi t ớ ỉ o Đã đ t đ n đ nh đích v . ỉ o Ho c không th duy t ti p đ ặ c c a quá trình duy t nh sau: • M i b ệ ế ượ ữ ệ ư c duy t, sao cho D[k] là bé nh t. ố ệ ỉ ấ ỗ ướ ủ ị ư ượ ế ặ ỉ ỉ c ch n chính là đ nh đích v ta k t thúc vòng l p. ượ c ch n là ∞ (t c là không ch n thêm đ ứ ị ượ ọ ọ ượ ữ ế c n a) ta cũng k t o Xác đ nh đ nh k trong s các đ nh ch a đ o N u k đ ế ọ o N u giá tr D[k] đ ế thúc vòng l p.ặ ư ạ ậ

i u các ố ư  D[t] = D[k] + ườ ạ ng h p còn l ợ i theo nguyên t c sau: n u D[t] > D[k] + A[k][t] ế i, ta đ a k vào t p S (gán Free[k] = 0) và t ắ o Trong tr đ nh còn l ỉ A[k][t];

Thu t toán đ c mô t nh sau: ậ ượ ả ư

Procedure Dijstra (u, v);

Begin

while True do

begin

Tìm đ nh k tho mãn Free[k] = 1 và D[k] nh nh t ; ả ấ ỏ ỉ

if D[k] = ∞ ho c k = v then BREAK; ặ

For v thu c V do ộ

If Free[v] = 1 và d[v]>d[k]+a[k][v] then

begin

d[v]:=d[k]+a[k][v];

Truoc[v]:=u;

end;

End;

M t s chú ý: ộ ố

2).

• Thu t toán làm vi c v i đ th có tr ng s không âm,ho c không có chu trình mà t ng ổ ố ệ ớ ồ ị ậ ặ ọ tr ng s âm. ố • Đ ph c t p c a thu t toán là O(n ọ ộ ứ ạ ủ ậ

ng đi ng n nh t Floyd- Warshall ườ ấ ắ

4.1.3 Thu t toán tìm đ ậ

Thu t toán này ng đi ng n nh t gi a m i c p đ nh trong đ th ậ xác đ nh đ ị ườ ấ ữ ọ ặ ồ ị. ắ ỉ

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị T t ng thu t toán nh sau: ư ưở ự ậ ư

ng đi ng n nh t gi a m i c p đ nh trong đ th , thì ta ph i xác đ nh • Đ xác đ nh đ ồ ị ữ ả ị ị ỉ ấ ườ ớ ể t c n*(n-1) giá tr , t t ấ ả ố nxn làm ma tr n l u k t qu . Khi đó A[i][j] là giá ả ọ ừ ỉ • Khi đó ta dùng luôn ma tr n tr ng s A ắ đ nh i đ n đ nh j. ế • T t tr kho ng cách ng n nh t đi t ậ ả ỉ ng đi t ọ ặ ắ ng ng v i các c p (u,v) trên đ th . ồ ị ặ ị ươ ứ ậ ậ ư ế ị ả ỉ ấ ng thu t toán này cũng khá đ n gi n: ư ưở s là đ nh k. ỉ ỉ ừ ỉ ườ ế ế đ nh u đ n đ nh v theo k. T c là ta so sánh A[u][v] v i ớ ứ ồ ế u qua k r i đ n u đ n v dài h n so v i đi t ơ ừ ớ ẽ ố ư ơ o Ch n 1 đ nh là trung gian, gi ả ử ọ o T i u hóa đ ế ố ư t ng A[u][k] và A[k][v]. N u đi t ừ ổ v thì ta s t ấ ọ ớ ỉ o Ta th y có n cách ch n đ nh k, v i m i k có n cách ch n đ nh xu t phát u và v i ớ ỗ m i u ta có n cách ch n đ nh k t thúc v. Nh v y ta có 3 vòng l p l ng nhau. i u giá tr A[u][v]. ị ọ ọ ấ ặ ồ ư ậ ỉ ỉ ế ỗ

ể xác đ nh các thành ph n liên thông c a đ th ầ ủ ồ ị. Đây là ị ứ ụ t ư ưở Cũng ng d ng t thu t toán Warshall. T t ng chính là: ng này đ ư ưở

ậ • N u t k đ n v cũng có đ ng đi, t c là ế ừ ườ ừ ế ườ ứ ứ A[k][v] = 1 thì ch c ch n có đ u đ k có đ ắ ng đi, t c là A[u][k] = 1 và t u đ n v ng đi t ắ ế ế  A[u][v] = 1. ườ ừ

3).

ả ộ ứ ạ ậ C 2 thu t toán đ u có Thu t toán đ ề c mô t đ ph c t p là : O(n nh sau: ượ ả ư ậ

Procedure Floyd_Warshall Procedure Warshall

Begin Begin

For k = 1 to n do For k = 1 to n do

For u = 1 to n do For u = 1 to n do

For v = 1 to n do For v = 1 to n do

If A[u][v] > A[u][k] + A[k][v] then If A[u][k] = 1 và A[k][v] = 1 then

A[u][v] = A[u][k] + A[k][v]; A[u][v] = 1;

End; End;

CH

NG 4: CÂY

ƯƠ

ủ ồ ị ồ

ỉ

Bài 1. Tìm cây khung nh nh t b ng thu t toán Prim c a đ th g m các đ nh A, B, C, D, E, F, H, I đ

ấ ằ c cho b i ma tr n tr ng s sau. ậ

ỏ ở

ậ ố

ượ

ọ

B C D E H A F I

15 16 19 23 20 32 18

33 13 34 19 20 12

B (cid:0)

21 20 19

(cid:0) C

22 30

21 11

(cid:0) D

23 34 29 22

23 21

(cid:0) E

20 19 21 30

17 18

(cid:0) F

23 17

18 14

(cid:0) H

(cid:0)� � 15 � � 16 33 � 19 13 13 � � � � � 32 20 20 21 � � 18 12 19 11 21 �

� � � � � � � � � � 14 � �(cid:0) �

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ự

Bài 2. Tìm cây khung nh nh t c a đ th sau theo thu t toán Kruskal và Prim.

ấ ủ ồ ị

ậ

ỏ

ủ ồ ị ồ

ỉ

Bài 3. Tìm cây khung nh nh t b ng thu t toán Prim c a đ th g m các đ nh A, B, C, D, E, F, H, I đ

ấ ằ c cho b i ma tr n tr ng s sau. ậ

ỏ ở

ậ ố

ượ

ọ

C D E F B G A H

16 15

23 19

18 32 20

B (cid:0)

13 33 24 29 13

20 19 11 21 20 19

C (cid:0)

23 33 13

22 30

21 12

D (cid:0)

E (cid:0)

23 21 17 14

F (cid:0)

23 17

G (cid:0)

20 11 19 12

14 18

(cid:0)� � 16 � � 15 13 � � � 19 24 29 22 � 18 20 21 30 � � 32 19 20 21 � � �

� � � � � � � � � � 18 � �(cid:0) �

c l p, k t qu cu i cùng c n đ a ra

ế

ả

ướ ặ

ầ ư

ả ố

ế

Yêu c u vi ừ ầ t p c nh và đ dài c a cây khung nh nh t. ủ ậ ạ

t các k t qu trung gian trong t ng b ộ

ấ

ỏ

Bài th c hành s 4: Các thu t toán v cây

ự

ố

ề

ậ

Bài t p: Cài đ t các thu t toán tìm cây khung nh nh t. ỏ ấ ậ ặ ậ

H ng d n: ướ ẫ

ồ ị ồ ị ề ề ấ ị Rõ ràng 1 đ th cho ta nhi u cây khung. V n đ là xác đ nh cây khung nào trong đ th có tr ng s sao cho t ng tr ng s là bé nh t. ấ ọ ố ổ ọ ố

ấ . Thu t toán Prim – Dijsktra xác đ nh cây khung bé nh t ậ ị

T t thu t toán tìm đ i u Dijsktra ng đi t . ư ưở ậ ự ủ ậ ườ ố ư

c duy t. ban đ u S = Ø. ỉ ệ ng đi ng n nh t gi a 2 đi m u,v ấ ữ ị c , thì thu t toán Dijsktra s ẽ đ nh u đ n đ nh ế ỉ ệ . c duy t ừ ệ ạ ư ệ ng c a thu t toán này là d a trên • Dùng t p S đ l u tr các đ nh đã đ ầ ượ ể ư ậ ữ • Đ i v i ố ớ bài toán tìm đ ậ ể ườ ắ giá tr kho ng cách t ầ ượ ch n các đ nh l n l trên đ th sao cho t ồ ị ừ ỉ ả ỉ ọ i khi đ nh v đ ể ượ . Quá trình d ng l m i duy t là nh nh t có th đ ỉ ỏ ấ ớ • Đ i v i ố ớ bài toán xác đ nh cây khung nh nh t ị i khi không còn duy t đ trên, nh ng ch ạ ư ượ ỏ ấ , thì quá trình duy t các đ nh cũng nh ỉ ữ . c thêm đ nh nào n a ỉ d ng l ừ ệ ượ ỉ

ế D[v] không ph i là kho ng cách đi t ế v đ n 1 đ nh trong t p S). ự • Chú ý ở cách t ừ ắ ả đ nh u đ n v mà là kho ng ả ậ ừ ỉ ỉ ế i đ nh cu i cùng ≠ ∞, thì ta đã có 1 cây khung bé ả ấ ừ ố ạ ỉ ả o N u giá tr kho ng cách t ị

i thì không xác đ nh đ c cây khung bé nh t. ng h p ng ợ c l ượ ạ ườ ị ượ ấ Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị đây bi n ả v đ n S (là kho ng cách ng n nh t t ế ế nh t.ấ o Trong tr

Thu t toán đ c mô t nh sau: đ ph c t p c a thu t toán là O(n

2).

ậ ượ ả ư ộ ứ ạ ủ ậ

Procedur Prim_Dijsktra;

Begin

Ch n 1 đ nh u là g c c a cây. D[u] = 0; D[v] = ∞ v i v ≠ u; S = Ø ố ủ ớ ọ ỉ

while True do

begin

Tìm đ nh k tho mãn Free[k] = 1 và D [k] nh nh t ả ỉ ỏ ấ ;

If (không xác đ nh đ c k OR D[k] = ∞) then Break. ị ượ

Else F := F U (T[k],k), S = S U k ; Free[k] = 0 For v ˛ V do

If Free[v] = 1 và D[v]> A[k][v] then // chú ý đk này!!!!!

begin

D[v]:= A[k][v]; T[v]:=k;

end;

End;

4.1.4 Thu t toán Kruskal (thu t toán tham lam – ăn tham)

ậ

T t ng c a thu t toán nh sau: ư ưở ậ ủ

nh đ n l n, sao cho nó không t o ra chu ư • Kh i t o t p các c nh c a cây khung F = Ø. ủ ạ • Ch n các c nh c a đ th theo tr ng s t ủ ồ ị ố ừ ỏ ế ớ ọ ạ trình trong t p F.

ỏ ậ ạ ậ ọ ở ạ ậ ạ ọ ậ • Đ a c nh v a ch n vào t p F và xóa nó kh i t p c nh E c a đ th . ừ ủ ồ ị ư ạ • Quá trình l p l ặ ạ i cho đ n khi trong t p F có đúng n-1 c nh. ậ ế ạ

Thu t toán mô t nh sau: ậ ả ư

Procedure Kruskal;

Begin

F := Ø; // kh i t o t p r ng ở ạ ậ ỗ

While |F| < (n-1) and (E ≠ Ø) do // ki m tra s ph n t c a t p F ầ ử ủ ậ ể ố

Begin

Ch n c nh {e} sao cho tr ng s trên {e} là nh nh t. ọ ạ ấ ọ ỏ ố

E:=E\{e};

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

End;

if (|T| < n-1) then

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ự

Đ th không liên thông; ồ ị

End;

Đ ph c t p c a thu t toán là O(m*log

2m) v i |E| = m.

ộ ứ ạ ủ ậ ớ

Bài t p t ng h p:

ậ ổ

ợ

1. Cho ma tr n k (tr ng s ) c a m t đ th nh sau ộ ồ ị ư ề ọ ố ủ ậ

ng ng i thích. N u có,tìm chu ả ồ ị ả ế ườ ử ng đi) Euler trong đ th . ồ ị c. Đ th có ph i là đ th Hamilton hay không? N u có, tìm chu trình Hamilton trong ồ ị ế ả

đ nh s 1 đ n đ nh s 8. ế ườ ố ỉ ng đi ng n nh t t ắ ỏ 2. Cho ma tr n k (tr ng s ) c a m t đ n đ th vô h a. V đ th t ẽ ồ ị ươ ứ b. Đ th có ph i là đ th Euler (n a Euler) hay không? Gi ồ ị trình (đ ồ ị đ th . ồ ị d. Tìm đ ấ ừ ỉ ố e. Tìm cây khung nh nh t c a đ th . ấ ủ ồ ị ộ ơ ề ọ ố ủ ồ ị ướ ậ ng nh sau: ư

t b c c a các đ nh. Đây có ph i là đ th Euler hay không? ả ỉ đ nh 1 đ n các đ nh còn l ồ ị i b ng thu t toán Dijkstra. ạ ằ ậ a. V đ th , cho bi ẽ ồ ị b. Tìm đ ườ c. Tìm cây khung nh nh t c a đ th b ng thu t toán Kruskal. ế ậ ủ ng đi ng n nh t t ắ ỏ ấ ừ ỉ ế ấ ủ ồ ị ằ ỉ ậ 17. Cho đ th nh hình v : ẽ ồ ị ư

ị ậ ủ ậ ỉ ả ạ ề ọ ự a. Xác đ nh bán b c ra và bán b c vào c a các đ nh c a đ th . ủ ồ ị b. Đây có ph i là đ th liên thông m nh không? T i sao? ồ ị ạ c. Xây d ng ma tr n k , tr ng s c a đ th . ố ủ ồ ị ậ ng đi ng n nh t t d. Dùng thu t toán Dijkstra tìm đ ắ ườ ấ ừ ỉ ậ đ nh 1 đ n đ nh 3. ế ỉ 18. Cho đ th nh hình v : ẽ ồ ị ư

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ự

a. Xác đ nh b c c a các đ nh c a đ th , t đó cho bi ủ ồ ị ừ ỉ ị ế ử t đây có là đ th Euler hay n a ồ ị

ậ ủ Euler hay không? ậ ự ề ọ ậ ng đi ng n nh t t ắ ấ ừ ỉ đ nh 1 đ n đ nh 5 trong đ th . ồ ị ế ỉ b. Xây d ng ma tr n k tr ng s c a đ th ố ủ ồ ị c. Dùng thu t toán Dijkstra tìm đ ườ d. Tìm cây khung nh nh t c a đ th . ấ ủ ồ ị ỏ

Bài t p nâng cao:

ậ

1. Bài toán truy n tin trên m ng. ề ạ

ồ ề ộ ạ ế ể ượ ề ế ấ ằ ế ạ ộ ố ế ừ ề ế ả ử ế trong m ng, hãy đ i h ộ . Gi nó đ n các máy khác là l ẻ ể ế ề ộ ố ổ ả ạ ạ ở ố ạ ẵ ng càng ít càng t t. ề 1 đ n N, và M kênh truy n tin m t chi u M t m ng máy tính g m N máy đánh s t ế ố ừ ạ ộ 1 đ n M. M ng máy tính là thông g a m t s c p máy trong m ng đ c đánh s t ữ ạ ố ừ ộ ố ặ ng m t máy có th truy n tin đ n m t máy b t kỳ khác b ng các đ su t, nghĩa là t ườ ố ộ ừ ộ ế n i tr c ti p ho c thông qua các máy trung gian. M t máy trong m ng là s ch n n u ẵ ặ ố ự nó đ n các máy khác là ch n. M t máy trong m ng là s kênh truy n tin tr c ti p t ạ ẵ ố ự n u s kênh truy n tin tr c ti p t s l s s và t là hai ự ế ừ ề ố ẻ ế ố ng truy n tin c a m t s kênh đ bi n đ i m ng đã máy l ủ ổ ướ ạ ẻ t ph i thông su t) mà trong nó hia máy s và t tr thành cho thành m ng (không nh t thi ố ế ấ 2 máy ch n và không làm thay đ i tính ch n l c a các máy khác trong m ng. S kênh ẵ ẻ ủ ổ đ i h ổ ướ ố

D li u nh p vào t ữ ệ ậ ừ file văn b n Net.inp: ả Net.inp Net.out

- Dòng đ u tiên ch a 2 s N, M (N<2000, M<10000). ố ứ ầ 3 6 9

- Dòng th 2 ch a 2 s s và t. ứ ứ ố 1 1 6

7 2 3 - ứ ố ề 9 3 4 ế máy u Dòng th I trong s M dòng ti p theo ch a 2 s u ế ố i ứ ự t kênh truy n tin th i truy n tin tr c và vi cho bi ứ ề i đ n vế ti p t ế ừ 4 1

• 4 6 K t qu ghi ra file Net.out ế ả

6 3 ố ượ ng kênh c n thay đ i h ầ ổ ướ ng 2 5 - Dòng đ u ghi s l ầ truy n tin (s q). ề ố

5 3 - M i dòng trong q dòng ti p theo ghi ch s kênh ỉ ố ế 5 6 ỗ c n đ o ng ả ầ c h ượ ướ ng truy n tin. ề

• Ví d : (xem b ng s li u bên c nh) ố ệ ụ ả ạ

2. Bài toán thang máy

ồ ế ể ệ

ố ừ ọ ế ầ ể ế ầ ừ ầ ể ế ầ ệ ầ ỉ ụ 1 đ n N (0

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ự ộ ầ ồ ở ề ầ ả ổ ườ ng thang máy ph i di chuy n là ít ả ể yêu c u r i tr v t ng m t sao cho t ng qu ng đ nh t.ấ

D li u nh p vào t ữ ệ ậ ừ file văn b n Tm.inp ả

- Dòng đ u ghi 2 s nguyên d ng N và M. ầ ố ươ

- M dòng ti p theo, dòng th I ghi 2 s a ố i và bi mô t ứ ế ả yêu c u th i ầ ứ

K t qu ghi ra file văn b n Tm.out ế ả ả

- Dòng đ u là t ng quãng đ ng tìm đ ầ ổ ườ c ượ

- Dòng th 2 mô t th t ứ ả ứ ự ự th c hi n các công vi c b i m t hoán v c a 1, ệ ở ị ủ ệ ộ 2, …M.

3. Bài toán K đ ườ ng đi ng n nh t ắ ấ

c đánh s t ượ ố ữ c đánh s t ể ố ự 1 đ n N, gi a 2 thành ph có ố 1 đ n M ế ch c cu c ch y đua ti p s c “thông ng n i tr c ti p ho c không. Các con đ ặ ể ế ạ ổ ế ố ừ ng này đ ộ ố ừ ế ứ ườ ứ ượ ạ Vùng đ t X có N thành ph (3

- Thành ph xu t phát là thành ph 1 và k t thúc là thành ph N. ế ấ ố ố ố

- M i đ i thi đ u có K ng i th nh t đ n đ ườ ự ấ ườ ứ ượ ứ ấ ế ượ i th hai m i b t đ u r i kh i thành ph 1, khi ng ố ớ ờ i đích thì đ c thành ườ ườ i ỏ i th 3 m i r i kh i thành c xem i d thi. Khi ng ớ ắ ầ ờ c thành ph N thì ng ứ ườ ố i th K v t ề ớ ứ ỏ ượ ườ ế ph N thì ng th 2 đ n thành đ ế ph 1, c nh v y cho đ n khi ng ứ ư ậ nh th i đi m tính cho toàn đ i. ể ộ ỗ ộ ố ứ ố ư ờ

- Đ ng ch y c a các đ i viên không đ c gi ng nhau hoàn toàn. ạ ủ ườ ộ ượ ố

- Có th ch y l i đo n đ ng đã ch y. ể ạ ạ ạ ườ ạ

ươ ạ ờ ỏ ộ Hãy vi ti p s c n u trên n u các v n đ ng viên có t c đ ch y nh nhau. ộ ng trình tính th i gian nh nh t đ m t đ i hoàng thành cu c ch y đua ấ ể ộ ộ ố ộ ạ t ch ế ế ứ ế ư ế ậ

D li u nh p vào t file văn b n Kminpath.inp ữ ệ ậ ừ ả

- Dòng đ u ghi 2 s nguyên d ng K, N và M. ầ ố ươ Net.inp Net.out

ế 4 5 8 23 - M dòng ti p theo, m i dòng ch a 3 s nguyên i, j, ỗ ng đi tr c ti p gi a hai thành ể ệ ố ữ 1 2 1 1 ứ w th hi n m t đ ự ế ộ ườ ph i và j m t th i gian ch y là w. ạ ờ ấ ố

1 3 2 1325 K t qu ghi ra file văn b n Kminpath.out ế ả ả 1 4 2 135 - Dòng th nh t ch a m t s nguyên duy nh t là ấ 2 3 2 12125 ứ th i gian ch y nh nh t c a 1 đ i ộ ỏ ứ ấ ạ ộ ố ấ ủ ờ 2 5 3 125 ế ể ệ 3 4 3 - K dòng ti p theo, m i dòng th hi n hành trình ỗ ộ ạ ủ 3 5 4 ch y c a m t v n đ ng viên trong đ i là dãy các ộ thành ph liên ti p trên hành trình đó. ộ ậ ế ố

4 5 6 Ví d : (xem b ng bên) ụ ả

ự Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị 4. Bài toán công chúa kén ch ngồ

ị ủ ồ ả ớ ằ ấ ồ ơ ủ ố ớ ể ằ ọ ế ố ủ ể ộ phòng đ u tiên. Nhà vua trao cho m i chàng trai đ n c u hôn m t s ả ả ộ ồ ầ ế ỗ ườ ầ ỗ ố ế ố ề ế ế ẫ ố ố i m t s phòng Magachip IV the Splendid, vua c a Byteotia, có ý đ nh ch n phò mã cho công chúa Ada ọ ệ i thông minh, không keo ki t c a mình. Công chúa thì mu n ch ng mình ph i là ng ủ ườ ố và không lãng phí quá. Nên nhà vua suy nghĩ m i ch n ph ng pháp th tài b ng cách ử ươ ọ ch n lâu đài c a mình làm n i thi đ u. Lâu đài g m nhi u phòng tr ng bày đ quí ồ ư ề hi m và n i v i nhau b ng dãy các hành lang đ th n dân có th tham quan, phòng ể ầ cu i cùng là phòng c a công chúa, đ thăm m t phòng ph i tr m t đ ng bytealer và ộ ố s xu t phát t ầ ừ ấ ẽ i thăm 1 s phòng sao cho đ n đ ng ti n ch a trong 1 cái túi và yêu c u là m i ng ế ứ ề ồ ề phòng cu i cùng thì tiêu h t s ti n đã cho, n u đ n phòng cu i cùng mà v n còn ti n thì ph i thăm l ả ộ ố ạ

i quy t v n đ trên đ 1 chàng trai luôn ớ ạ i. Hãy l p trình gi ậ ả ế ấ ề ể tr ng bày n a m i quay l ữ ư có

Zam.inp th th c hi n đ c yêu c u c a nhà vua. ể ự ệ ượ ầ ủ

5 6 3 4 9 file Zam.inp miêu t lâu đài, s hi u phòng công ả ố ệ D li u nh p t ậ ừ ữ ệ , t ng s ti n trong túi: chúa đang ở ổ ố ề 1 2 3 4 5

2 4 ng n(s l ầ ố ượ ố ố ố ệ 5 4 ng phòng), m(s - Dòng đ u tiên có 5 s nguyên d ươ hành lang), e(s hi u phòng xu t phát), p(s hi u phòng công ố ệ ấ chúa), b(t ng s ti n vua ban cho). ố ề ổ 1 5 ng c ố ươ ỗ ầ i, m i s là chi phí m i l n ỗ ố 1 2 - Dòng 2 có n s nguyên d vào thăm trong phòng i. 2 3 ng (x, y), ặ ố ừ ươ 3 1 - Trong m dòng ti p theo có t ng c p s nguyên d ị ộ ố Chiacat.inp Chiacat.out ế m i c p n i bi u th m t hành ể lang n i phòng x v i phòng y. ỗ ặ ố ớ Zam.out

10 10 18 ế 3 2 4 1 7 1 2 8 Tính ra dãy các phòng đi qua đ n phòng c a công chúa và l u hành trình vào file ư ủ Zam.out 3 6 1 4 4 Ví d : (nh b ng d li u bên c nh) ữ ệ ư ả ụ ạ 4 5 1 7 1

6 10 2 3 5 5. Bài toán chia c t đ ch ắ ị

8 10 2 4 5 ố 2 9 9 ơ ả ố ị ế 3 4 4

3 6 2 ữ ộ

3 9 7 ướ 4 5 5 ệ

5 6 6 ớ ư ế 5 7 5 ỉ ầ i. Bi 5 8 3 ự ượ ế ằ

6 8 7

6 10 1 t ch ớ ố ươ

7 8 5 ng đ giành chi n th ng. Cu i năm 1944, quân Liên Xô ph n công vào vùng X, n i có N thành ph b phát xít Đ c chi m đóng. D c theo các con ọ ứ ng gi a 2 thành ph đ u có quân đ ố ề ườ ữ ự ủ . B tham m u quân s c a Đ c canh gi ư ứ ệ Liên Xô m i ch đ o ph n công tiêu di t ả ớ ỉ ạ đ ch, b c đ u th c hi n chia c t quân ắ ệ ự ầ ị t đ chúng đ ch thành 2 vùng tách bi ể ị c v i nhau, nh ng không liên l c đ ư ượ ạ ợ c n tính toán tiêu di i t nh th nào là l ệ ầ ng ít nh t mà ch c n huy đ ng l c l ấ ộ t r ng đi nh t đ giành th ng l ắ ấ ợ ể ả ố t quân Đ c thì Liên Xô ph i b tiêu di ứ ệ trí s quân ít nh t b ng v i s quân đ ch ố ị ấ ằ ng trình giúp chi m đóng. Hãy vi ế ế ề b tham m u quân Liên Xô ch c n đi u ư ộ ít nh t l c l ể ấ ự ượ ỉ ầ ế ắ 8 10 1

9 10 9 23

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị D li u nh p vào t file Chiacat.inp ậ ừ ự ữ ệ

ng N (s thành ph t i đa 100) và M(s con ươ ầ ố ố ố ố ố ng n i các c p 2 thành ph trong vùng X). đ - Dòng đ u tiên là 2 s nguyên d ố ườ ặ ố

ng i, j và w th hi n trên con ươ ố ể ệ ng n i thành ph i v i thành ph j hi n có w lính Đ c. đ - M dòng ti p theo, m i dòng có 3 s nguyên d ỗ ố ế ố ườ ứ ệ ớ ố

K t qu ghi ra file Chiacat.out ế ả

- Dòng đ u là s l ng quân Liên Xô c n đi u đ ng ố ượ ầ ề ầ ộ

ng (u, v) mà quân Liên Xô ườ - Dòng sau, m i dòng có 2 s u và v th hi n con đ ỗ i trong đ t ph n công đ u tiên này. ợ ạ c n chi m l ầ ể ệ ầ ố ả ế

Ví d : (xem b ng bên) ụ ả

Vi

t ti u lu n

ế ể

ậ

Đ TÀI 1:

Ề

NG PHÁP Đ TH Đ TH HI N VI C B

Ồ Ị Ể

ƯƠ

Ể

Ệ

S D NG PH Ử Ụ TRÍ L CH THI CHO SINH VIÊN KHOA TOÁN – TIN H C. Ị

Ệ Ố Ọ

Đ C T Đ TÀI : Ả Ề

Ặ

ng pháp đ th đ th hi n vi c b trí l ch thi cho sinh viên khoa

ồ ị ể ể ệ

ệ

ố

ị

ươ Toán – Tin h c 7 môn thi trong 7 ngày.

S d ng ph ử ụ ọ

Yêu c u ph i b trí l ch thi sao cho hai môn thi c a cùng m t giáo viên không

ầ

ủ

ộ

ả ố c r i vào hai ngày liên ti p nhau.

ị ế

ượ ơ

t r ng không có giáo viên nào có nhi u h n 5 môn thi.

ế ằ

ề ơ

V lý thuy t : Tìm hi u và trình bày các khái ni n c b n v :

ệ ơ ả ề

ề

ể

ế

ng.

- Đ th và các khái ni m c b n v đ th có h ệ

ơ ả ề ồ ị

ồ ị

ướ

ng, đ th vô h ồ ị

ướ

- Các th t c (hàm) có liên quan đ n giao di n c a màn hình đ h a. ế

ệ ủ

ồ ọ

ủ ụ

- Đ ng đi và chu trình Hamilton.

ườ

- Thi

t l p thu t toán c a đ tài và minh h a k t qu b ng đ th Hamilton.

ế ậ

ọ ế

ả ằ

ồ ị

ủ

ề

ậ

V l p trình:

ề ậ

- Vi

t ch

ng trình d a vào thu t toán đã thi

t l p.

ế

ươ

ự

ậ

ế ậ

- Giao di n thân thi n v i ng

i s d ng.

ệ ớ

ệ

ườ ử ụ

- K t qu cho ra là m t đ th v i màu s c phân bi

ộ ồ ị ớ

ế

ắ

ả

ệ

YÊU C U C A Đ TÀI Ủ Ầ Ề

MÔI TR

NG CÀI Đ T

ƯỜ

Ặ

ự

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị Ngôn ng s d ng : C, C++, Visual C++, Visual Basic ữ ử ụ

Đ TÀI 2:

Ề

Ử Ụ

ƯƠ

NG PHÁP Đ TH Đ GI I BÀI TOÁN Ồ Ị Ể Ả

S D NG PH DÂN GIAN (BÀI TOÁN 1).

Đ C T Đ TÀI : Ả Ề

Ặ

ộ ị

ế

ả

ộ

ườ

ể n ng uy n. ự

Có m t v khách đ n xin nhà vua ban cho m t qu cam trong v n m i hay ph i qua 3 c ng lính canh.

Nhà vua ch p thu n. Ông ta đ n v ậ

ế ườ

ả

ấ

ớ

ổ

Đ n c ng th nh t, ng

i lính canh b o v khách: " Vua ban cho thì anh c vào

ứ

ế

ổ

ườ

ứ

ị

mà hái, nh ng lúc ra ph i đ a cho ta m t n a s cam và thêm m t trái".

ộ

ấ ả ư

ả ộ ữ ố

ổ

ứ

Qua c ng th hai và th ba, hai lính canh cũng nói v i anh nh ng ư n còn đ ả ấ

ớ ỏ ườ

ứ

ể

ả

ị

ườ ượ

i lính canh ả c m t qu ộ

ứ th nh t. V khách ph i hái bao nhiêu qu cam đ lúc ra kh i v trong tay?

V lý thuy t : Tìm hi u và trình bày các khái ni n c b n v :

ệ ơ ả ề

ể

ế

ề

- Các th t c (hàm) có liên quan đ n giao di n c a màn hình đ h a. ế

ệ ủ

ồ ọ

ủ ụ

ng.

- Đ th và các khái ni m c b n v đ th có h ệ

ơ ả ề ồ ị

ồ ị

ướ

ng, đ th vô h ồ ị

ướ

- Minh h a bài toán b ng đ th . ồ ị

ằ

ọ

- Thi

ế ậ

t l p thu t toán. ậ

i s d ng thay đ i k t qu s

ể ở ộ

ằ

ườ ử ụ

ổ ế

ả ố

c sau khi ra kh i v

- Có th m r ng bài toán b ng cách cho ng n. ượ

ng cam mà v khách có đ ị

ỏ ườ

l ượ

V l p trình:

ề ậ

- Vi

t ch

ng trình d a vào thu t toán đã thi

t l p.

ế

ươ

ự

ậ

ế ậ

- Giao di n thân thi n v i ng

i s d ng.

ệ ớ

ệ

ườ ử ụ

- K t qu cho ra là m t đ th v i màu s c phân bi

ộ ồ ị ớ

ế

ắ

ả

ệ

YÊU C U C A Đ TÀI Ủ Ầ Ề

MÔI TR

NG CÀI Đ T

ƯỜ

Ặ

Ngôn ng s d ng : C, C++, Visual C++, Visual Basic

ữ ử ụ

Đ TÀI 3:

Ề

Ử Ụ

ƯƠ

NG PHÁP Đ TH Đ GI I BÀI TOÁN Ồ Ị Ể Ả

S D NG PH DÂN GIAN (BÀI TOÁN 2).

Đ C T Đ TÀI : Ả Ề

Ặ

Có hai cha con ng

i nông dân đi mua vé tàu h a. Ng

ườ

ỏ

này bao nhiêu tu i ?". Ông cha tr l ổ

i bán vé tàu h i: " Chú bé ườ ổ i: "Con trai tôi tu i g p 5 l n em gái nó, m nó tu i ầ

ỏ ổ ấ

ả ờ

ẹ

ổ

ộ

ạ

i". Ng

ổ ủ ợ ạ

ườ

ộ

i. Còn m tôi thì ẹ ủ ồ i bán vé tàu nói: "Thôi đ r i!

ự ổ

ằ t c gia đình chúng tôi c ng l c mi n vé". ễ

ượ

D a vào đâu mà ng

t r ng, theo lu t đ

ự

ườ

ế ằ

ậ ườ

ắ ng s t

i 6 tu i đi cùng ng

thì tr em d ẻ

ướ

ổ

i vé tàu mi n vé cho chú bé? Bi c mi n vé. ễ

ễ i l n s đ ườ ớ ẽ ượ

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị g p 6 l n tu i nó. Tu i tôi thì b ng tu i c a v và hai con tôi c ng l ầ ấ b ng tu i c a t ổ ủ ấ ả ằ Con ông đ

V lý thuy t : Tìm hi u và trình bày các khái ni n c b n v :

ệ ơ ả ề

ể

ề

ế

- Các th t c (hàm) có liên quan đ n giao di n c a màn hình đ h a. ế

ệ ủ

ồ ọ

ủ ụ

ng.

- Đ th và các khái ni m c b n v đ th có h ệ

ơ ả ề ồ ị

ồ ị

ướ

ng, đ th vô h ồ ị

ướ

- Minh h a bài toán b ng đ th . ồ ị

ằ

ọ

- Thi

ế ậ

t l p thu t toán. ậ

V l p trình:

ề ậ

- Vi

t ch

ng trình d a vào thu t toán đã thi

t l p.

ế

ươ

ự

ậ

ế ậ

- Giao di n thân thi n v i ng

i s d ng.

ệ ớ

ệ

ườ ử ụ

- K t qu cho ra là m t đ th v i màu s c phân bi

ộ ồ ị ớ

ế

ắ

ả

ệ

YÊU C U C A Đ TÀI Ủ Ầ Ề

MÔI TR

NG CÀI Đ T

ƯỜ

Ặ

Ngôn ng s d ng : C, C++, Visual C++, Visual Basic

ữ ử ụ

Đ TÀI 4:

Ề

NG ĐI NG N NH T TRÊN

Ậ

ƯỜ

Ắ

Ấ

CÁC THU T TOÁN TÌM Đ Đ THỒ Ị Đ C T Đ TÀI : Ả Ề

Ặ

ụ ế ơ ả V n d ng các lý thuy t c b n v đ th đ cài đ t ch ươ ữ ng trình cho phép bi u di n ễ ả i ướ ể c b ng gi ằ ậ ể ặ ấ ỉ ng. ề ồ ị ể đ th , ki m tra tính liên thông và tìm đ ồ ị ắ ườ thu t Dijkstra, Ford-Bellman trên đ th vô h ậ ng đi ng n nh t gi a 2 đ nh cho tr ướ ồ ị

YÊU C U C A Đ TÀI : Ủ Ầ Ề • Lý thuy t:ế ơ ả ng và đ th vô h ồ ị ng ng pháp tìm ki m trên đ th (tìm ề ồ ị ễ ướ ế ồ ị ươ ồ ị theo chi u r ng và chi u sâu) và tính liên thông. ề ư ườ ng  Các thao tác c b n v đ h a. ề ồ ọ  Các khái ni m v đ th có h ướ ệ  Các cách bi u di n đ th , các ph ể ề ộ  Các gi i thu t có liên quan nh : ki m tra tính liên thông, tìm đ ể ậ ả đi ng n nh t. ắ ấ t đ cài đ t ch ng trình.  Nh ng c u trúc d li u c n thi ế ể ặ ươ ấ ữ ệ ầ ươ ả • Ch ữ

ơ ả  C p nh t d li u v đ th . ề ồ ị ậ ữ ệ  Bi u di n đ th trên màn hình. ồ ị ễ  Ki m tra tính liên thông. ữ ng trình: Ph i có nh ng ch c năng c b n sau: ứ ậ ể ể

ự

 Cho phép tìm đ ng đi ng n nh t gi a 2 đ nh b t kỳ. Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ườ ữ ấ ấ ắ ỉ

MÔI TR NG CÀI Đ T : ƯỜ Ặ

++

Ngôn ng l p trình s d ng: C hay C ử ụ ữ ậ

Đ TÀI 5: CÁC GI I THU T TÌM CÂY PH T I TI U Ậ

Ủ Ố Ể

Ả

Ề

Đ C T Đ TÀI : Ả Ề Ặ

V n d ng các lý thuy t c b n v đ th đ cài đ t ch ế ơ ả ụ ặ ể i thu t Kruscal. ề ồ ị ể ọ ượ ươ ng nh nh t b ng gi ấ ằ ng trình cho phép bi u di n ễ ậ ả ỏ đ th , ki m tra tính liên thông và tìm cây có tr ng l ồ ị ậ ể

YÊU C U C A Đ TÀI : Ủ Ầ Ề • Lý thuy t:ế ơ ả ng và đ th vô h ồ ị ng ng pháp tìm ki m trên đ th (tìm ề ồ ị ễ ướ ế ồ ị ươ ồ ị theo chi u r ng và chi u sâu) và tính liên thông. ề

ả ư ả i thu t Kruscal tìm cây có tr ng l  Các thao tác c b n v đ h a. ề ồ ọ  Các khái ni m v đ th có h ướ ệ  Các cách bi u di n đ th , các ph ể ề ộ i thu t có liên quan nh : ki m tra tính liên thông, gi ậ ọ i thu t ậ ượ ng ể ậ ả ấ t đ cài đ t ch ng trình.  Nh ng c u trúc d li u c n thi ế ể ặ ươ ữ ệ ầ ươ • Ch ữ ả

 Các gi ki m tra tính liên thông và gi ể nh nh t. ỏ ấ ữ ng trình: Ph i có nh ng ch c năng c b n sau: ứ ậ ể ể

ơ ả  C p nh t d li u v đ th . ậ ữ ệ ề ồ ị  Bi u di n đ th trên màn hình. ồ ị ễ  Ki m tra tính liên thông.  Cho phép tìm cây có tr ng l ọ ượ ng nh nh t. ỏ ấ

MÔI TR NG CÀI Đ T : ƯỜ Ặ

Ngôn ng l p trình s d ng: C hay C ử ụ ữ ậ

Đ TÀI 6: BÀI TOÁN T CH C THI CÔNG

Ổ Ứ

Ề

Đ C T Đ TÀI : Ả Ề Ặ

ươ ể ậ ể V n d ng các lý thuy t c b n v đ th đ cài đ t ch ể ế ơ ả ạ ế ặ ờ ồ ị ấ ụ ễ ờ ễ ạ ệ ế ng trình cho phép bi u di n ễ ề ồ ị ể ấ ủ ừ đ th , bi u di n đ th sau khi x p h ng, xác đ nh các th i đi m s m nh t, tr nh t c a t ng ị ớ ồ ị công vi c, th i gian hoàn thành công trình và v s đ GANT th hi n k ho ch hoàn thành ể ệ ẽ ơ ồ công trình.

YÊU C U C A Đ TÀI : Ủ Ầ Ề • Lý thuy t:ế ơ ả

 Các thao tác c b n v đ h a. ề ồ ọ  Các khái ni m v đ th có h ng ướ ướ ệ  Các cách bi u di n đ th , Các phép bi u di n đ th . ồ ị ể ng và đ th vô h ồ ị ể ề ồ ị ễ ồ ị ễ

ự

i thu t x p h ng trên đ th , gi i thu t xác đ nh các th i gian Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ậ ế ả ạ ả ậ ờ ị ồ ị ấ ễ ấ  Gi s m nh t và th i gian tr nh t. ờ ớ  Nh ng c u trúc d li u c n thi t đ cài đ t ch ng trình. ữ ệ ầ ế ể ấ ươ ặ ươ ả • Ch ữ

ch c thi công. c và sau khi x p h ng lên màn hình. ạ ổ ứ ế ữ ng trình: Ph i có nh ng ch c năng c b n sau: ứ ề ậ ồ ị ướ ể ể ờ ơ ả  C p nh t d li u v bài toán t ậ ữ ệ  Bi u di n đ th tr ễ  Xác đ nh các th i đi m s m nh t, tr nh t c a t ng công vi c, th i ờ ấ ấ ủ ừ ễ ệ ị ớ gian hoàn thành công trình

 V s đ GANT ẽ ơ ồ

MÔI TR NG CÀI Đ T : ƯỜ Ặ

Ngôn ng l p trình s d ng: C hay C ử ụ ữ ậ

Đ TÀI 7: BÀI TOÁN QU N LÝ D ÁN

Ự

Ả

Ề

Đ C T Đ TÀI : Ả Ề Ặ

ươ ể ậ ể V n d ng các lý thuy t c b n v đ th đ cài đ t ch ể ế ơ ả ạ ế ặ ờ ồ ị ấ ụ ễ ờ ễ ạ ế ệ ng trình cho phép bi u di n ễ ề ồ ị ể ấ ủ ừ đ th , bi u di n đ th sau khi x p h ng, xác đ nh các th i đi m s m nh t, tr nh t c a t ng ị ớ ồ ị công vi c, th i gian hoàn thành công trình và v s đ GANT th hi n k ho ch hoàn thành ể ệ ẽ ơ ồ công trình.

YÊU C U C A Đ TÀI : Ủ Ầ Ề • Lý thuy t:ế ơ ả

ề ồ ị ễ ồ ị i thu t x p h ng trên đ th , gi ng và đ th vô h ồ ị ể i thu t xác đ nh các th i gian ễ ậ ả ạ ả ờ ồ ị ấ ễ ấ  Các thao tác c b n v đ h a. ề ồ ọ  Các khái ni m v đ th có h ng ướ ướ ệ  Các cách bi u di n đ th , Các phép bi u di n đ th . ồ ị ể  Gi ị ậ ế s m nh t và th i gian tr nh t. ờ ớ  Nh ng c u trúc d li u c n thi t đ cài đ t ch ng trình. ữ ệ ầ ế ể ấ ươ ặ ươ ả • Ch ữ

 V s đ GANT ẽ ơ ồ

MÔI TR NG CÀI Đ T : ƯỜ Ặ

S d ng: MS . PROJECT 2003 ử ụ

Đ TÀI 8: BÀI TOÁN “8 QUÂN H U”

Ậ

Ề

Đ C T Đ TÀI : Ả Ề

Ặ

8 sao cho không có quân h u nào có th

ậ

ể c con khác (theo lu t ch i c vua), nghĩa là ph i đ t các quân h u sao cho

ậ

ả ặ

ặ ườ

ộ

ạ ng chéo nào trên bàn c có h n 1 quân h u. Ch ng h n, ơ

ậ

ờ

ậ ẳ

ặ

ậ

ộ

Bài t p ậ và th c hành môn lý thuy t đ th ự ế ồ ị Bài toán : Đ t 8 quân h u trên bàn c vua 8 ờ ặ t n công đ ơ ờ ượ ấ không có hàng, c t ho c đ m t cách đ t quân h u đúng nh sau :

Q

YÊU C U C A Đ TÀI : Ủ Ầ Ề

ế

ề

ữ

ữ ệ

i thu t ậ

ả i thu t tìm ki m sâu k t h p quay lui (Backtracking)

ậ

ế

ế ợ

ặ ấ ặ

ướ

ấ ả

ế

ặ ế

ứ

ậ

ủ ộ ộ ậ

ứ

ậ

ở

ầ

i trên bàn c cho đ n khi tìm đ

ứ i đúng.

i gi

ứ ấ ể ặ ế

ộ ờ

ả

ờ

ỗ ướ

ờ

ng trình sang file th c thi.

V lý thuy t : - N m v ng lý thuy t c b n v c u trúc d li u và gi ắ ế ơ ả ề ấ - Gi ả V l p trình: ề ậ - Cài đ t c u trúc d li u t ch c bàn c . ờ ữ ệ ổ ứ c tiên, đ t quân - Cài đ t thu t toán tìm ki m sâu k t h p quay lui theo nguyên t c : Tr ậ ế ợ ế ặ ắ t c các ô c a c t đó đã b kh ng ch nên không h u vào ô th nh t c a c t 1, rõ ràng t ị ố ứ ấ ủ ộ ậ th đ t quân h u khác. Đ t ti p m t quân h u vào c t th hai, hai ô đ u c a c t đó đã ộ ể ặ ầ ủ ộ b c m b i quân h u th nh t, do v y ta đ t quân h u vào ô th ba. Ti p t c v i c t ế ụ ớ ộ ậ ị ấ ặ ộ th ba, ô đ u tiên có th đ t quân h u c a c t này là ô th năm … Ti p t c v i các c t ế ụ ớ ậ ủ ộ ứ còn l c m t l ượ ạ - Hi n th bàn c sau m i n ể - D ch ch ị

c đi. ự

ị ươ

Ngôn ng l p trình s d ng : C, C

++, Visual C++

ử ụ

ữ ậ

Đ TÀI 9: BÀI TOÁN “QUÂN MÃ ĐI TU N”

Ầ

Ề Đ C T Đ TÀI : Ả Ề

Ặ

8, m t quân mã đ

ộ

ượ i m t ô nào đó. Hãy tìm cách di chuy n quân mã qua t

ủ

ỉ ượ

ể ẳ

ầ

ạ

ị

ị ấ ả c đi qua 1 l n duy nh t. Ch ng h n 10 v trí h p l i ô (1, 1) trên bàn c vua nh

ầ c phép đi theo lu t c vua. V trí đ u ậ ờ t c các ô ợ ệ ư

ắ ầ

ế

ở

ờ

Bài toán : Trên bàn c vua 8 ờ tiên c a quân mã đ t t ộ ặ ạ c a bàn c sao cho m i ô ch đ ấ ỗ ờ ủ đ u tiên cho quân mã n u quân mã b t đ u kh i hành t ạ ầ sau :

4

1

6

2

5

7

3

8

9 ...

10

YÊU C U C A Đ TÀI : Ủ Ầ Ề

ề

i thu t.

ắ

ậ

ả

ữ ệ

ặ ấ

ch c bàn c . ờ ặ

ầ

ử

ệ

ể

ạ

ả

ọ

ế ế

ể ặ

ữ

ọ

ướ trên bàn c . C ti p t c cho nh ng n

ằ ờ ứ ế ụ

ướ

ữ

ế

ỗ ướ

ờ

c đi. ự

ự ế

++, Visual C++

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị V lý thuy t : - N m v ng lý thuy t c b n v c u trúc d li u và gi ế ơ ả ề ấ ữ - Thu t toán đ qui ệ ậ V ch ng trình: ề ươ - Cài đ t c u trúc d li u t ữ ệ ổ ứ - Kh i t o ng u nhiên v trí đ t quân mã đ u tiên. ị ẫ ở ạ ng trình máy tính đ qui theo ki u th sai, vét c n m i kh năng đ tìm - Cài đ t ch ặ ươ c đi k ti p b ng cách ch n m t trong nh ng ô có th đ t quân i: tìm ki m n l i gi ộ ế ả ờ ti p theo mã h p l ấ c sau đó đ n khi tìm th y ợ ệ ế i. i gi m t l ả ộ ờ - Hi n th bàn c sau m i n ị ể ng trình sang file th c thi. - D ch ch ươ ị Ngôn ng l p trình s d ng : C, C ử ụ ữ ậ

Đ TÀI 10:

Ề

BÀI TOÁN PHÂN B KÊNH TRUY N HÌNH T I ĐBSCL

Ố

Ạ

Ề

DÙNG THU T TOÁN TÔ MÀU Đ TH Ồ Ị

Ậ

Đ C T Đ TÀI : Ả Ề

Ặ

ề

Các kênh truy nề

ử

ồ

ằ

ừ ố

ượ

ố s 2 đ n s 13 đ ế ố ử

ề ầ

ạ

ế

ồ

Bài toán (Phân b kênh truy n hình đ ng b ng Sông C u long): ồ c phân chia cho các đài truy n hình các t nh trong vùng đ ng hình t ỉ b ng Sông C u long (Cà Mau, B c Liêu, Sóc Trăng, C n th , Vĩnh long, An giang, Kiên ằ giang, Đ ng tháp, Trà Vinh, B n Tre, Ti n giang, Long An) sao cho không có hai đài phát nào

hai t nh n m c nh nhau trên b n đ đ a lý l

i dùng cùng m t kênh ?

ề ồ ị

ả

ạ

ằ

ạ

ở

ộ

ỉ

YÊU C U C A Đ TÀI : Ủ Ầ Ề

ề

ả

V lý thuy t: ữ

Toán r i r c

ữ ệ ố ờ ạ , Nguy n Đ c Nghĩa, NXB ĐH Qu c

i thu t ậ ứ ễ

ậ

ấ

ứ

ề ươ ữ ệ ổ ứ ồ ị

ướ ạ ươ ứ

ỗ

ỉ

ệ

ỗ

ươ ứ

i d ng file ch a các thông tin v đ th . ề ồ ị ng ng 1 đ nh, m i màu bi u th 1 kênh. Vi c phân ị ể ậ

ồ ị

ầ ượ t

ệ

ng ng v i vi c tô màu đ th (tô màu theo thu t toán Greedy xét l n l ớ các đ nh)

ỉ

i thu t tô màu (hi n th

ng ng)

ự

ệ

ể

ị Tên t nh

ỉ

t và S kênh ươ ứ ố

ậ ng trình sang file th c thi.

ế - N m v ng lý thuy t c b n v c u trúc d li u và gi ế ơ ả ề ấ ắ - Gi i thu t tô màu đ th (giáo trình ậ ồ ị ả Gia TP. H Chí Minh) ồ ng trình : V ch - D li u nh p vào và xu t ra d - T ch c đ th : M i đài phát t chia kênh t theo s th t ố ứ ự - Cài đ t quá trình th c hi n gi ặ - D ch ch ị

ả ự

ươ

Ngôn ng l p trình s d ng : C, C

++ , Visual C++

ử ụ

ữ ậ

Đ TÀI 11:

Ề

Ố

Ạ

Ề

BÀI TOÁN PHÂN B KÊNH TRUY N HÌNH T I MI N Ề ĐÔNG NAM BỘ

DÙNG THU T TOÁN TÔ MÀU Đ TH Ồ Ị

Ậ

Đ C T Đ TÀI : Ả Ề

Ặ

ự

ộ Các kênh truy n hình t

ề

ề ươ

ồ

c) sao cho không có hai đài phát nào

ồ ị

ả

ằ

ạ

ở

ỉ

ướ i dùng cùng m t kênh ?

ộ

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị ừ Bài toán (Phân b kênh truy n hình mi n đông Nam B ): ố ề s 15 đ n s 25 đ c phân chia cho các đài truy n hình các t nh trong vùng mi n đông ế ố ỉ ượ ố Nam B (TP.H Chí Minh, Đ ng Nai, Bà R a – Vũng Tàu, Tây Ninh, Bình D ng, Bình ị ộ Ph hai t nh n m c nh nhau trên b n đ đ a lý l ạ

YÊU C U C A Đ TÀI : Ủ Ầ Ề

ề

ả

V lý thuy t: ữ

Toán r i r c

ữ ệ ố ờ ạ , Nguy n Đ c Nghĩa, NXB ĐH Qu c

i thu t ậ ứ ễ

ậ

ấ

ứ

ề ươ ữ ệ ổ ứ ồ ị

ướ ạ ươ ứ

ỗ

ỉ

ệ

ỗ

ươ ứ

ồ ị

i d ng file ch a các thông tin v đ th . ề ồ ị ng ng 1 đ nh, m i màu bi u th 1 kênh. Vi c phân ị ể ậ

ầ ượ t

ệ

ng ng v i vi c tô màu đ th (tô màu theo thu t toán Greedy xét l n l ớ các đ nh)

ỉ

i thu t tô màu (hi n th

ng ng)

ự

ệ

ể

ị Tên t nh

ỉ

t và S kênh ươ ứ ố

ậ ng trình sang file th c thi.

ế - N m v ng lý thuy t c b n v c u trúc d li u và gi ế ơ ả ề ấ ắ - Gi i thu t tô màu đ th (giáo trình ậ ồ ị ả Gia TP. H Chí Minh) ồ V ch ng trình : - D li u nh p vào và xu t ra d - T ch c đ th : M i đài phát t chia kênh t theo s th t ố ứ ự - Cài đ t quá trình th c hi n gi ặ - D ch ch ị

ả ự

ươ

Ngôn ng l p trình s d ng : C, C

++ , Visual C++

ử ụ

ữ ậ

Đ TÀI 12:

Ề

Ả

Ự

Ồ Ự

ƯỜ NG

Ữ

Ớ

Ế Ồ

Ộ

Ấ

Ể

XÂY D NG B N Đ TR C TUY N NH NG CON Đ Ớ Ệ L N TRONG N I THÀNH TP.H CHÍ MINH V I VI C TÍNH CHI PHÍ TH P NH T Đ DI CHUY N GI A TRUNG Ữ TÂM CÁC QU N.Ậ

Đ C T Đ TÀI : Ả Ề Ặ

ụ ề ồ ị ể ươ ị V n d ng các lý thuy t c b n v đ th đ cài đ t ch ế ơ ả ậ ng đi trên đ th , ki m tra tính liên thông và tìm đ ặ ườ ấ ỉ ườ ồ ị ng trình cho phép xác đ nh ng đi ng n nh t gi a 2 đ nh , m i ỗ ữ ắ i trung tâm Tp.H Chí Minh b ng gi i thu t Dijkstra, Ford- ậ ồ ằ ả con đ ể đ nh là 1 đ a danh c th t ụ ể ạ ị ỉ ng. Bellman trên đ th vô h ướ ồ ị

ữ ng trình: Ph i có nh ng ch c năng c b n sau: ứ ậ ể ể ơ ả  C p nh t d li u v đ th . ậ ữ ệ ề ồ ị  Bi u di n đ th trên màn hình. ồ ị ễ  Ki m tra tính liên thông.  Cho phép tìm đ ng đi ng n nh t gi a 2 đ nh b t kỳ. ườ ắ ữ ấ ấ ỉ

MÔI TR NG CÀI Đ T : ƯỜ Ặ

++

Ngôn ng l p trình s d ng: C hay C ử ụ ữ ậ

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị

ự Đ TÀI 13:

Ề

Ệ Ố

Ế Ố Ạ Ự NG Đ I H C TRONG THÀNH PH V I CHI PHÍ

Ủ Ố Ớ

Ạ Ọ

XÂY D NG H TH NG K T N I M NG C A CÁC TR TH P NH T

Ấ

ƯỜ Ấ Đ C T Đ TÀI : Ả Ề

Ặ

ồ ị ự ế ế ố ng đ i h c, xây d ng ch V n d ng các lý thuy t c b n v đ th đ thi ế ế ễ k t n i các ng trình cho phép bi u di n đ th , ki m tra tính liên thông và ồ ị t k ra đ th th c t ể ề ồ ị ể ể ườ ự tr tìm cây có tr ng l ế ơ ả ươ ng nh nh t b ng gi i thu t Kruscal ho c Prim. ậ ụ ạ ọ ọ ấ ằ ỏ ượ ả ậ ặ

 Các gi ki m tra tính liên thông và gi ể nh nh t. ỏ ấ ữ ng trình: Ph i có nh ng ch c năng c b n sau: ứ ậ ể ể

MÔI TR NG CÀI Đ T : ƯỜ Ặ

Ngôn ng l p trình s d ng: C hay C ử ụ ữ ậ

ĐỀ TÀI 14: BÀI TOÁN ĐƯỜNG ĐI NGƯỜI GIAO HÀNG

Đ C T Đ TÀI

Ả Ề

Ặ

N i dung bài toán: ộ

Xét bài toán r t n i ti ng có tên là bài toán tìm đ ấ ổ ế ườ ườ ườ ộ ng đi c a ng ủ i giao hàng c n đi giao hàng t ầ ố ể ấ ố ố ở ề ả ỗ ố i giao hàng ạ i n m t thành ph nào đó, đi qua các thành ph khác đ giao hàng m t ừ ộ ộ ườ ng ố ế ượ (TSP - Traveling Salesman Problem): Có m t ng thành ph . Xu t phát t ừ ộ và tr ầ ố thành ph đ n các thành ph khác là xác đ nh đ ố đi khép kín th a mãn đi u ki n trên) sao cho t ng đ dài các c nh là nh nh t. ổ ệ ề v thành ph ban đ u. M i thành ph ch đ n m t l n, kho ng cách t ỉ ế c. Hãy tìm m t chu trình (m t đ ị ộ ộ ầ ộ ạ ấ ỏ ỏ

YÊU C U C A Đ TÀI t k gi ế ế ả ữ ệ ậ ậ ỹ Ầ N m v ng c s lý thuy t v c u trúc d li u. Các k thu t thi ắ Ch ươ ế ề ấ ứ Ề ơ ở ầ Ủ ữ ố ng trình c n có các ch c năng sau: Cho phép nh p vào bài toán: s thành ph , ng án tìm i thu t. ố trong t p tin). Xu t ra ph ươ ậ ậ ấ ữ ố kho ng cách gi a các thành ph (có th l y s li u t ả c. N u th hi n d đ ượ ạ ồ ể ấ ố ệ ừ i d ng đ ho càng t t. ố c a các t nh ĐBSCL. ỉ ể ệ ướ ạ ế Mô ph ng th c t ự ế ủ ỏ

MÔT TR NG CÀI Đ T ƯỜ Ặ Ngôn ng l p trình s d ng: C, C++ , Visual C++ ử ụ ữ ậ

ự

Bài t p ậ và th c hành môn lý thuy t đ th ế ồ ị Đ TÀI 15: BÀI TOÁN Đ

NG ĐI NG

I Đ A TH

Ề

ƯỜ

ƯỜ Ư

Ư

Đ C T Đ TÀI

Ả Ề

Ặ

N i dung bài toán: ộ

ườ ư ừ ư ư ệ ấ Xét bài toán v ng ư ầ ề ệ i n i xu t phát sao cho qu ng đ ắ ả ế ấ ở ạ ơ B u đi n Tp. H Chí Minh, anh ta i đ a th , xu t phát t ồ t các b u đi n chính trong n i ô, m i n i đúng 1 l n. Cu i cùng anh ta quay ố ỗ ơ ộ ộ ng mà anh ta đi qua là ng n nh t. Hãy tìm m t ườ ng đi khép kín th a mãn đi u ki n trên) sao cho t ng đ dài các ệ ỏ ấ ổ ề ộ đi đ n t tr l ấ chu trình (m t đ ộ ườ c nh là nh nh t. ấ ạ ỏ

YÊU C U C A Đ TÀI i thu t. ữ ệ ậ ậ ỹ ế ề ấ ứ Ề ơ ở ầ ậ Ủ ữ ng trình c n có các ch c năng sau: Cho nh p vào bài toán: s b u đi n chính t ả t k gi ế ế ả ố ư ả ể ấ ố ệ ừ ữ ặ các qu n, kho ng cách n i gi a các b u đi n (có th l y s li u t sát th c t ). Xu t ra ph c. N u th hi n d ng án tìm đ t. Ầ N m v ng c s lý thuy t v c u trúc d li u. Các k thu t thi ắ Ch ươ ậ ự ế ạ i ệ trong b n đ ho c kh o ả ồ i d ng đ ho càng t ố ồ ể ệ ướ ạ ố ươ ư ượ ệ ế ấ ạ

MÔT TR NG CÀI Đ T ƯỜ Ặ Ngôn ng l p trình s d ng: C, C++ , Visual C++ ử ụ ữ ậ