Đồ thị - 2
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (454.29 KB, 19 trang )
ðồ thị
(Graph)(Graph)
Lê Sỹ Vinh
Bộ môn Khoa Học Máy Tính – Khoa CNTT
ðại Học Công Nghệ - ðHQGHN
Email:
Đồ thị (graph)
• G = (V, E)
– V: Tập ñỉnh
– E = { (u,v) | u, v ∈ V}: Tập cạnh
Ví dụ: Biểu diễn bản ñồ ñường ñi trong thành phố bằng ñồ thị G = (V, E)
– V: Tập hợp các ñiểm trong thành phố
– E: Tập hợp các ñường ñi trong thành phố, mỗi ñường ñi nối hai ñiểm
ðồ thị có hướng và không có hướng
(directed and undirected graph)
G = (V, E) là ñồ thị không có hướng nếu (u, v) ∈ E thì (v, u) ∈ E
ðồ thị có trọng số và không có trọng số
(weighted and unweighted graph)
G = (V, E) là ñồ thị có trọng số nếu mỗi cạnh (u, v) ∈ E ñược gán một
giá trị
