- Trang chủ
- Về Blog
- Liên hệ
| Note |  |
Home - Thi thử online
- Tiếng Anh
- _Lớp 12
- _Lớp 11
- _Lớp 10
- Toán học
- _Lớp 12
- _Lớp 11
- _Lớp 10
- Văn học
- _Lớp 12
- _Lớp 11
- _Lớp 10
- Vật lý
- _Lớp 12
- _Lớp 11
- _Lớp 10
- Hóa học
- _Lớp 12
- _Lớp 11
- _Lớp 10
- Đáp án đề thi
- _Toán học 2020
- _Văn học 2020
- _Tiếng Anh 2020
- _Hóa học 2020
- _Vật lý 2020
Home /
Toán rời rạc 2 /
Gợi ý giải đề thi môn Toán rời rạc 2(Đề 1) Gợi ý giải đề thi môn Toán rời rạc 2(Đề 1)
Việt Hoàng 5/24/2019 Toán rời rạc 2 
Gợi ý:
Đề số 1 Câu 1: a, deg(1)=3deg(5)=2 deg(2)=2deg(6)=4 deg(3)=3deg(7)=3 deg(4)=3deg(8)=2 b, | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 3 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 4 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 6 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 7 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
c, | Đỉnh đầu | Đỉnh cuối | Đỉnh đầu | Đỉnh cuối |
| 1 | 2 | 4 | 6 |
| 1 | 3 | 5 | 6 |
| 1 | 4 | 5 | 7 |
| 2 | 3 | 6 | 7 |
| 3 | 4 | 6 | 8 |
| 7 | 8 |
Câu 2: a, BFS(7)={7(0),5(7),6(7),8(7),4(6),1(4),3(4),2(1)} Đường đi từ đỉnh 7 -> đỉnh 2: 7à6à4à1à2 b, BFS(1)={1(0),2(1),3(1),4(1),6(4),5(6),7(6),8(6)}=V àSố thành phần liên thông: k=1 | Đỉnh u | Số TPLT l của G/{u} | l>k | Đỉnh trụ |
| 1 | DFS(2)={2(0),3(2),4(3),6(4),5(6),7(6),8(6)} àl=1 | No | ------ |
| 4 | DFS(1)={1(0),2(1),3(1)} DFS(5)={5(0),6(5),7(5),8(6)} àl=2 | Yes | 4 |
| 6 | DFS(1)={1(0),2(1),3(1),4(1)} DFS(5)={5(0),7(5),8(7)} àl=2 | Yes | 6 |
KL:Đỉnh 4,6 là các đỉnh trụ Câu 3: a, Input: Cho đồ thị G=(V,E) gồm n đỉnh biểu diễn bởi ma trận kề Output: Tìm chu trình Euler của đồ thị G bắt đầu từ đỉnh u. (1): Kiểm tra G có thỏa mãn điều kiện hay không Nếu G không thỏa mãn điều kiện thì kt=0 Nếu có chu trình Euler thì kt=1 (2):Nếu kt=0 => thông báo đồ thị không có chu trình Euler và dừng Nếu kt=1 =>Chọn u là đỉnh cho trước và chuyển sang (3) (3): Xây dựng chu trình Euler trong G (3.1) Tạo mảng CE để ghi chu trình Euler vào stack để xếp các đỉnh sẽ xét.Xếp đỉnh u và stack (3.2)Xét đỉnh v nằm trên cùng của Stack và thực hiện: - Nếu v là đỉnh cô lập thì lấy v ra khỏi Stack và đưa vào CE - Nếu v có đỉnh kề là x thì đưa x vào Stack sau đó xóa cạnh nối v với x (3.3)Quay lại (3.2) cho tới khi Stack rỗng (4)Xuất chi trình EULER chứa trong CE theo thứ tự ngược lại b, BFS(1)={1(0),2(1),3(1),5(1),6(1),7(3),8(3),4(5),9(7)}=V => G liên thông 1 Tính bậc của các đỉnh: Deg(1)=4 Deg(2)=2 Deg(3)=4 Deg(4)=2 Deg(5)=4 Deg(6)=4 Deg(7)=4 Deg(8)=4 Deg(9)=2 => Tất cả 9 đỉnh đều có bậc chẵn 2 àG là đồ thị EULER Chu trình EULER của đồ thị G bắt đầu từ đỉnh 1 | Bước | Stack | CE |
| 1 | 1,2,3,1,5,4,6,1 | Ø |
| 2 | 1,2,3,1,5,4,6,5,7,3,8,6 | 1 |
| 3 | 1,2,3,1,5,4,6,5,7,3,8,7,9,8 | 1,6 |
| 4 | 1,2,3,1,5,4,6,5,7,3,8,7,9 | 1,6,8 |
| 5 | Ø | 1,6,8,9,7,8,3,7,5,6,4,5,1,3,2,1 |
KL: Chu trình EULER bắt đầu từ đỉnh 1: 1-2-3-1-5-4-6-5-7-3-8-7-9-8-6-1 Câu 4: a,Thuật toán xây dựng cây khung nhỏ nhất H=<V,T>: Bước 1: Khởi tạo T= Ø;//Khởi tạo tập cạnh cây khung là Ø d(H)=0;//Khởi tạo độ dài nhỏ nhất của cây khung là 0 Bước 2: Sắp xếp <Sắp xếp các cạnh của đồ thị theo thứ tự tăng dần trọng số> Bước 3:Lặp While(|T|<n-1&&E‡ Ø){ e=<Cạnh có độ dài nhỏ nhất>; E=E\{e}; If(T∪{e} không tạo nên chu trình) then{ T=T ∪{e}; d(H)=d(H)+d(e); } Endif; } Endwhile; Bước 4: Trả lại kết quả If(|T|<n-1) then(Đồ thị không liên thông) Else return (T,d(H)) b, n=9 Sắp xếp thứ tự các cạnh theo thứ tự tăng dần của trọng số: (1,2)<=(2,3)<=(3,7)<=(6,8)<=(1,3)<=(4,6)<=(5,7)<=(1,5)<=(1,6)<=(3,8)<=(7,9)<=(4,5)<=(5,6)<=(7,8)<=(8,9) | Cạnh ei | T∪ei chứa chu trình | T | WT | k |
| (1,2) | No | (1,2) | 1 | 1 |
| (2,3) | No | (2,3) | 2 | 2 |
| (3,7) | No | (3,7) | 3 | 3 |
| (6,8) | No | (6,8) | 4 | 4 |
| (1,3) | Yes | ---- | --------- | --------- |
| (4,6) | No | (4,6) | 6 | 5 |
| (5,7) | No | (5,7) | 8 | 6 |
| (1,5) | Yes | ------- | -------- | --------- |
| (1,6) | No | (1,6) | 11 | 7 |
| (3,8) | Yes | ------ | ---------- | ---------- |
| (7,9) | No | (7,9) | 14 | 8 |
KL: WTmin=14 T={(1,2),(2,3),(3,7),(6,8),(4,6),(5,7),(1,6),(7,9)} Câu 5: | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 4 | 1 | ¥ | ¥ |
| 2 | ¥ | 0 | ¥ | 3 | 1 |
| 3 | ¥ | 2 | 0 | ¥ | 5 |
| 4 | ¥ | ¥ | 3 | 0 | 3 |
| 5 | ¥ | ¥ | ¥ | ¥ | 0 |
| Các bước thực hiện thuật toán Dijkstra tại s=1 |
| Bước | Đỉnh 1 | Đỉnh 2 | Đỉnh 3 | Đỉnh 4 | Đỉnh 5 |
| 1 | <0,1> | <4,1> | <1,1> | <¥,1> | <¥,1> |
| 2 | <3,3> | <1,1> | <¥,1> | <6,3> |
| 3 | <3,3> | <6,2> | <4,2> |
| 4 | <6,2> | <4,2> |
| 5 | <6,2> |
KL: Đường đi ngắn nhất từ đỉnh 1->2: 1à3à2(Độ dài 3) Đường đi ngắn nhất từ đỉnh 1->3: 1à3 (Độ dài 1) Đường đi ngắn nhất từ đỉnh 1->4: 1à3à2à4(Độ dài 6) Đường đi ngắn nhất từ đỉnh 1->5: 1à3à2à5 (Độ dài 4) Tải đề thi: Tải về *Chú ý: Gợi ý tại mỗi đề chỉ mang tính chất tham khảo rất mong sự góp ý của mọi người để có lời giải hoàn thiện và chính xác nhất. >>Xem thêm Gợi ý giải đề thi môn Toán rời rạc 2(Đề 2) Gợi ý giải đề thi môn Toán rời rạc 2(Đề 3) Nếu thấy tài liệu có ích hi vọng các bạn ủng hộ trang web bằng cách like và theo dõi địa chỉ page chính thức củaTài Liệu Blog tại đây nhé: https://www.facebook.com/TaiLieuBlog/ 💰Ủng hộ blog: https://unghotoi.com/1546792457ngwn4 Bài viết liên quan
Toán rời rạc 2
Nhận xét
Không có nhận xét nào
Đăng ký: Đăng Nhận xét ( Atom )
Facebook
Tài Liệu Blog
Bài viết phổ biến
-
14 cách mở bài, kết bài siêu hay môn Văn tạo ấn tượng với người chấm thi THPT quốc gia Ngữ Văn là môn thi bắt buộc trong kỳ thi THPT quốc gia 2019. Đây cũng là môn tự luận duy nhất nên khiến nhiều thí sinh e ngại. Tài Liệu... -
Sơ đồ tư duy ngữ văn 11-Thầy Nhật dạy văn Sơ đồ tư duy ngữ văn 11 THÔNG TIN TÀI LIỆU: · Tên File: Sơ đồ tư duy Ngữ Văn 11 · Nguồn : Phạm Minh Nhật · ... -
Các công thức giải nhanh trong Hóa Học Các công thức giải nhanh trong Hóa Học Tài Liệu Blog chia sẻ với các bạn đọc tổng hợp các công thức giải nhanh hóa học 12 cơ bản. Các ... -
Sơ đồ tư duy kiến thức giải tích 12-thầy Nguyễn Thanh Tùng Có thể thấy, trong đề thi THPT Quốc gia những câu hỏi liên quan đến kiến thức Giải tích luôn chiếm số lượng lớn. Nguyên nhân là bởi nó ...
Nhãn
- Toán học 12
- Tiếng Anh 12
- Hóa học 12
- Văn học 12
- Vật lý 12
- Toán rời rạc 2
- Sinh học 2019
- Giáo trình đại học
- Sách kĩ năng
- Kiến trúc máy tính
- Địa lý 12
- Toán học 10
- Toán học 11
- ABOUT US
Lịch sử bài đăng
Lịch sử bài đăng tháng 9 (1) tháng 8 (3) tháng 7 (1) tháng 5 (1) tháng 4 (3) tháng 3 (4) tháng 2 (2) tháng 12 (2) tháng 11 (6) tháng 10 (4) tháng 9 (11) tháng 8 (5) tháng 7 (3) tháng 6 (21) tháng 5 (25) tháng 4 (9) tháng 3 (13) tháng 2 (9) tháng 1 (11) tháng 12 (28) tháng 11 (36) tháng 10 (95) tháng 9 (24) tháng 8 (60) tháng 7 (4)
Bài viết ngẫu nhiên
Bài viết gần đây
Thông tin liên hệ
HỢP TÁC NỘI DUNG
Điện thoại: 0945928233
E-mail: tailieublog99@gmail.com
��Ủng hộ blog:https://unghotoi.com/1546792457ngwn4
|2019 Tài Liệu Blog
