Note Đóng lại

GỢI Ý GIẢI ĐỀ THI MÔN TOÁN RỜI RẠC 2(ĐỀ 2)

5/27/2019
Đề số 2


Câu 1:
Gợi ý:
a,
deg(1)=3
deg(2)=3
deg(3)=3
deg(4)=4
deg(5)=3
deg(6)=4
deg(7)=3
deg(8)=3
b,
1
2
3
4
5
6
7
8
1
0
1
1
1
0
0
0
0
2
1
0
1
1
0
0
0
0
3
1
1
0
1
0
0
0
0
4
1
1
1
0
0
1
0
0
5
0
0
0
0
0
1
1
1
6
0
0
0
1
1
0
1
1
7
0
0
0
0
1
1
0
1
8
0
0
0
0
1
1
1
0

c,
Đỉnh đầu
Đỉnh cuối
Đỉnh đầu
Đỉnh cuối
1
2
5
6
1
3
5
7
1
4
5
8
2
3
6
7
2
4
6
8
3
4
7
8
4
6



Câu 2:
Gợi ý:
a,
DFS(8)={8(0),5(8),6(5),4(6),1(4),2(1),3(2),7(6)}
Đường đi từ đỉnh 8 -> đỉnh 2:  8à5à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
Cạnh e
Số TPLT l của G/{e}
l>k
Cạnh cầu
(3,4)
BFS(1)={1(0),2(1),3(1),4(1),6(4),5(6),7(6),8(6)}
àl=1
No
------
(4,6)
BFS(1)={ {1(0),2(1),3(1),4(1)}
BFS(5)={5(0),6(5),7(5),8(5)}
àl=2
Yes
(4,6)
(6,7)
BFS(1)={1(0),2(1),3(1),4(1),6(4),5(6),8(6),7(5)}
àl=1
No
----


Câu 3:
Gợi ý:
a,
Thuật toán EULER-CYCLE(u):
Bước 1: Khởi tạo
stack= Ø;//Khởi tạo một stack bắt đầu là Ø
CE= Ø;//Khởi tạo một mảng CE bắt đầu Ø
Push(u,stack);//Đẩy đỉnh u vào ngăn xếp
Bước 2: Lặp
While(stack ‡ Ø){//Lặp đến khi stack rỗng
s=get(stack);//Lấy đỉnh đầu ở ngăn xếp
if(Ke(s) ‡ Ø){//Nếu danh sách Ke(s) chưa rỗng
            t=<Đỉnh đầu trong danh sách Ke(s)>;
            Push(t,stack);//Đẩy đỉnh t vào stack
            E=E/(s,t);//Loại bỏ cạnh (s,t)
}
{
            s=pop(stack);//Đưa s ra khỏi ngăn xếp
            s=>CE;//Đưa s vào mảng CE
}
}
Bước 3: Trả lại kết quả
<Lật ngược các đỉnh trong mảng CE nhận được chu trình EULER>;
b,
1
2
3
4
5
6
7
8
9
1
0
1
0
1
1
1
0
0
0
2
1
0
1
1
0
0
0
0
1
3
0
1
0
1
0
0
1
0
1
4
1
1
1
0
0
0
1
0
0
5
1
0
0
0
0
1
0
0
0
6
1
0
0
0
1
0
0
0
0
7
0
0
1
1
0
0
0
1
1
8
0
0
0
0
0
0
1
0
1
9
0
1
1
0
0
0
1
1
0

b,
BFS(1)={1(0),2(1),4(1),5(1),6(1),3(2),9(2),7(4),8(9)}=V
èG liên thông (1)
Tính bậc của các đỉnh:
deg(1)=4
deg(2)=4
deg(3)=4
deg(4)=4
deg(5)=2
deg(6)=2
deg(7)=4
deg(8)=2
deg(9)=4
èTất cả 9 đỉnh đều có bậc chẵn (2)
(1),(2) àG là đồ thị EULER
Tìm chu trình EULER bắt đầu từ đỉnh u=1
Bước
Stack
CE
1
1,2,3,4,1,5,6,1
Ø
2
1,2,3,4,2,9,3,7,4
1,6,5,1
3
Ø
1,6,5,1,4,7,9,8,7,3,9,2,4,3,2,1

KL: Chu trình EULER: 1-2-3-4-2-9-3-7-8-9-7-4-1-5-6-1
Câu 4:
Gợi ý:
a,
Thuật toán Prim:
Bước 1:Khởi tạo
VH={s};//Tập đỉnh cây khung thiết lập ban đầu là s
V=V\{s};//Tập đỉnh V được bớt đi s
T= Ø;//Khởi tạo tập cạnh cây khung ban đầu là Ø
d(H)=0;//Khởi tạo độ dài cây khung là 0
Bước 2:Lặp
While(V‡ Ø){
e=<u,v>;//e là cạnh có độ dài nhỏ nhất TM u € V,v € VH
d(H)=d(H)+d(e);//Thiết lập độ dài cây khung nhỏ nhất
T=T◡e;//Kết nạp cạnh e vào cây khung
VH=VH◡u;//Tập đỉnh VH thêm vào đỉnh u
V=V\{u};//Tập đỉnh V bớt đi đỉnh u
}
Bước 3: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=1
Lập bảng:
Bước
d[1][1]
d[2][2]
d[3][3]
d[4][4]
d[5][5]
d[6][6]
d[7][7]
d[8][8]
d[9][9]
1
0|0
1|1
¥|1
2|1
5|1
4|1
¥|1
¥|1
¥|1
2

1|1
1|2
2|1
5|1
4|1
¥|1
¥|1
1|2
3


1|2
1|3
5|1
4|1
5|3
¥|1
1|2
4



1|3
5|1
4|1
1|4
¥|1
1|2
5




5|1
4|1
1|4
4|7
1|2
6




5|1
4|1

3|9
1|2
7




5|1
4|1

3|9

8




2|6
4|1



9




2|6





KL: T={(1,2),(2,3),(3,4),(5,6),(1,6),(4,7),(8,9),(2,9)}
WT=1+1+1+2+4+1+3+1=14
Câu 5:
Gợi ý:
a,
1
2
3
4
5
1
0
5
1
¥
¥
2
¥
0
¥
1
4
3
¥
2
0
¥
6
4
¥
¥
¥
0
2
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>
<5,1>
<1,1>
<¥,1>
<¥,1>
2

<3,3>
<1,1>
<¥,1>
<7,3>
3

<3,3>

<4,2>
<7,3>
4



<4,2>
<6,4>
5




<6,4>
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 4)
Đường đi ngắn nhất từ đỉnh 1->5: 1à3à2à4à5(độ dài 6)

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.

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ủa Tài Liệu Blog tại đây nhé: https://www.facebook.com/TaiLieuBlog/

Nhận xét

Không có nhận xét nào

Đăng ký: Đăng Nhận xét ( Atom )