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

Điều kiện cần và đủ để đồ thị là Euler Đồ thị vô hướng – Đồ thị vô hướng liên thông G= là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Đồ thị có hướng – Đồ thị có hướng liên thông yếu G= là đồ thị Euler khi và chỉ khi tất cả các đỉnh của nó đều có bán đỉnh bậc ra bằng bán đỉnh bậc vào (điều này làm cho đồ thị là liê...

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

Tư tưởng • Trong quá trình tìm kiếm, ưu tiên “chiều sâu” hơn “chiều rộng” – Đi xuống sâu nhất có thể trước khi quay lại • Bắt đầu tại một đỉnh v0 nào đó, chọn một đỉnh u bất kỳ kề với v0 và lấy nó làm đỉnh duyệt tiếp theo. – Cách duyệt tiếp theo được thực hiện tương tự như đối với đỉnh v0 với đỉnh bắt đầu là u. • Để kiểm tra việc duyệt mỗi ...

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

Ưu & nhược điểm của ma trận kề • Ưu điểm – Đơn giản, dễ cài đặt trên máy tính – Sử dụng một mảng hai chiều để biểu diễn ma trận kề – Dễ dàng kiểm tra được hai đỉnh u,v có kề với nhau hay không – Đúng một phép so sánh (a*u+*v+≠0?) • Nhược điểm – Lãng phí bộ nhớ: bất kể số cạnh nhiều hay ít ta cần n2 đơn vị bộ nhớ để biểu diễn – Không thể bi...

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

Quy ước • Ta chủ yếu làm việc với đơn đồ thị vô hướng và đơn đồ thị có hướng. • Khi viết “đồ thị vô hướng” ta hiểu là “đơn đồ thị vô hướng”. • Khi viết “đồ thị có hướng” ta hiểu là “đơn đồ thị có hướng”. 10Một số thuật ngữ cơ bản trên đồ thị vô hướngBậc của đỉnh • ĐN 1. Hai đỉnh u và v của đồ thị vô hướng G = được gọi là kề nhau ...

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

Nội dung (1/2) 1. KHÁI NIỆM VỀ ĐỒ THỊ – Định nghĩa đồ thị – Một số thuật ngữ trên đồ thị vô hướng – Một số thuật ngữ cơ bản trên đồ thị có hướng – Một số dạng đồ thị đặc biệt 2. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH – Biểu diễn đồ thị bằng ma trận kề – Biểu diễn đồ thị bằng danh sách cạnh – Biểu diễn đồ thị bằng danh sách kề 3. TÌM KIẾM TRÊN ĐỒ ...

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

IV. GIẢI PTVP TUYẾN TÍNH CẤP 2 BẰNG PP SAI PHÂN HỮU HẠN : Xét phương trình vi phân tuyến tính cấp 2 với điều kiện biên p(x)y” + q(x)y’ + r(x)y = f(x), a≤x≤b y(a) = α, y(b) = β ❖ PP sai phân hữu hạn : ▪ Chia đoạn [a,b] thành n đoạn bằng nhau với bước h=(b-a)/n và các điểm nút x 0 = a, x1 = x0 +h, . , xk = x0 + kh, . , xn = b

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

Ví dụ : Xét tích phân xác định số đoạn chia tối thiểu n để sai số ≤10-5 giải a.Dùng công thức hình thang mở rộng b.Dùng công thức Simpson mở rộng. Với n vừa tìm được, hãy xấp xỉ tích phân trên

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

V. BÀI TOÁN XẤP XỈ THỰC NGHIỆM : Trong thực tế, các giá trị yk được xác định thông qua thực nghiệm hay đo đạc nên thường thiếu chính xác. Khi đó việc xây dựng một đa thức nội suy đi qua tất cả các điểm Mk(xk, yk) cũng không còn chính xác

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

2. Phương pháp Gauss : Ta sử dụng các phép biến đổi sơ cấp theo dòng để chuyển ma trận A về ma trân tam giác trên Các phép biến đổi sơ cấp theo dòng ➢ hoán chuyển 2 dòng ➢ nhân 1 dòng với 1 số khác 0 ➢ cộng 1 dòng với dòng khác

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

Ví dụ : Xét phương trình x = cosx trên khoảng cách ly nghiệm [0,1] Giả sử chọn giá trị ban đầu x o = 1. Xác định số lần lặp n khi xấp xỉ nghiệm pt với sai số 10-8 (dùng công thức tiên nghiệm) Giải a. g(x)=cosx g’(x)=-sinx g(x) là hàm co với hệ số co q = sin1≈0.8415 < 1 Mặt khác g(x) =cos x ∈[0,1] nên pp lặp hội tụ

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