1
CH NG 6ƯƠ
ĐỒ THỊ
2
Ch ng 6: Đ thươ ồ ị
6.1 Đnh nghĩa và các khái ni mị ệ
6.2 Bi u di n đ thể ễ ồ ị
6.3 Phép duy t đ thệ ồ ị
6.4 Tìm đng đi ng n nh tườ ắ ấ
3
Đ th là m t c u trúc r i r c g m các đnh và ồ ị ộ ấ ờ ạ ồ ỉ
các c nh (vô h ng ho c có h ng) n i các ạ ướ ặ ướ ố
đnh đó .ỉ
Nhi u bài toán thu c nh ng lĩnh v c r t khác ề ộ ữ ự ấ
nhau có th gi i đc b ng mô hình đ th : ể ả ượ ằ ồ ị
bi u di n s c nh tranh các loài trong m t ể ễ ự ạ ộ
môi tr ng sinh thái, hai máy tính có đc ườ ượ
n i v i nhau b ng m t đng truy n thông ố ớ ằ ộ ườ ề
hay không. tìm đng đi ng n nh t gi a hai ườ ắ ấ ữ
thành ph , l p l ch thi, phân chia kênh cho ố ậ ị
các đài truy n hình …ề
6.1-Đnh nghĩa và khái ni mị ệ
4
Khi mô hình hoá b ng đ th : đnh bi u th ằ ồ ị ỉ ể ị
các đi t ng đc xem xét (ng i, t ố ượ ượ ườ ổ
ch c, đa danh,...), c nh đ th là nh ng ứ ị ạ ồ ị ữ
đo n th ng (ho c cong) hay nh ng mũi tên ạ ẳ ặ ữ
n i m t s đi m v i nhau, t ng tr ng ố ộ ố ể ớ ượ ư
cho m t quan h nào đó gi a các đi ộ ệ ữ ố
t ng.ượ
Các lo i đ th :ạ ồ ị
M t đn đ th G = (V, E) g m m t t p ộ ơ ồ ị ồ ộ ậ
khác r ng V mà các ph n t c a nó g i là ỗ ầ ử ủ ọ
các đnh và m t t p E là các c nh g m các ỉ ộ ậ ạ ồ
c p không có th t c a các đnh phân ặ ứ ự ủ ỉ
bi t.ệ
6.1-Đnh nghĩa và khái ni mị ệ
5
M t đn đ th có h ng G = (V, E) g m ộ ơ ồ ị ướ ồ
m t t p khác r ng V mà các ph n t c a ộ ậ ỗ ầ ử ủ
nó g i là các đnh và m t t p E các c p có ọ ỉ ộ ậ ặ
th t g m 2 ph n t khác nhau c a V ứ ự ồ ầ ử ủ
g i là các cung.ọ
M t đa đ th G = (V, E) gi ng nh đn đ ộ ồ ị ố ư ơ ồ
th , có th có c nh b i (có nhi u h n hai ị ể ạ ộ ề ơ
c nh t ng ng v i m t c p đnh) và ạ ươ ứ ớ ộ ặ ỉ
khuyên (c nh n i đnh v i chính nó).ạ ố ỉ ớ
6.1-Đnh nghĩa và khái ni mị ệ