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
CH NG 2: Đ TH EULER VÀ Đ TH HAMILTON ƯƠ Ồ Ị Ồ Ị ...............................9
CH NG 3ƯƠ
Đ TH CÓ TR NG S VÀ Đ NG ĐI NG N NH TỒ Ị Ọ Ố ƯỜ Ắ Ấ ..............................13
.........................................................................................................................................................14
CH NG 4: CÂY ƯƠ ...............................................................................................17
Vi t ti u lu nế ể ậ ..............................................................................................................................24
Đ TÀI 1:Ề..............................................................................................................................24
S D NG PH NG PHÁP Đ TH Đ TH HI N VI C B TRÍ L CH THI CHOỬ Ụ ƯƠ Ồ Ị Ể Ể Ệ Ệ Ố Ị
SINH VIÊN KHOA TOÁN – TIN H C. Ọ...............................................................................24
Đ TÀI 2:Ề..............................................................................................................................25
S D NG PH NG PHÁP Đ TH Đ GI I BÀI TOÁN DÂN GIAN (BÀI TOÁN 1).Ử Ụ ƯƠ Ồ Ị Ể Ả . .25
Đ TÀI 3: Ề.............................................................................................................................25
S D NG PH NG PHÁP Đ TH Đ GI I BÀI TOÁN DÂN GIAN (BÀI TOÁN 2).Ử Ụ ƯƠ Ồ Ị Ể Ả . .25
Đ 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
1
XÂY D NG B N Đ TR C TUY N NH NG CON Đ NG 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.Ữ Ậ ........................................................................................31
Đ TÀI 13: Ề...........................................................................................................................32
XÂY D NG H TH NG K T N I M NG C A CÁC TR NG Đ I H C TRONGỰ Ệ Ố Ế Ố Ạ Ủ ƯỜ Ạ Ọ
THÀNH PH V I CHI PHÍ TH P NH T Ố Ớ Ấ Ấ .........................................................................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
2
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ụ ự ế
Bài 1.1. V i m i tr ng h p sau, v các mô hình đ th bi u di n các đ ng bay và nóiớ ỗ ườ ợ ẽ ồ ị ể ễ ườ
rõ v lo i đ th đ 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.ồ ị ể ễ ố ế ữ
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 t ng m c nh thành ph , c t và h cánh t i Phú Qu c.ể ị ế ị ặ ệ ắ ả ố ấ ạ ạ ố
c) Đ th bi u di n đ y đ thông tin v h ng bay và s chuy n bay gi a các thànhồ ị ể ễ ầ ủ ề ướ ố ế ữ
ph .ố
Ph n h ng d nầ ướ ẫ
a) Đ th vô h ngồ ị ướ
b) Đa đ th vô h ngồ ị ướ
c) Đa đ th có h ngồ ị ướ
3
Phú Qu cốNgh Anệ
Hà N iộ
H i PhòngảĐà N ngẵ
TP. HCM
Phú Qu cốNgh Anệ
Hà N iộ
H i PhòngảĐà N ngẵ
TP. HCM
Bài t p ậvà th c hành môn lý thuy t đ thự ế ồ ị
Bài 1.2. Xác đ nh xem đ th nào sau đây là đ th đ n, đa đ th , đ th có h ng. ị ồ ị ồ ị ơ ồ ị ồ ị ướ
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óộ ộ ắ ộ ế ả ằ ộ ồ ị
h ng…ướ
2 Các thu t ng đ thậ ữ ồ ị
Bài 2.1. Xác đ nh ịs l ng các đ nh, ố ượ ỉ s ốl ng các c nh, và b c c a các đ nh trong cácượ ạ ậ ủ ỉ
đ th ồ ị sau. Cho bi t đ nh nào là đ nh cô l p, đ nh nào là ế ỉ ỉ ậ ỉ đ nh ỉtreo.
4
Phú Qu cốNgh Anệ
Hà N iộ
H i PhòngảĐà N ngẵ
TP. HCM
a)
b)
c)
d)
c
a
f e d
a)
b a
ed c
b)
b
b
h g e
c)
c d
i
f
a