Note Đóng lại

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




Đề số: 2(2016-2017)
Gợi ý:

Câu 1:
a,
deg(1)=2
deg(2)=3
deg(3)=2
deg(4)=3
deg(5)=3
deg(6)=2
deg(7)=2
deg(8)=1

b,Ma trận kề

1
2
3
4
5
6
7
8
1
0
1
1
0
0
0
0
0
2
1
0
1
1
0
0
0
0
3
1
1
0
0
0
0
0
0
4
0
1
0
0
1
1
0
0
5
0
0
0
1
0
1
1
0
6
0
0
0
1
1
0
0
0
7
0
0
0
0
1
0
0
1
8
0
0
0
0
0
0
1
0

Câu 2:
a,
void BFS(int u){
          bool chuaxet[MAX];
          for(int i=1;i<=n;i++) chuaxet[i]=true;//n là số đỉnh của đồ thị
          queue<int> q;
          q.push(u);
          chuaxet[u]=false;
          cout<<u<<“ ”;
          while(!q.empty()){
                    int s=q.front();
                    cout<<s<<” ”;
                    q.pop();
                    for(int i=1;i<=n;i++){
                              if(chuaxet[i]&&a[s][i]){
                                        chuaxet[i]=false;
                                        q.push(i);
}
}
}
}
b,
BFS(1)={1(0),2(1),3(1),4(2),5(4),6(4),7(5),8(7)}
è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
BFS(2)={2(0),3(2),4(2),5(4),6(4),7(5),8(7)}
àl=1
No
------
2
BFS(1)={1(0),3(1)}
BFS(4)={4(0),5(4),6(4),7(5),8(7)}
àl=2
Yes
2
3
BFS(1)={1(0),2(1),4(2),5(4),6(4),7(5),8(7)}
àl=1
No
-------
4
BFS(1)={1(0),2(1),3(1)}
BFS(5)={5(0),6(5),7(5),8(7)}
àl=2
Yes
4
5
BFS(1)={ 1(0),2(1),3(1),4(2),6(4)}
BFS(7)={7(0),8(7)}
àl=2
Yes
5
6
BFS(1)={1(0),2(1),3(1),4(2),5(4),7(5),8(7)}
àl=1
No
-------
7
BFS(1)={ 1(0),2(1),3(1),4(2),5(4),6(4)}
BFS(8)={8(0)}
àl=2
Yes
7
8
BFS(1)={ 1(0),2(1),3(1),4(2),5(4),6(4),7(5)}
àl=1
No
------

KL: Các đỉnh trụ : 2,4,5,7

Câu 3:
a,
Điều kiện cần và đủ để một đồ thị vô hướng là nửa EULER:
-Đồ thị vô hướng G liên thông
-Số đỉnh v thuộc V có bậc lẻ không vượt quá 2
Chứng minh đồ thị vô hướng G là nửa EULER:
BFS(1)={1(0),3(1),5(1),2(3),10(3),6(2),8(2),9(2),7(10),4(6)}=V
àĐồ thị G liên thông (1)
Tính bậc của các đỉnh:
deg(1)=2
deg(2)=4
deg(3)=4
deg(4)=2
deg(5)=2
deg(6)=4
deg(7)=3
deg(8)=2
deg(9)=3
deg(10)=2
àCó 2 đỉnh 7 và 9 là có bậc lẻ  (2)
(1),(2)èĐồ thị vô hướng G là nửa EULER.
b,
Tìm đường đi EULER trên đồ thị G bắt đầu từ u=7
n=10,u=7.
Bước
Stack
CE
1
7
Ø
2
Ø
9,6,4,8,2,9,7,10,3,5,1,3,2,6,7

KL:Đường đi Euler từ đỉnh u=7: 7-6-2-3-1-5-3-10-7-9-2-8-4-6-9
Câu 4:

