Khoa Công Nghệ Thông Tin -Trường Đại học Ngân hàng TP.HCM
Chương 5: Đồthị
Khoa Công Nghệ Thông Tin -Trường Đại học Ngân hàng TP.HCM
2
Trình bày những kiếnthứccăn bản vềlý thuyếtđồ
thị, cách biểudiễn, một sốthuật toán trên đồthị
Đánh giá thuật toán
Một số ứng dụng củađồthị
Mục tiêu
Khoa Công Nghệ Thông Tin -Trường Đại học Ngân hàng TP.HCM
3
Boston
Hartford
Atlanta
Minneapolis
Austin
SF
Seattle
Anchorage
Định nghĩa
Khoa Công Nghệ Thông Tin -Trường Đại học Ngân hàng TP.HCM
4
ĐồthịG = (V,E)
V = tập hợp hữu hạn các phần tử(đỉnh hay nút)
EV×V, tập hữu hạn các cạnh (cung)
ab
c
de
Cung
Đỉnh
Định nghĩa
Khoa Công Nghệ Thông Tin -Trường Đại học Ngân hàng TP.HCM
5
Nếu (x,y) E
x gọilà đỉnh gốc, ylà ngọn
Nếu x ≡y, (x,y) gọilà khuyên
Mộtdãy u1, u2,…, un,uiV (i=1,n) gọilà mộtđường, nếu
(ui-1,ui)E
Độdài đường: length(u1,u2,…,un)=n
(u1,u2,…,un)đường đi đơn, nếu ui≠uj, 1<i≠j<n (là đường đi,
mà các đỉnh phân biệt, ngoạitrừđình đầu và đỉnh cuối)
Các khái niệm