Note Đóng lại

Gợi ý giải bài tập Toán rời rạc 2(P1)

5/25/2019
Tài liệu blog

Gợi ý giải bài tập Toán rời rạc 2

Câu hỏi 1
Cho đơn đồ thị vô hướng G = <V, E> gồm 10 đỉnh được biểu diễn dưới dạng danh sách kề như sau:

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

Hãy thực hiện:
a)     Tìm deg(u) với mọi uÎV?
b)     Hãy biểu diễn đồ thị G =<V, E> dưới dạng ma trận kề?
c)     Hãy biểu diễn đồ thị G =<V, E> dưới dạng danh sách cạnh?

Giải:
a,
deg(1)=3          deg(6)=3
deg(2)=6          deg(7)=3
deg(3)=4          deg(8)=4
deg(4)=6          deg(9)=4
deg(5)=3           deg(10)=4
b,
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
1
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

c,
Danh sách cạnh:

Đỉnh đầu
Đỉnh cuối
Đỉnh đầu
Đỉnh cuối
1
2
3
4
1
9
3
5
1
10
3
10
2
3
4
5
2
4
4
6
2
8
4
7
2
9
4
8
2
10
5
6


6
7


7
8


8
9


9
10

Câu hỏi 2
Cho đơn đồ thị vô hướng G = <V, E> gồm 10 đỉnh và 20 cạnh được biểu diễn dưới dạng danh sách cạnh như sau:

Đỉnh đầu
Đỉnh cuối
Đỉnh đầu
Đỉnh cuối
1
2
5
7
1
5
5
9
1
8
5
10
1
10
6
7
2
3
6
10
2
4
7
8
2
6
7
9
4
6
7
10
4
8
8
9
5
6
9
10

Hãy thực hiện:
a)     Tìm deg(u) với mọi uÎV?
b)     Hãy biểu diễn đồ thị G =<V, E> dưới dạng ma trận kề?
c)     Hãy biểu diễn đồ thị G =<V, E> dưới dạng danh sách kề?


Giải :
a,
deg(1)=4          deg(6)=5
deg(2)=4          deg(7)=5
deg(3)=1          deg(8)=4
deg(4)=3          deg(9)=4
deg(5)=5           deg(10)=5
b,
1
2
3
4
5
6
7
8
9
0
1
0
1
0
0
1
0
0
1
0
1
2
1
0
1
1
0
1
0
0
0
0
3
0
1
0
0
0
0
0
0
0
0
4
0
1
0
0
0
1
0
1
0
0
5
1
0
0
0
0
1
1
0
1
1
6
0
1
0
1
1
0
1
0
0
1
7
0
0
0
0
1
1
0
1
1
1
8
1
0
0
1
0
0
1
0
1
0
9
0
0
0
0
1
0
1
1
0
1
0
1
0
0
0
1
1
1
0
1
0
c,

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

Câu hỏi 3
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
0
0
1
0
0
0
0
1
1
2
0
0
0
1
1
0
0
0
0
0
3
0
0
0
0
0
1
1
0
0
0
4
1
1
0
0
1
0
0
0
0
0
5
0
1
0
1
0
0
0
0
0
0
6
0
0
1
0
0
0
1
0
0
0
7
0
0
1
0
0
1
0
0
0
0
8
0
0
0
0
0
0
0
0
1
1
9
1
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
1
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 số thành phần liên thông 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)
B1(Khởi tạo):
Queue= Ø;
Push(Queue,u);
Chuaxet[u]=false;
B2(Lap):
While(Queue ‡ Ø){
s=Pop(Queue);<Tham dinh s>;

for each t Є ke() do{
if(chuaxet[t]){
chuaxet[t]=false;
Push(Queue,t);}
}
B3(Tra lai ket qua)
Return<Tap dinh da tham>
b,
BFS(1)={1(0),4(1),9(1),10(1),2(4),5(4),8(9),10(9)};
BFS(3)={3(0),6(3),7(3)}
èĐồ thị có 2 thành phần liên thông
TP liên thông thứ 1: {1,2,4,5,8,9,10}
TP liên thông thứ 2:{3,6,7}.
Câu hỏi 4:
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
0
0
0
0
1
0
0
0
0
2
0
0
0
1
1
0
0
0
0
0
3
0
0
0
1
1
0
0
0
1
1
4
0
1
1
0
1
0
0
0
0
0
5
0
1
1
1
0
0
0
0
0
0
6
1
0
0
0
0
0
1
0
0
0
7
0
0
0
0
0
1
0
0
0
0
8
0
0
0
0
0
0
0
0
1
1
9
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
1
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 số thành phần liên thông 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):
Bước 1: (Khởi tạo)
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(t,Queue);


}
      }
}
Buoc 3: (Tra lai ket qua)
Return(<Tap dinh da tham>);
b,
BFS(1)={1(0),6(1),7(6)};
BFS(2)={2(0),4(2),5(2),3(4),9(3),10(3),8(9)};
=>Số thành phần liên thông k=2;
TPLT thứ 1:{1,6,7};
TPLT thứ 2:{2,3,4,5,8,9,10}.
Câu hỏi 5
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
0
0
1
0
0
0
0
1
1
2
0
0
0
1
1
0
0
0
0
0
3
0
0
0
0
0
1
0
0
0
0
4
1
1
0
0
1
0
0
0
0
0
5
0
1
0
1
0
0
0
0
0
0
6
0
0
1
0
0
0
1
0
0
0
7
0
0
0
0
0
1
0
0
0
0
8
0
0
0
0
0
0
0
0
1
1
9
1
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
1
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 tất cả các cạnh cầu 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):
Bước 1: (Khởi tạo)
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),4(1),9(1),10(1),2(4),5(4),8(9)}
BFS(3)={3(0),6(3),7(6)}
èk=2;

