Ly thuyet do thi

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Ly thuyet do thi

Bài gửi by Nhoc_DL on Tue 28 Sep 2010, 7:25 pm

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

Nhoc_DL
Khách viếng thăm


Về Đầu Trang Go down

Re: Ly thuyet do thi

Bài gửi by Tigon2431 on Wed 29 Sep 2010, 4:14 pm

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ỉ..... Sleep Sleep : Rolling Eyes Rolling Eyes

Tigon2431
Thành viên mới
Thành viên mới

Tổng số bài gửi : 7
Join date : 29/09/2010

Về Đầu Trang Go down

Re: Ly thuyet do thi

Bài gửi by nhuhaipt2004 on Thu 30 Sep 2010, 7:32 am

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
Administrator

Tổng số bài gửi : 96
Join date : 26/08/2010

Về Đầu Trang Go down

Re: Ly thuyet do thi

Bài gửi by nhuhaipt2004 on Thu 30 Sep 2010, 7:36 am

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)

nhuhaipt2004
Administrator
Administrator

Tổng số bài gửi : 96
Join date : 26/08/2010

Về Đầu Trang Go down

Re: Ly thuyet do thi

Bài gửi by Sponsored content


Sponsored content


Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết