Ly thuyet do thi
2 posters
Trang 1 trong tổng số 1 trang
Re: Ly thuyet do thi
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ỉ..... :
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ỉ..... :
Tigon2431- Thành viên mới
- Tổng số bài gửi : 7
Join date : 29/09/2010
Re: Ly thuyet do thi
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.
nhuhaipt2004- Administrator
- Tổng số bài gửi : 96
Join date : 26/08/2010
Re: Ly thuyet do thi
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)
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)
nhuhaipt2004- Administrator
- Tổng số bài gửi : 96
Join date : 26/08/2010
Similar topics
» Ly thuyet đo thi
» Ly thuyet do thi
» Giải Bài Tập Lý Thuyết Đồ Thị Chương I
» Lý Thuyết giao dich va quản lý cạnh tranh (Chương 4)
» Ly thuyet do thi
» Giải Bài Tập Lý Thuyết Đồ Thị Chương I
» Lý Thuyết giao dich va quản lý cạnh tranh (Chương 4)
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết