Ly thuyet do thi

Cam on ban nhieu nha! chuc lop minh thi tot!

Ai có thể cho mình biết tóm tắt phần cần học trong lý thuyết đồ thị không?

Còn 3 ngày nữa để học bài thôi!!!!! Lòng luôn dặn lòng luôn cố gắng, mà sao tối về ngủ khì khì nhỉ..... :

30% là chương 1 hoặc chương 3 (phần viết code), 70% rơi vào 4 thuật giải: 4 Thuật toán: 1.Kruskal; 2. Prim; 3. Dijkstra; 4. Ford – Bellman. Chúc Bạn Học Tốt.

Thuật toán Kruskal
Nội dung của thuật toán như sau:
Xây dựng tập cạnh F của T = (V, F) theo từng bước:
1. Sắp xếp các cạnh của G theo thứ tự trọng số (độ dài) tăng dần
2. Bắt đầu với F= Ø bổ sung dần các cạnh của G vào F với điều kiện không tạo
nên chu trình trong T.
3. Thuật toán dừng lại khi có n-1 cạnh được chọn.
--------------------
Thuật toán Prim
Nội dung của thuật toán như sau:
Xây dựng tập đỉnh T V và tập cạnh F của cây khung T=( T V , F) theo từng bước:
1. Bắt đầu với T V = {s}, một đỉnh bất kỳ và F=.
2. Trong các cạnh có 1 đỉnh  T V và 1 đỉnh  T V chọn cạnh có trọng số nhỏ nhất.
3. Bổ sung cạnh đó vào F và đỉnh tương ứng vào T V
4. Thuật toán dừng lại khi có n-1 cạnh được chọn ( hoặc T V =V )
-------------------------
Tìm ĐƯỜNG ĐI NGẮN NHẤT
Đường đi ngắn nhất từ một đỉnh – Thuật toán Ford-Bellman
-----------------------------
Thuật toán Ford-Bellman dùng để tìm đường đi ngắn nhất từ một đỉnh s đến tất cả
các đỉnh còn lại của đồ thị.
 Ý tưởng thuật toán
Cho đồ thị có hướng, có trọng số G=(V, E). Trọng số các cung của G được tính
như sau:
• TrongSo(u, v) = ∞ nếu (u, v) E.
• TrongSo(u, v) = a(u, v) nếu cung (u, v) E.
Thuật toán tìm đường đi ngắn nhất d(v) từ đỉnh s, v V:
+ Xét u  V. Nếu d(u) + TrongSo(u, v) < d(v) thì ta thay d(v) = d(u) +
TrongSo(u, v).
+ Quá trình này sẽ được lặp lại với tất cả các đỉnh u có thể, với tất cả các đỉnh v
có thể cho đến khi không thể làm tốt hơn các giá trị d(v).
----------------------
Thuật toán Dijkstra
Thuật toán Dijkstra dùng để tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại
trong đồ thị. Thuật toán được áp dụng cho đồ thị có trọng số các cung không âm.
 Ý tưởng thuật toán
 Đầu vào
- Đồ thị có hướng G=(V,E) với n đỉnh.
- s  V là đỉnh xuất phát.
- a[u,v] ≥ 0 với u,v  V là ma trận trọng số
 Đầu ra
- Khoảng cách từ s đến tất cả các đỉnh còn lại d[v], v  V .
- Truoc[v], v  V là đỉnh nằm trước v trong đường đi ngắn nhất từ s đến v.
Các bước thuật toán như sau:
Bước 1: Đặt nhãn cho tất cả các đỉnh trong tập T = V \ {s}
Bước 2: Nếu T =  thì đi đến Bước 5.
Trái lại chọn u  T gần s nhất ( d(u) : min )
Bước 3: Loại u ra khỏi T: T = T \ {u}; Cố định nhãn của u
Khoa Công Nghệ Thông Tin – Đại học SPKT TP.HCM Lý thuyết đồ thị
90
Bước 4: Gán lại nhãn các đỉnh của T (theo đường đi ngắn nhất từ s qua u).
Quay lại Bước2
Bước 5: Xuất các nhãn cố định (chính là khoảng cách ngắn nhất)