Cạnh e
Số tp lt l of G/{e}
l>k
Cạnh cầu
(1,4)
BFS(1)={1(0),9(1),10(1),8(9)}
BFS(2)={2(0),4(2),5(2)}
BFS(3)={3(0),6(3),7(6)};
=>l=3
Yes
(1,4)
(1,9)
BFS(1)={1(0),4(1),10(1),2(4),5(4),8(10),9(10),10(8)}
BFS(3)={3(0),6(3),7(6)}
=> l=2
No
--------
(1,10)
BFS(1)={1(0),4(1),9(1), 2(4),5(4),8(9),10(9)}
BFS(3)={3(0),6(3),7(6)}
=>l=2
No
--------
(2,4)
BFS(1)={1(0),4(1),9(1),10(1),5(4),8(9),2(5)}
BFS(3)={3(0),6(3),7(6)}
=> l=2
No
--------
(4,5)
BFS(1)={1(0),4(1),9(1),10(1),2(4),8(9),5(2)}
BFS(3)={3(0),6(3),7(6)}
=>l=2
No
--------
(8,9)
BFS(1)={}
------------------
=>l=2
No
--------
(3,6)
BFS(1)={1(0),4(1),9(1),10(1),2(4),5(4),8(9)}
BFS(3)={3(0)};
BFS(6)={6(0),7(6)}
=>l=3
Yes
(3,6)
(6,7)
BFS(1)={1(0),4(1),9(1),10(1),2(4),5(4),8(9)}
BFS(3)={3(0),6(3)};
BFS(7)={7(0)};
=>l=3;
Yes
(6,7)





KL: Có 3 cạnh cầu (1,4);(3,6);(6,7)

Câu hỏi 6
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
0
0
0
0
1
0
0
0
0
2
0
0
0
1
1
0
0
0
0
0
3
0
0
0
1
1
0
0
0
1
1
4
0
1
1
0
1
0
0
0
0
0
5
0
1
1
1
0
0
0
0
0
0
6
1
0
0
0
0
0
1
0
0
0
7
0
0
0
0
0
1
0
0
0
0
8
0
0
0
0
0
0
0
0
1
1
9
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
1
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 tất cả các đỉnh trụ 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):
Bước 1: (Khởi tạo)
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),6(1),7(6)}
BFS(2)={2(0),4(2),5(2),3(4),9(3),8(9),10(9)}
=>k=2