1
2
3
4
5
6
7
8
9
10
1
0
1
1
¥
¥
¥
2
¥
¥
¥
2
1
0
1
¥
¥
¥
3
¥
7
¥
3
1
1
0
¥
¥
5
¥
3
¥
¥
4
¥
¥
¥
0
6
¥
¥
¥
¥
¥
5
¥
¥
¥
6
0
5
¥
1
4
7
6
¥
¥
5
¥
5
0
3
¥
¥
¥
7
2
3
¥
¥
¥
3
0
¥
¥
6
8
¥
¥
3
¥
1
¥
¥
0
¥
5
9
¥
7
¥
¥
4
¥
¥
¥
0
6
10
¥
¥
¥
¥
7
¥
6
5
6
0
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;
T= Ø;//Khởi tạo tập cạnh cây khung ban đầu rỗng
d(H)=0;//Khởi tạo độ dài cây khung ban đầu là 0
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 thuộc  V,t thuộc 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
            V=V\{s};//Tập đỉnh V bớt đi đỉnh s
            VH=VH◡{s};//Tập đỉnh VH thêm đỉnh s
}
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,
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]
d[10]|p[10]
1
¥|5
¥|5
¥|5
6|5
0|0
5|5
¥|5
1|5
4|5
7|5
2
¥|5
¥|5
3|8
6|5

5|5
¥|5
1|5
4|5
5|8
3
1|3
1|3
3|8
6|5

5|5
¥|5

4|5
5|8
4
1|3
1|3

6|5

5|5
2|1

4|5
5|8
5

1|3

6|5

5|5
2|1

4|5
5|8
6



6|5

3|7
2|1

4|5
5|8
7



6|5

3|7


4|5
5|8
8



6|5




4|5
5|8
9



6|5





5|8
10



6|5







KL: T={(1,3),(2,3),(3,8),(4,5),(6,7),(1,7),(5,8),(5,9),(8,10)};
WT=1+1+3+6+3+2+1+4+5=26
Câu 5:
a,
void BELLMAN(int u){
          int D[MAX];// Mảng D chứa độ dài đường đi
          int a[MAX][MAX],Trace[MAX];
          int n,v;//n là số đỉnh,v là đỉnh kết thúc
          for(int i=1;i<=n;i++){
                    D[i]=A[u][i];
                    Trace[i]=S;
}
          int k,s,t;
          D[u]=0;
          For(k=1;k<=n-2;k++){
                    For(s=1;s<=n;s++){
                              If(s!=u){
                                        For(t=1;t<=n;t++){
                                                  If(D[s]>D[t]+a[t,s]){
                                                            D[s]= D[t]+a[t,s];
                                                            Trace[t]=s;
}
}
}
}
}
While(v!=u){
cout<<”<---”<<v;
v=Trace[v];
}
}
b,
n=8,Đồ thị không chứa 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]
d[6]|p[6]
d[7]|p[7]
d[8]|p[8]
0
0|0
2|1
¥|1
¥|1
¥|1
¥|1
3|1
¥|1
1

1|7
6|2
8|3
7|3
2|2
3|1
3|6
2

1|7
5|8
7|3
5|6
2|2
3|1
2|5
3

1|7
4|8
6|3
5|6
2|2
3|1
2|5
4

1|7
4|8
6|3
5|6
2|2
3|1
2|5
5

1|7
4|8
6|3
5|6
2|2
3|1
2|5
6

1|7
4|8
6|3
5|6
2|2
3|1
2|5
KL:
Đường đi ngắn nhất từ đỉnh 1->2: 1à7à2(d=1)
Đường đi ngắn nhất từ đỉnh 1->3: 1à7à2à6à5à8à3(d=4)
Đường đi ngắn nhất từ đỉnh 1->4: 1à7à2à6à5à8à3à4(d=6)
Đường đi ngắn nhất từ đỉnh 1->5: 1à7à2à6à5(d=5)
Đường đi ngắn nhất từ đỉnh 1->6: 1à7à2à6(d=2)
Đường đi ngắn nhất từ đỉnh 1->7: 1à7(d=3)
Đường đi ngắn nhất từ đỉnh 1->8: 1à7à2à6à5à8(d=2)


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/

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