Về Chương 5
Bản Đồ Đồ Thị
BẢN ĐỒ ĐỒ THỊ
GRAPH CONCEPTS
G = (V, E) — tập đỉnh V và tập cạnh E
👁 Xem
✏️ + Cạnh
🗑️ Xóa đỉnh
Có hướng
Thêm đỉnh
A
2
B
3
C
2
D
1
E
2
Đỉnh |V|
5
Cạnh |E|
5
Hướng
Không
Mật độ
50%
📚 Các Loại Đồ Thị
🔗 Vô Hướng
Cạnh không có chiều
➡️ Có Hướng (Digraph)
Cạnh chỉ đi 1 chiều
⚖️ Có Trọng Số
Cạnh có giá trị số
🌐 Đầy Đủ
Mọi cặp đỉnh có cạnh
📐 Khái Niệm
Bậc (degree):
Số cạnh tại đỉnh
Lân cận:
Đỉnh kề nhau
Đường đi:
Chuỗi đỉnh qua cạnh
Chu trình:
Đường đi khép kín
Liên thông:
Mọi cặp đỉnh có đường đi
🎯 Ứng Dụng
🗺️ Bản đồ, định tuyến
🌐 Mạng xã hội
🔌 Mạng máy tính
⚙️ Phụ thuộc module