TimTaiLieu.vn - Tài liệu, ebook, giáo trình, đồ án, luận văn

Thuật toán Ford-Fulkerson: Để tìm luồng cực đại của mạng vận tải G, xuất phát từ luồng tuỳ ý ϕ của G, rồi nâng luồng lên đầy, sau đó áp dụng thuật toán Ford-Fulkerson theo 3 bước: Bước 1 (đánh dấu ở đỉnh của mạng): Lối vào v0 được đánh dấu bằng 0. 1) Nếu đỉnh vi đã được đánh dấu thì ta dùng chỉ số +i để đánh dấu cho mọi đỉnh y chưa được đánh...

15 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 313 | Lượt tải: 0

5.2. Thuật toán gán nhãn (1/4) – Thuật toán được mô tả như sau: – Từ ma trận trọng số A[u,v], u,v∈V, tìm cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v∈V. – Nếu thấy d[u] + A[u,v] < d[v] thì d[v] = d[u] + A[u, v] (làm tốt lên giá trị của d[v]) – Quá trình sẽ kết thúc khi không thể làm “tốt lên” được nữa. – Khi đó d[v] sẽ cho ta g...

13 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 322 | Lượt tải: 0

2. Cây khung và bài toán tìm cây khung nhỏ nhất: Định nghĩa: Trong đồ thị liên thông G, nếu ta loại bỏ cạnh nằm trên chu trình nào đó thì ta sẽ được đồ thị vẫn là liên thông. Nếu cứ loại bỏ các cạnh ở các chu trình khác cho đến khi nào đồ thị không còn chu trình (vẫn liên thông) thì ta thu được một cây nối các đỉnh của G. Cây đó gọi là cây ...

13 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 478 | Lượt tải: 0

1.Đồ thị EULER:  Bài toán người phát thư Trung Hoa (Guan 1960): Một NV đi từ Sở BĐ, qua một số đường phố để phát thư, rồi quay về Sở. Phải đi qua các đường theo trình tự nào để đường đi là ngắn nhất? Xét bài toán: Cho đồ thị liên thông G. Một chu trình qua mọi cạnh của G gọi là một hành trình trong G. Hãy tìm hành trình ngắn nhất (qua ít cạ...

18 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 388 | Lượt tải: 0

2. Duyệt đồ thị theo chiều rộng (BFSBreadth First Search) * Ý tưởng: -Từ đỉnh v nào đó chưa thăm, thăm v, cất tất cả các đỉnh u (chưa thăm) kề với v vào hàng đợi. Lấy từ hàng đợi một đỉnh u, thăm u, rồi lại cất tất cả các đỉnh t (chưa thăm) kề với u vào hàng đợi Thuật toán lặp lại việc thăm cho tới khi hàng đợi rỗng. - Nếu tại một đỉnh x n...

10 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 373 | Lượt tải: 0

Định nghĩa 2 (Đa đồ thị).  Đa đồ thị vô hướng G= (V, E) bao gồm V là tập các đỉnh khác rỗng, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp (bội hay song song) nếu chúng cùng tương ứng với một cặp đỉnh.  Mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào cũ...

38 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 754 | Lượt tải: 0

CÁC KIẾN THỨC CẦN CÓ • Giống như đối với tích phân kép, sinh viên cần có các kiến thức cơ bản về giải tích, đặc biệt là phép tính tích phân hàm một biến số. • Bên cạnh đó, sinh viên cũng cần có các kiến thức về hình học phẳng, hình học không gian. 5HƯỚNG DẪN HỌC • Xem bài giảng đầy đủ và tóm tắt những nội dung chính của từng bài. • Tích cự...

38 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 423 | Lượt tải: 0

TÓM TẮT. Tích phân Gaussian là một phần không thể thiếu khi tính toán ma trận độ cứng cũng như vec tơ lực trong hầu hết các phương pháp số. Phần tứ giác bậc cao (Q8 và Q9) trong FEM cần số điểm tích phân tối thiểu Gaussian 3×3 trong khi phần tử lập phương bậc cao (HH20) thì cần tối thiểu 3×3×3 để đảm bảo sự ổn định và tính chính xác. Tuy nhiên, t...

5 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 257 | Lượt tải: 0

Câu I (4,5 điểm) 1. Một kiện hàng chứa 10 sản phẩm loại I, 12 sản phẩm loại II và 8 sản phẩm loại III. Sinh viên A lấy ngẫu nhiên 4 sản phẩm từ kiện hàng này, sau đó sinh viên B lấy tiếp ngẫu nhiên 4 sản phẩm từ các sản phẩm còn lại trong kiện hàng này. Tính xác suất sinh viên A hoặc sinh viên B lấy được ít nhất 1 sản phẩm loại I. 2. Dây chuyề...

2 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 297 | Lượt tải: 0

Câu 1: Nắm vững phép toán ma trận, tính được định thức và ứng dụng, tìm ma trận đảo v ứng dụng, biết và thực hiện các cách giải hệ phương trình tuyến tính và ứng dụng. Câu 2: Tìm được trị riêng, vectơ riêng và ứng dụng giải hệ phương trình vi phân (hoặc giải bằng biến đổi Laplace). Nhận dạng được các bài toán trong thực tế được mô hình bởi hệ ...

2 trang | Chia sẻ: thanhle95 | Ngày: 15/07/2021 | Lượt xem: 539 | Lượt tải: 0