Cơ bản
• Định tuyến là quá trình tìm đường đi giữa hai điểm trong
mạng theo một số yêu cầu cho trước
– Đường đi ngắn nhất ?
– Đường có băng thông rộng nhất ?
• Đường đi phải thường phải tối ưu theo một tiêu chí nào đó
• Các gói tin được gửi đi theo đường đi này. Thực tế chúng
cũng có thể được gửi đi đồng thời trên nhiều đường
A C
E F
S D
1Mbps
3Mbps 3Mbps
4Mbps
B
2Mbps
CuuDuongThanCong.com https://fb.com/tailieudientucntt
cuu duong than cong . com
•graph G=(V, E) được định nghĩa bởi tập hợp các đỉnh
(vertex) Vvà tập hợp các cạnh E (edge). Các đỉnh thường
được gọi là các nút, các cạnh được gọi là các liên kết
• Ký hiệu V={vi| i=1,2,......N}; E={ei| i=1,2,......M}
ej=(vi,vk) hoặc ej=(i,k)
Graph (đồ hình)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
cuu duong than cong . com
Định nghĩa
• Nút kề nhau (láng giềng): nút ivà kgọi là kề nhau nếu tồn tại một liên
kết (i, k) giữa chúng
• Bậc của nút là số lượng liên kết đi tới nút
– Là số lượng nút láng giềng nếu giữa hai nút có không nhiều hơn một liên
kết
• Liên kết có hướng được gọi là cung: ký hiệu: aj=[vi,vk] hoặc aj=[i, k]
CuuDuongThanCong.com https://fb.com/tailieudientucntt
cuu duong than cong . com
Định nghĩa
• Graph gọi là vô hướng nếu chỉ chứa các liên kết vô hướng. Nếu chứa ít
nhất một cung, graph được coi là có hướng.
– Trong nhiều trường hợp, liên kết vô hướng có thể được xem là tập hợp của
hai liên kết có hướng ngược nhau
• Nếu giữa hai nút, tồn tại hai liên kết tách biệt thì chúng được gọi là các
liên kết song song.
– Graph có chứa các liên kết song song được gọi là multigraph
• Vòng lặp: liên kết nối một nút với chính nó
• Đường dẫn (path) giữa hai nút là tập hợp các liên kết nối tiếp nhau
• Chu trình (cycle): là đường dẫn có điểm đầu và cuối trùng nhau
• Graph liên thông (connected graph): giữa hai nút bất kỳ đều tồn tại ít
nhất một đường dẫn
CuuDuongThanCong.com https://fb.com/tailieudientucntt
cuu duong than cong . com
