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

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

Edit



Đề 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


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
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/
Share on Google Plus

About Kỹ Thuật Xe

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.
    Blogger Comment
    Facebook Comment

0 nhận xét:

Đăng nhận xét

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