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

Đề số 1: (2014-2015)

Câu 1:

a,

deg(1)=3

deg(2)=2

deg(3)=3

deg(4)=3

deg(5)=2

deg(6)=4

deg(7)=3

deg(8)=2

b,Biểu diễn đồ thị G dưới dạng ma trận kề:

	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, 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	5	6
1	3	5	7
1	4	6	7
2	3	6	8
3	4	7	8
4	6

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 số 7àđỉnh số 2: 7à6à4à1à2

b,

DFS(1)={1(0),2(1),3(1),4(1),6(4),5(6),7(6),8(6)}

àSố thành phần liên thông : k=1

Lập bảng:

Đỉ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(2)} DFS(5)={5(0),6(5),7(6),8(7)} àl=2	Yes	4
6	DFS(1)={1(0),2(1),3(2),4(3)} DFS(5)={5(0),7(5),8(7)} àl=2	Yes	6

KL: Các đỉnh trụ: 4,6

Câu 3:

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 ban đầu là Ø

Push(u,Stack);//Đưa đỉnh u vào ngăn xếp

Bước 2:(Lặp)

While(Stack ≠ Ø){//Lặp nếu stack không rỗng

          s=get(Stack);//Lấy đỉnh đầu của ngăn xếp;

          if(ke(s) ≠ Ø){//Nếu danh sach ke(s) không rỗng

                    t=<t là đỉnh đầu trong ke(s)>;

                    push(t,Stack);//Đưa đỉnh t vào ngăn xếp

                    E=E\{s,t};//Loại cạnh (s,t) khỏi đồ thị

}

else{

          Pop(s,Stack);//Loại đỉnh đầu ngăn xếp

          s=>CE;//Đưa đỉnh s vào mảng CE

}

}

Bước 3:(Trả lại kết quả)

<Lật ngược các đỉnh trong CE thu được chu trình Euler>;

b,

Danh sách kề:

Ke(1)={2,3,5,6}	Ke(6)={1,4,5,8}
Ke(2)={1,3}	Ke(7)={3,5,8,9}
Ke(3)={1,2,7,8}	Ke(8)={3,6,7,9}
Ke(4)={5,6}	Ke(9)={7,8}
Ke(5)={1,4,6,7}

n=9,u=1

Lập bảng:

Bước	Stack	CE
1	1	Ø
2	1,2,3,1,5,4,6,1	Ø
3	1,2,3,1,5,4,6,5,7,3,8,6	1
4	1,2,3,1,5,4,6,5,7,3,8,7,9,8	1,6
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 Kruskal:

Bước 1:(Khởi tạo)

T=Ø;//Khởi tạo cây khung ban đầu là Ø

d(H)=0;//Khởi tạo độ dài cây khung ban đầu là 0

Bước 2:(Sắp xếp)

<Sắp xếp độ dài các cạnh theo thứ tự tăng dần của trọng số>;

Bước 3:(Lặp)

While(|T|<n-1&&E≠ Ø) do{//Lặp nếu | T|<n-1 và E≠ Ø

          e=<e là cạnh có trọng số nhỏ nhất>;

          E=E\{e};//Loại cạnh e ra khỏi đồ thị

          if(T ᴗ{e} không chứa chu trình) then{

                    T=T ᴗ{e};//Kết nạp cạnh e và cây khung

                    d(H)=d(H)+d(e);//Thiết lập độ dài mới cho cây khung

}

}

Bước 4:(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

Sắp xếp 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)

Lập bảng:

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)	No	(3,8)	14	8

KL: W^T_min=14

T={(1,2), (2,3), (3,7), (6,8), (4,6), (5,7), (1,6), (3,8)};

Câu 5:

n=10,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]
1	0|0	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 đến đỉnh 5:

d[1][5]=4:  1à3à2à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 mọi người ủng hộ blog bằng cách like và theo dõi địa chỉ page chính thức của Ebook HoIT Asia tại: https://www.facebook.com/Ebook-Document-652588761864731/

💰Ủng hộ blog: https://ebook.hoit.asia/p/donate.html