GỢI Ý GIẢI ĐỀ THI MÔN TOÁN RỜI RẠC 2(ĐỀ 6)
Đề số:
4(2014-2015)
Câu 1:
a,
deg(1)=3
deg(2)=4
deg(3)=3
deg(4)=2
deg(5)=3
deg(6)=4
deg(7)=1
b,
Biểu diễn đồ
thị G dưới dạng ma trận kề:
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
2
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
3
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
4
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
5
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
6
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
7
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
c,Biểu diễn
đồ thị G dưới dạng danh sách cạnh:
Đỉnh đầu
|
Đỉnh cuối
|
Đỉnh đầu
|
Đỉnh cuối
|
1
|
2
|
3
|
5
|
1
|
3
|
4
|
6
|
1
|
5
|
5
|
6
|
2
|
3
|
6
|
7
|
2
|
4
|
||
2
|
6
|
Câu 2:
a,
DFS(7)={7(0),6(7),2(6),1(2),3(1),5(3),4(2)};
àĐường đi từ đỉnh số 7 tới đỉnh số 2: 7à6à2
b,
BFS(1)={1(0),2(1),3(1),5(1),4(2),6(2),7(6)};
àSố thành phần liên thông: k=1
n=7;
Lập bảng:
Cạnh e
|
Số TPLT l của G\{e}
|
l>k
|
Cạnh cầu
|
(2,3)
|
BFS(1)={1(0),2(1),3(1),5(1),4(2),6(2),7(6)}
àl=1
|
No
|
------
|
(6,7)
|
BFS(1)={1(0),2(1),3(1),5(1),4(2),6(2)}
BFS(7)={7(0)};
àl=2
|
Yes
|
(6,7)
|
Câu 3:
Thuật toán
Cycle-Euler(u):
Bước 1:(Khởi
tạo)
stack=Ø;//Khởi tạo stack ban đầu
là Ø
CE=Ø;//Khởi
tạo một mảng CE ban đầu là Ø
Push(u,stack);//Đẩy
đỉnh u vào stack
Bước
2:(Lặp)
while(stack≠
Ø){//Lặp nếu stack khác rỗng
s=get(stack);//Lấy đỉnh đầu của ngăn
xếp
if(ke(s) ≠ Ø){Nếu danh sách ke(s)
chưa rỗng
t=<t là đỉnh đầu tiên
trong ke(s)>;
Push(t,stack);//Đưa đỉnh
t vào stack
E=E\{s,t};//Loại cạnh
(s,t) khỏi đồ thị
}
else{
Pop(s,stack);//Loại
đỉnh đầu stack
s=>CE;//Đưa
đỉnh s vào mảng CE
}
}
Bước
3:(Trả lại kết quả)
Return<Lật
ngược các đỉnh trong CE thu được chu trình EULER>;
b,
Ke(1)={2,4,5,6} Ke(7)={3,8}
Ke(2)={1,3}
Ke(8)={7,9}
Ke(3)={2,4,7,9} Ke(9)={3,8}
Ke(4)={1,3}
Ke(5)={1,6}
Ke(6)={1,5}
n=9,u=1;
Lập bảng:
Bước
|
stack
|
CE
|
1
|
1
|
Ø
|
2
|
1,2,3
|
1,6,5,1,4
|
3
|
Ø
|
1,6,5,1,4,3,9,8,7,3,2,1
|
KL:Chu trình
Euler bắt đầu từ đỉnh 1: 1-2-3-7-8-9-3-4-1-5-6-1
Câu 4:
a,
Thuật toán Prim(u):
Bước 1:(Khởi
tạo)
VH={u};//Khởi
tạo tập đỉnh cây khung ban đầu là u
V=V\{u};//Tập
đỉnh V được bớt đi u
d(H)=0;//Khởi
tạo độ dài cây khung ban đầu là 0
T= Ø ;//Tập cạnh cây khung thiết lập ban
đầu là Ø
Bước
2:(Lặp)
While(V≠
Ø){
e=<s,t>;//e là cạnh có độ dài
nhỏ nhất thỏa mãn s∈V,t∈VH
d(H)=d(e)+d(H);//Thiết lập độ dài
cho cây khung
T=Tᴗ{e};//Kết nạp cạnh e và câu khung;
V=V\{s};//Tập đỉnh V bớt đỉnh s;
VH=VHᴗ{s};//Thêm
đỉnh s vào tập đỉnh VH
}
Bước
3:(Trả lại kết quả)
If(|T|<n-1)
<Đồ thị không liên thông>;
Else
return(T,d(H));
b,
n=9,u=1;
Lập bảng:
Bước
|
d[1]|p[1]
|
d[2]|p[2]
|
d[3]|p[3]
|
d[4]|p[4]
|
d[5]|p[5]
|
d[6]|p[6]
|
d[7]|p[7]
|
d[8]|p[8]
|
d[9]|p[9]
|
1
|
0|0
|
1|1
|
¥|1
|
4|1
|
2|1
|
1|1
|
¥|1
|
¥|1
|
¥|1
|
2
|
1|1
|
1|2
|
4|1
|
2|1
|
1|1
|
¥|1
|
¥|1
|
¥|1
|
|
3
|
1|2
|
3|3
|
2|1
|
1|1
|
4|3
|
¥|1
|
5|3
|
||
4
|
3|3
|
2|1
|
1|1
|
4|3
|
¥|1
|
5|3
|
|||
5
|
3|3
|
2|1
|
4|3
|
¥|1
|
5|3
|
||||
6
|
3|3
|
4|3
|
¥|1
|
5|3
|
|||||
7
|
4|3
|
3|7
|
5|3
|
||||||
8
|
3|7
|
4|8
|
|||||||
9
|
4|8
|
KL: T={(1,2),(2,3),(3,4),(1,5),(1,6),(3,7),(7,8),(8,9)};
WTmin=1+1+3+2+1+4+3+4=19
Câu 5:
n=5,u=1;
Đồ thị không
chu trình âm
Bước
|
d[1]|p[1]
|
d[2]|p[2]
|
d[3]|p[3]
|
d[4]|p[4]
|
d[5]|p[5]
|
0
|
0|0
|
2|1
|
4|1
|
¥|1
|
¥|1
|
1
|
1|3
|
4|1
|
2|2
|
4|4
|
|
2
|
1|3
|
4|1
|
2|2
|
4|4
|
|
3
|
1|3
|
4|1
|
2|2
|
4|4
|
Đường đi ngắn
nhất từ đỉnh 1-> đỉnh 5:
d[1][5]=4: 1à3à2à4à5
*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
Tổng hợp bài tập môn Toán rời rạc 2 kèm gợi ý
Nếu thấy tài liệu có ích hi vọng các bạn ủng hộ blog 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: https://www.facebook.com/TaiLieuBlog/
💰Ủng hộ blog: https://unghotoi.com/1546792457ngwn4
Nhận xét