TÌMKIẾMTRÊNĐỒTHỊ
CHƯƠNG3
TônQuangToại
KhoaCNTT,ĐạihọcNgoạingữ‐ TinhọcTP.HCM
Một số khái niệm
Thuật toán tìm kiếm theo chiều rộng
Thuật toán tìm kiếm theo chiều sâu
Ứng dụng
Nộidung
Đường đi,chu trình
Tính liên thông
2đỉnh liên thông
Đồ thị vô hướng liên thông
Đồ thị có hướng Liên thông mạnh
Miền liên thông
Đỉnh khớp,cạnh cầu
Mộtsốkháiniệm
Đường đi (Path):Đường đi từ đỉnh x đến đỉnh
ytrong đồ thị G=(V,E)là một dãy các đỉnh liên
tiếp nối đỉnh xđến đỉnh y:
ଵ ଶ ௞ trongđó:
ଵ ௞
௜௜ାଵ
Độ dài đường đi:Là số cạnh của đường đi
Đường đi đơn (simple):Là đường đi quamỗi
cạnhtốiđa1lần.
Mộtsốkháiniệm
Chutrình (Cycle):Là đường đi có đỉnh đầu
trùng với đỉnh cuối
Chutrình đơn:Mỗi cạnh xuất hiện tối đa 1lần
trong chu trình
Mộtsốkháiniệm