Gợi ý giải bài tập Toán rời rạc 2(P2)
Gợi ý giải bài tập Toán rời rạc 2
Cho
đơn đồ thị vô hướng G = <V, E> gồm 10 đỉnh đfdkược biểu diễn dưới dạng ma
trận kề như sau:
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
2
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
3
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
4
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
5
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
6
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
7
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
8
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
9
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
Hãy thực hiện:
a) Trình
bày thuật toán duyệt theo chiều rộng bắt đầu từ đỉnh u Î V trên đồ thị G?
b)
Sử dụng thuật toán duyệt
theo chiều rộng tìm một đường đi có ít cạnh nhất từ đỉnh 1 đến đỉnh 7 của đồ
thị G, chỉ rõ kết quả tại mỗi bước thực hiện theo thuật toán?
Giải:
a,
Thuật toán BFS(u):
Queue=
Ø;Push(u,Queue);
Chuaxet[u]=false;
Bước 2:(Lặp)
While(Queue ‡ Ø) {
s=Pop(Queue); <Tham dinh s>;
for
each t Є ke() do{
if(chuaxet[t]){
chuaxet[t]=false;
Push(t,Queue);
}
}
}
}
Bước 3: (Tra lai ket qua)
Return<tap
dinh da tham>
b,
BFS(1)={1(0),2(1),9(1),10(1),3(2),4(2),8(2),5(3),6(4),7(4)}
=> Đường đi có ít cạnh nhất: 7ß4ß2ß1
Cho đơn đồ thị vô hướng G = <V,
E> gồm 10 đỉnh được biểu diễn dưới dạng ma trận kề như sau:
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
2
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
3
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
4
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
5
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
6
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
7
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
8
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
9
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
Hãy thực hiện:
a) Trình
bày thuật toán duyệt theo chiều rộng bắt đầu từ đỉnh u Î V trên đồ thị G?
b) Sử
dụng thuật toán duyệt theo chiều rộng tìm cây khung của đồ thị G bắt đầu tại u = 5, chỉ
rõ kết quả tại mỗi bước thực hiện theo thuật toán?
Giải:
a,
Thuật toán BFS(u):
Buoc 1: (Khoi tao)
Queue=
Ø;
Push(Queue,u);
Chuaxet[u]=false;
Buoc 2: (Lap)
While(Queue‡
Ø){
s=Pop(Queue);
<Tham dinh s>;
for each t Є ke() do{
if(chuaxet[t]){
chuaxet[t]=false;
Push(Queue,t);
}
}
}
Buoc 3: Tra lai ket qua
Return(<Tap dinh da tham>);
b,
BFS(5)={5(0),3(5),4(5),6(5),2(3),4(3),10(3),7(4),8(4),1(2),9(2)}=V;
KL: Cây khung của G:
T={(3,5),(4,5),(5,6),(2,3),(3,4),(3,10),(4,7),(4,8),(1,2),(2,9)}
Câu hỏi 18
Cho đơn đồ thị có hướng G =
<V, E> gồm 10 đỉnh được biểu diễn dưới dạng ma trận kề như sau:
a)
Trình bày thuật toán duyệt theo chiều sâu bắt đầu từ
đỉnh u Î
V trên đồ thị G?
b)
Chứng minh rằng G là đồ thị liên thông yếu nhưng không
liên thông mạnh?
Giải:
a,Thuật toán DFS(u):
<Tham dinh u>;
Chuaxet[u]=false;
For each v Є V do{
If(chuaxet[v]) DFS(v);
}
b,
DFS(1)={1(0),4(1),2(4),10(4)} ‡ V;
èĐồ thị không liên
thông mạnh
Xét đồ thị vô hướng nền of G:
DFS(1)={1(0),4(1),2(4),3(2),7(3),5(7),6(5),8(6),9(8),10(2)}=V
=>G liên thông yếu
Câu hỏi 19
Cho đơn đồ thị có hướng G =
<V, E> gồm 10 đỉnh được biểu diễn dưới dạng ma trận kề như sau:
a)
Trình bày thuật toán duyệt theo chiều rộng bắt đầu từ
đỉnh u Î
V trên đồ thị G?
b)
Sử dụng thuật toán duyệt theo chiều rộng chứng minh
rằng G là đồ thị liên thông mạnh?
Giải:
a,
Buoc
1:
(Khoi tao)
Queue= Ø;
Push(Queue,u);
Chuaxet[u]=false;
Buoc
2:
(Lap)
While(Queue‡ Ø){
s=Pop(Queue);
<Tham
dinh s>;
for each t Є ke() do{
if(chuaxet[t]){
chuaxet[t]=false;
Push(Queue,t);
}
}
}
Buoc 3: Tra lai ket qua
Return(<Tap dinh da tham>);
b,
BFS(1)={1(0),2(1),3(1),4(2),5(2),9(3),10(3),6(4),7(4),8(6)}=V
BFS(2)={2(0),3(2),4(2),5(2),9(3),10(3),6(4),7(4),1(10),8(6)}=V
BFS(3)={3(0),9(3),10(3),1(10),2(10),4(2),5(2),6(4),7(4),8(6)}=V;
…………………………………………………….
BFS(10)={10(0),1(10),2(10),3(1),4(2),5(2),9(3),10(3),6(4),7(4),8(6)}=V;
è G là đồ thị liên thông
mạnh
Câu hỏi 20
Cho đơn đồ thị có hướng G =
<V, E> gồm 10 đỉnh được biểu diễn dưới dạng ma trận kề như sau:
Hãy thực hiện:
a)
Trình bày thuật toán duyệt theo chiều sâu bắt đầu từ
đỉnh u Î
V trên đồ thị G?
b)
Sử dụng thuật toán duyệt
theo chiều sâu tìm tất cả các thành phần liên thông mạnh của đồ thị G, chỉ rõ
kết quả tại mỗi bước thực hiện theo thuật toán?
Giải:
a,Thuật toán DFS(u):
<Tham dinh u>;
Chuaxet[u]=false;
For each v Є V do{
If(chuaxet[v]) DFS(v);
}
b,
DFS(1)={1(0),4(1),2(4),10(4)}
DFS(2)={2(0),4(2),10(4),1(10)}
DFS(3)={3(0},8(3),5(8),6(5),7(6),9(7)}
DFS(4)={4(0),2(4),10(4),1(10)}
DFS(5)={5(0),6(5),7(6),3(7),8(3),9(3)}
DFS(6)={6(0),5(6),7(5),3(7),8(3),9(8)}
DFS(7)={7(0),3(7),8(3),5(8),6(5),9(8)}
DFS(8)={8(0),5(8),6(5),7(6),3(7),9(3)}
DFS(9)={9(0),5(9),6(5),7(6),3(7),8(3)}
DFS(10)={10(0),1(10),4(1),2(4),} ‡ V
Thành
phần liên thông mạnh 1: 1,2,4,10
Thành phần liên thông mạnh 2: 3,5,6,7,8,9
Câu hỏi 21
Cho đơn đồ thị vô hướng G =
<V, E> gồm 10 đỉnh được biểu diễn dưới dạng ma trận kề như sau
Hãy thực hiện:
a)
Phát biểu điều kiện cần và đủ để một đồ thị vô
hướng là đồ thị Euler?
b)
Chứng minh đồ thị G đã cho là đồ thị Euler?
Giải:
a,
Cho đồ thị G=(V,E)
Đồ thị vô hướng G là đồ thị Euler
khi và chỉ khi G liên thông và với mọi v thuộc V có bậc chẵn
b,
+, BFS(1)={1(0),2(1),5(1),10(1),3(2),4(2),6(2),7(5),8(5),9(5)}
=V
=> G liên thông (1)
+,
deg(1)=4 deg(6)=2
deg(2)=4 deg(7)=4
deg(3)=2 deg(8)=4
deg(4)=2 deg(9)=2
deg(5)=6 deg(10)=4
=> Tất cả có 10 đỉnh bậc chẵn (2)
(1),(2)è đồ thị G đã cho là đồ
thị Euler
Câu hỏi 22
Cho đơn đồ thị vô hướng G =
<V, E> gồm 10 đỉnh được biểu diễn dưới dạng ma trận kề như sau
Hãy thực hiện:
a)
Trình bày thuật toán tìm một chu trình Euler của đồ thị?
b)
Áp dụng thuật toán, tìm một chu trình Euler của đồ thị
G đã cho bắt đầu từ đỉnh 1, chỉ rõ kết quả tại mỗi bước thực hiện theo thuật toán
Giải:
a,
Thuật toán Euler-Cycle(u):
Bước 1(Khởi tạo):
Stack= Ø;
CE= Ø;
Push(Stack,u);
Bước 2(Lặp):
While(Stack‡ Ø) do{
s=get(Stack);
if(Ke(s) ‡ Ø) then{
t=<Dinh dau tien trong
Ke(s)>;
Push(Stack,t);
E=E\(s,t);
}
else{
s=Pop(Stack);
s=>CE;
}
}
Bước 3(Trả lại kết quả):
Return(<Lật ngược lại các đinh
trong CE thu được chu trình EULER>),
b,
+,
BFS(1)={1(0),2(1),5(1),8(1),10(1),3(2),4(2),6(2),7(5),9(5)}=V
àG liên thông (1)
+,
Deg(1)=4
Deg(2)=4
Deg(3)=2
Deg(4)=2
Deg(5)=6
Deg(6)=2
Deg(7)=4
Deg(8)=4
Deg(9)=2
Deg(10)=4
àTất cả 10 đỉnh đều có bậc
chẵn (2)
(1),(2)èĐồ thị G là đồ thị Euler
Bước
|
Stack
|
CE
|
1
|
1
|
Ø
|
2
|
1,2,3,4,2,6,5,1,8,5,7,8,10,1
|
Ø
|
3
|
1,2,3,4,2,6,5,1,8,5,7,8,10,5,9,7,10
|
1
|
4
|
Ø
|
1,10,7,9,5,10,8,7,5,8,1,5,6,2,4,3,2,1
|
Kết thúc: Chu trình EULER:
1-2-3-4-2-6-5-1-8-5-7-8-10-5-9-7-10-1
Câu hỏi 23
Cho đơn đồ thị G = <V, E> gồm 7 đỉnh được biểu diễn dưới dạng ma trận
trọng số như sau
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
1
|
0
|
20
|
5
|
17
|
¥
|
¥
|
¥
|
2
|
20
|
0
|
¥
|
1
|
¥
|
¥
|
1
|
3
|
5
|
¥
|
0
|
25
|
3
|
10
|
¥
|
4
|
17
|
1
|
25
|
0
|
15
|
¥
|
¥
|
5
|
¥
|
¥
|
3
|
15
|
0
|
1
|
¥
|
6
|
¥
|
¥
|
10
|
¥
|
1
|
0
|
1
|
7
|
¥
|
1
|
¥
|
¥
|
¥
|
1
|
0
|
Hãy thực hiện:
a)
Trình bày thuật toán Dijkstra tìm đường đi ngắn nhất
xuất phát từ đỉnh uÎ
V?
b)
Áp dụng thuật toán Dijkstra, tìm đường đi ngắn nhất từ
đỉnh 1 đến đỉnh 7 của đồ thị G đã cho, chỉ rõ kết quả tại mỗi bước thực hiện
theo thuật toán?
Giải:
a,
Trình bày thuật toán Dijkstra:
Thuật toán Dijkstra:
Bước 1: Khởi tạo s là đỉnh xuất phát
d[s]=0;(Gán nhãn của đỉnh s là 0)
T=V\{s};//T là tập đỉnh có nhãn tạm
thời
For(v ЄV){
d[v]=A[s,v];
truoc[v]=s;
}
Bước 2: Lặp
While(V‡ Ø){
<Chọn u là đỉnh có d[u]
min>;
T=T/{u};<Cố định nhãn của đỉnh
u>;
For each vЄV do{
If(d[v]>d[u]+A[u,v]){
d[v]=d[u]+A[u,v];
truoc[v]=u;
}
}
}
Bước 3(Trả lại kết quả): Return(d(s,t)).
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]
|
1
|
<0,1>
|
<20,1>
|
<5,1>
|
<17,1>
|
<¥,1>
|
<¥,1>
|
<¥,1>
|
2
|
<20,1>
|
<5,1>
|
<17,1>
|
<8,3>
|
<15,3>
|
<¥,1>
|
|
3
|
<20,1>
|
<17,1>
|
<8,3>
|
<9,5>
|
<¥,1>
|
||
4
|
<20,1>
|
<17,1>
|
<9,5>
|
<10,6>
|
|||
5
|
<11,7>
|
<17,1>
|
<10,6>
|
||||
6
|
<11,7>
|
<12,2>
|
|||||
7
|
<12,2>
|
Đường đi ngắn nhất từ đỉnh 1 đến đỉnh
7: 1->3->5->6->7(Độ dài 10)
Câu hỏi 24
Cho đơn đồ thị G = <V, E>
gồm 7 đỉnh được biểu diễn dưới dạng ma trận trọng số như sau
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
1
|
0
|
10
|
15
|
20
|
¥
|
1
|
¥
|
2
|
¥
|
0
|
3
|
¥
|
¥
|
¥
|
30
|
3
|
¥
|
¥
|
0
|
25
|
3
|
¥
|
45
|
4
|
¥
|
10
|
25
|
0
|
35
|
¥
|
¥
|
5
|
¥
|
2
|
3
|
¥
|
0
|
¥
|
3
|
6
|
¥
|
¥
|
1
|
1
|
¥
|
0
|
25
|
7
|
¥
|
1
|
¥
|
30
|
¥
|
1
|
0
|
Hãy thực hiện:
a)
Trình bày thuật toán Dijkstra tìm đường đi ngắn nhất
xuất phát từ đỉnh uÎ
V?
b)
Áp dụng thuật toán Dijkstra, tìm đường đi ngắn nhất từ
đỉnh 1 đến đỉnh 7 của đồ thị G đã cho, chỉ rõ kết quả tại mỗi bước thực hiện
theo thuật toán?
Giải:
Trình bày thuật toán Dijkstra:
Thuật toán Dijkstra:
Bước 1: Khởi tạo u là đỉnh xuất phát
d[u]=0;(Gán nhãn của đỉnh u là 0)
T=V\{u};//T là tập đỉnh có nhãn tạm
thời
For(v ЄV){
d[v]=A[s,v];
truoc[v]=s;
}
Bước 2: Lặp
While(T‡ Ø){
<Chọn t là đỉnh có d[t]
min>;
T=T/{t};<Cố định nhãn của đỉnh
t>;
For each vЄV do{
If(d[v]>d[t]+A[t,v]){
d[v]=d[t]+A[t,v];
truoc[v]=t;
}
}
}
Bước 3(Trả lại kết quả): Return(d(u),truoc[u])
b,
Bước
|
Đỉnh 1
|
Đỉnh 2
|
Đỉnh 3
|
Đỉnh 4
|
Đỉnh 5
|
Đỉnh 6
|
Đỉnh 7
|
1
|
<0,1>
|
<10,1>
|
<15,1>
|
<20,1>
|
<¥,1>
|
<1,1>
|
<¥,1>
|
2
|
|
<10,1>
|
<2,6>
|
<2,6>
|
<¥,1>
|
<1,1>
|
<26,6>
|
3
|
|
<10,1>
|
<2,6>
|
<2,6>
|
<5,3>
|
|
<26,6>
|
4
|
|
<10,1>
|
|
<2,6>
|
<5,3>
|
|
<26,6>
|
5
|
|
<7,5>
|
|
|
<5,3>
|
|
<8,5>
|
6
|
|
<7,5>
|
|
|
|
|
<8,5>
|
7
|
|
|
|
|
|
|
<8,5>
|
Đường đi ngắn nhất từ đỉnh 1 đến đỉnh
7: 1à6à3à5à7(Độ
dài 8)
Câu hỏi 25
Cho đơn đồ thị G = <V, E>
gồm 7 đỉnh được biểu diễn dưới dạng ma trận trọng số như sau
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
1
|
0
|
15
|
¥
|
¥
|
¥
|
1
|
9
|
2
|
¥
|
0
|
8
|
¥
|
¥
|
¥
|
¥
|
3
|
¥
|
¥
|
0
|
4
|
1
|
¥
|
¥
|
4
|
¥
|
7
|
¥
|
0
|
¥
|
¥
|
1
|
5
|
¥
|
10
|
¥
|
2
|
0
|
¥
|
¥
|
6
|
¥
|
14
|
2
|
¥
|
¥
|
0
|
¥
|
7
|
¥
|
2
|
¥
|
¥
|
¥
|
¥
|
0
|
Hãy thực hiện:
a)
Trình bày thuật toán Dijkstra tìm đường đi ngắn nhất
xuất phát từ đỉnh uÎ
V?
b)
Áp dụng thuật toán Dijkstra, tìm đường đi ngắn nhất từ
đỉnh 6 đến đỉnh 2 của đồ thị G đã cho, chỉ rõ kết quả tại mỗi bước thực hiện
theo thuật toán
a,
Trình bày thuật toán Dijkstra:
Thuật toán Dijkstra:
Bước 1: Khởi tạo u là đỉnh xuất
phát
d[u]=0;//Gán nhãn của đỉnh u=0
T=V\{u};//T là tập đỉnh có nhãn tạm
thời
For(vЄV){
d[v]=A[s,v];
truoc[v]=s;
}
Bước 2: Lặp
While(T‡ Ø){
<Chọn t là đỉnh
có d[t] min>;
T=T/{t};<Cố
định nhãn của đỉnh t>;
For
each vЄV do{
If(d[v]>d[t]+A[t,v]){
d[v]=d[t]+A[t,v];
truoc[v]=t;
}
}
}
Bước 3(Trả lại kết quả): Return(d(u),truoc[u]).
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]
|
1
|
<0,1>
|
<15,1>
|
<¥,1>
|
<¥,1>
|
<¥,1>
|
<1,1>
|
<9,1>
|
2
|
<15,1>
|
<3,6>
|
<¥,1>
|
<¥,1>
|
<1,1>
|
<9,1>
|
|
3
|
<15,1>
|
<3,6>
|
<7,3>
|
<4,3>
|
<9,1>
|
||
4
|
<14,5>
|
<6,5>
|
<4,3>
|
<9,1>
|
|||
5
|
<13,4>
|
<6,5>
|
<7,4>
|
||||
6
|
<9,7>
|
<7,4>
|
|||||
7
|
<9,7>
|
||||||
Đường đi ngắn nhất từ đỉnh 6 đến
đỉnh 2 :6à3à5à4à7à2
(9-1=8)
Nếu thấy tài liệu có ích hi vọng mn ủ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