Note Đóng lại

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




Đề số 1(2016-2017)
Câu 1:
a,
deg(1)=2
deg(2)=2
deg(3)=2
deg(4)=2
deg(5)=4
deg(6)=3
deg(7)=2
deg(8)=1
b,Biểu diễn đồ thị G dưới dạng ma trận kề:

Câu 2:
a,
int n;//n là số đỉnh
bool chuaxet[MAX];//Mảng chuaxet lưu trạng thái của từng đỉnh
for(int i=1;i<=n;i++){
          chuaxet[i]=true;
}
void DFS(int u){
          cout<<u<<” ”;
          chuaxet[u]=false;
          for(int v=1;v<=n;v++){
                    if(chuaxet[v]&&a[u][v]){
                              DFS(v);
}
}
                 
}
b,
DFS(1)={1(0),3(1),4(3),5(4),2(5),6(2),7(6),8(7)}=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
l=1
-------
-------
2
l=1
-------
-------
3
l=1
-------
-------
4
l=1
-------
-------
5
l=2
Yes
5
6
            l=2
Yes
6
7
l=2
Yes
7
8
l=1
-------
-------
KL: Có 3 đỉnh là đỉnh trụ: 5,6,7
Câu 3:
a,
*Điều kiện cần và đủ để một đồ thị vô hướng là EULER:
-Đồ thị vô hướng G liên thông
-Mọi đỉnh v thuộc V đều có bậc chẵn

1
2
3
4
5
6
7
8
9
0
1
0
1
0
0
0
0
0
0
0
1
2
1
0
0
0
0
1
0
1
0
1
3
0
0
0
1
1
0
0
0
0
0
4
0
0
1
0
0
0
1
0
0
0
5
0
0
1
0
0
1
0
0
0
0
6
0
1
0
0
1
0
1
0
1
0
7
0
0
0
1
0
1
0
1
1
0
8
0
1
0
0
0
0
1
0
0
0
9
0
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
*Chứng minh đồ thị vô hướng G là Euler:
-BFS(1)={1(0),2(1),10(1),6(2),5(6),7(6),9(6),3(5),4(7),8(7)}=V
àG liên thông (1)
-Tính bậc của các đỉnh:
deg(1)=2
deg(2)=4
deg(3)=2
deg(4)=2
deg(5)=2
deg(6)=4
deg(7)=4
deg(8)=2
deg(9)=2
deg(10)=2
àTất cả 10 đỉnh đều có bậc chẵn (2)
(1),(2) èĐồ thị vô hướng G là Euler.
b,Tìm chu trình Euler trên đồ thị G bắt đầu từ đỉnh 2
n=10,u=2;
Bước
Stack
CE
0
2
Ø
1
2,1,10,2,6,5,3,4,7,6,9,7,8
2
2
Ø
2,8,7,9,6,7,4,3,5,6,2,10,1,2
KL: Chu trình Euler bắt đầu từ đỉnh 2:  2-1-10-2-6-5-3-4-7-6-9-7-8-2
Câu 4:
a,
Thuật toán Kruskal:
Bước 1: (Khởi tạo)
T= Ø;//Khởi tạo tập cạnh cây khung là rỗng
d(H)=0;//Khởi tạo độ dài cây khung là 0
Bước 2: (Sắp xếp)
<Sắp xếp các cạnh đồ thị theo thứ tự tăng dần trọng số>;
Bước 3:(Lặp)
While(|T|<n-1&&E Ø){//Lặp nếu |T|<n-1 và E Ø
               e=<Cạnh có độ dài nhỏ nhất>;
            E=E\{e};//Loại cạnh e ra khỏi đồ thị
            If(T◡{e} không tạo nên chu trình) then{
                        T=T◡{e};//Kết nạp cạnh e vào cây khung
                        d(H)=d(H)+d(e);//Cập nhật độ dài tập cạnh cây khung
}
}
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=10;
Sắp xếp các cạnh theo thứ tự tăng dần của trọng số:
(1,2)<=(1,3)<=(2,3)<=(5,8)<=(1,7)<=(2,7)<=(3,8)<=(6,7)<=(5,9)<=(3,6)<=(5,6)<=(8,10)<=(4,5)<=(7,10)<=(9,10)<=(2,9)<=(5,10)
Lập bảng:
Cạnh ei
T ◡ei chứa chu trình
T
WT
k
(1,2)
No
(1,2)
1
1
(1,3)
No
(1,3)
2
2
(2,3)
Yes
------
------
------
(5,8)
No
(5,8)
3
3
(1,7)
No
(1,7)
5
4
(2,7)
Yes
-----
-----
-----
(3,8)
No
(3,8)
8
5
(6,7)
No
(6,7)
11
6
(5,9)
No
(5,9)
15
7
(3,6)
Yes
-----
-----
-----
(5,6)
Yes
-----
-----
-----
(8,10)
No
(8,10)
20
8
(4,5)
No
(4,5)
26
9
KL:
WTmin=26;
T={(1,2),(1,3),(5,8),(1,7),(3,8),(6,7),(5,9),(8,10),(4,5)}
Câu 5:
a,
void DIJKSTRA(int u){
          int n,v;//n la so dinh do thi,v la đỉnh cuối
          cout<<"Duong di tu dinh u den dinh ";
          cin>>v;
          int truoc[100],d[100];/*Mảng truoc[] lưu đỉnh trước,d[] lưu độ dài đường đi                             từ đỉnh u đến đỉnh xét*/
          bool chuaxet[100];
          for(int i=1;i<=n;i++){
                    d[i]=a[u][i];
                    truoc[i]=u;
                    chuaxet[i]=true;
          }
          truoc[u]=0;
          d[u]=0;
          chuaxet[u]=false;
          int i,j;
          while(chuaxet[v]){
                    minp=2000;
                    for(i=1;i<=n;i++){//Tìm đỉnh i sao cho d[i] min
                              if(chuaxet[i]&&(minp>d[i])){
                                        j=i;
                                        minp=d[i];
                              }
                    }
                    chuaxet[j]=false;
                    if(chuaxet[v]){
                              for(i=1;i<=n;i++){
                                        if(chuaxet[i]&&(d[j]+a[j][i])<d[i]){
                                                  d[i]=d[j]+a[j][i]);
                                                  truoc[i]=j;
                              }
                    }
          }
          int i=truoc[v];
          while(i!=u){
                    cout<<i<<” “;//In ra duong di tu dinh u đến đỉnh v
                    i=truoc[i];
}
}
b,n=10,u=1,v=4
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]
1
0|1
4|1
|1
|1
|1
|1
1|1
|1
2

3|7
|1
|1
|1
6|7
1|1
|1
3

3|7
8|2
|1
|1
4|2

|1
4


8|2
|1
7|6
4|2

5|6
5


7|8
|1
7|6


5|6
6


7|8
9|3
7|6



7



8|5
7|6



8



8|5




KL:
Đường đi ngắn nhất từ đỉnh số 1 tới đỉnh số 4:  1à7à2à6à5à4 (Độ dài 8)

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 mọi người ủ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/

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