Đỉnh u
Số tp lt l of G/{u}
l>k
Đỉnh trụ
1
BFS(2)={2(0),4(2),5(2),3(4),9(3),8(9),10(9)}
BFS(6)={6(0),7(6)};
=>l=2;
No
---------
2
BFS(1)={1(0),6(1),7(6)}
BFS(3)={3(0),4(3),5(3),9(3),10(3),8(9)}
=>l=2
No
--------
3
BFS(1)={1(0),6(1),7(6)}
BFS(2)={2(0),4(2),5(2)}
BFS(8)={8(0),9(8),10(8)}
=>l=3
Yes
3
4
BFS(1)={1(0),6(1),7(6)}
BFS(2)={2(0), 5(2),3(5),9(3),10(3),8(9)}
=>l=2
No
---------
5
BFS(1)={1(0),6(1),7(6)}
BFS(2)={2(0),4(2),3(4),9(3),8(9),10(9),9(10)}
=>l=2
No
---------
6
BFS(1)={1(0)}
BFS(2)={2(0),4(2),5(2),3(4),9(3),8(9),10(9)}
BFS(7)={7(0)}
=>l=3
Yes
6
7
BFS(1)={1(0),6(1)}
BFS(2)={2(0),4(2),5(2),3(4),9(3),8(9),10(9)}
=>l=2
No
--------
8
BFS(1)={1(0),6(1),7(6)}
BFS(2)={2(0),4(2),5(2),3(4),9(3), 10(9)}
=>l=2
No
--------
9
BFS(1)={1(0),6(1),7(6)}
BFS(2)={2(0),4(2),5(2),3(4),10(3),8(10)}
=>l=2
No
--------
10
BFS(1)={1(0),6(1),7(6)}
BFS(2)={2(0),4(2),5(2),3(4),9(3),8(9)}
=>l=2
No
------

Câu hỏi 7
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
Câu hỏi 8
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 9
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:



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

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 10
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:


1
2
3
4
5
6
7
8
9
0
1
0
1
1
0
0
0
0
0
0
0
2
0
0
1
1
1
0
0
0
0
0
3
0
0
0
0
0
0
0
0
1
1
4
0
0
0
0
0
1
1
0
0
0
5
0
0
0
0
0
1
0
0
0
0
6
0
0
0
0
0
0
1
1
0
0
7
0
0
0
1
0
0
0
1
0
0
8
1
1
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
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,
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(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 11
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
1
0
0
1
0
1
2
1
0
1
1
0
1
0
0
0
0
3
0
1
0
1
0
0
0
0
0
0
4
0
1
1
0
0
0
0
0
0
0
5
1
0
0
0
0
1
1
1
1
1
6
0
1
0
0
1
0
0
0
0
0
7
0
0
0
0
1
0
0
1
1
1
8
1
0
0
0
1
0
1
0
0
1
9
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
1
0
1
1
0
0
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 12
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
1
0
0
1
0
1
2
1
0
1
1
0
1
0
0
0
0
3
0
1
0
1
0
0
0
0
0
0
4
0
1
1
0
0
1
0
0
0
0
5
1
0
0
0
0
1
1
1
1
1
6
0
1
0
1
1
0
1
0
0
0
7
0
0
0
0
1
1
0
1
1
0
8
1
0
0
0
1
0
1
0
0
0
9
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
Hãy thực hiện:
a)     Phát biểu điều kiện  đủ để một đồ thị vô hướng là đồ thị nửa Euler?
b)     Chứng minh đồ thị G đã cho là đồ thị nửa Euler?
Giải:
a,
Một đồ thị vô hướng là đồ thị nửa Euler khi và chỉ khi số đỉnh v thuộc V có bậc lẻ không vượt quá 2. 
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)=3
Deg(5)=6
Deg(6)=4
Deg(7)=4
Deg(8)=3
Deg(9)=2
Deg(10)=2
àCó 2 đỉnh 4 và 8 là đinh bậc lẻ (2)
(1),(2)è đồ thị G đã cho là đồ thị nửa Euler.
 Câu hỏi 13
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
1
0
0
1
0
1
2
1
0
1
1
0
1
0
0
0
0
3
0
1
0
1
0
0
0
0
0
0
4
0
1
1
0
0
0
0
0
0
0
5
1
0
0
0
0
1
1
1
1
1
6
0
1
0
0
1
0
0
0
0
0
7
0
0
0
0
1
0
0
1
1
1
8
1
0
0
0
1
0
1
0
0
1
9
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
1
0
1
1
0
0
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)}
à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 14
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
Đỉnh 1
Đỉnh 2
Đỉnh 3
Đỉnh 4
Đỉnh 5
Đỉnh 6
Đỉnh 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 15
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(V‡ Ø){
<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,m)).(m là đỉnh cuối)
b,

Các bước thực hiện thuật toán Dijkstra tại s=1
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)

*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 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/

Nhận xét

1 nhận xét:

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