Bài tập ôn thi môn Toán rời rạc
BÀI TẬP ÔN THI MÔN TOÁN RỜI RẠC
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(3) = 2, 4, 5, 10
Ke(4) = 2, 3, 5, 6, 7, 8
Ke (5) = 3, 4, 6
Ke (7) = 4, 6, 8
Ke (8) = 2, 4, 7, 9
Ke (9) = 1, 2, 8, 10
Ke (10)= 1, 2, 3, 9
Hãy thực hiện:
a) Tìm deg(u) với mọi uV?
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?
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
1
1
1
2
2
2
4
4
5
2
5
8
10
3
4
6
6
8
6
5
5
5
6
6
7
7
7
8
9
7
9
10
7
10
8
9
10
9
10
Hãy thực hiện:
a) Tìm deg(u) với mọi uV?
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ề?
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 1 0 1 1 0 0
2 0 0 1 1 0 1 0 0 0 0
3 0 1 0 1 0 1 1 1 0 0
4 1 1 1 0 1 1 1 1 0 0
5 1 0 0 1 0 1 1 1 0 0
6 0 1 1 1 1 0 0 1 0 0
7 1 0 1 1 1 0 0 1 0 0
8 1 0 1 1 1 1 0 0 0 0
9 0 0 0 0 0 0 0 0 0 1
http://www.ptitvl.com – Ngân Hàng Đề Thi
0 0 0 0 0 0 0 0 0 1 0
Hãy thực hiện:
a) Tìm deg(u) với mọi uV? (Không LT)
b) Hãy biểu diễn đồ thị G =<V, E> dưới dạng danh sách cạnh?
c) Hãy biểu diễn đồ thị G =<V, E> dưới dạng danh sách kề?
Câu hỏi 4
Cho đa đồ 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
1
1
1
1
1
2
2
3
3
2
2
2
2
3
5
3
5
4
7
4
4
4
5
5
6
8
8
8
9
6
7
7
8
9
7
9
9
10
10
Hãy thực hiện:
a) Tìm deg(u) với mọi uV?
b) Hãy biểu diễn đồ thị G =<V, E> dưới dạng ma trận kề?
c) Tìm số đường đi độ dài 2 trên đồ thị G từ đỉnh 1 đến các đỉnh 3, 7 và 10?
Câu hỏi 5
Cho đa đồ 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 2 0 2 0 0 0 0 0 0
2 2 0 1 1 1 0 0 0 0 0
3 0 1 0 1 1 0 0 0 0 0
4 2 1 1 0 2 0 0 0 0 0
5 0 1 1 2 0 2 1 0 0 0
6 0 0 0 0 2 0 0 2 0 0
7 0 0 0 0 1 0 0 1 0 0
8 0 0 0 0 0 2 1 0 1 2
9 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 2 1 0
Hãy thực hiện:
a) Tìm deg(u) với mọi uV? (Không LT)
b) Hãy biểu diễn đồ thị G =<V, E> dưới dạng danh sách cạnh?
c) Tìm số đường đi từ đỉnh 4 đến các đỉnh 1, 5 và 9?
Câu hỏi 6
Cho đơn đồ thị có 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) = 4, 10
Ke(2) = 4, 5, 6
Ke(3) = 8
Ke (6) = 1, 4, 7
Ke (7) = 3, 9
Ke (8)= 7, 9
Ke(9) = 8
Ke(4) = 2, 10
http://www.ptitvl.com – Ngân Hàng Đề Thi
Ke (5) = 7, 8
Ke(10) = 1, 2
Hãy thực hiện:
a) Tìm deg+(u), deg-(u) với mọi uV?
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?
Câu hỏi 7
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 1 0 0 0 1
0 1 1 0 0 0 0 0 0 0 0
Hãy thực hiện:
a) Tìm deg+(u), deg-(u) với mọi uV?
b) Hãy biểu diễn đồ thị G =<V, E> dưới dạng danh sách kề?
c) Hãy biểu diễn đồ thị G =<V, E> dưới dạng danh sách cạnh?
Câu hỏi 8
Cho đơn đồ thị có 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
1
2
2
2
3
4
4
5
5
2
5
3
4
5
6
6
7
9
6
6
7
7
8
8
9
9
10
10
7
8
2
8
1
10
6
7
1
4
10
Hãy thực hiện:
a) Tìm deg+(u), deg-(u) với mọi uV?
b) Hãy biểu diễn đồ thị G =<V, E> dưới dạng danh sách kề?
c) Hãy biểu diễn đồ thị G =<V, E> dưới dạng ma trận kề?
http://www.ptitvl.com – Ngân Hàng Đề Thi
Câu hỏi 9
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?
http://www.ptitvl.com – Ngân Hàng Đề Thi
Câu hỏi 10
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 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 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?
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 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?
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 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:
http://www.ptitvl.com – Ngân Hàng Đề Thi
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 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?
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 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?
Câu hỏi 14
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 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 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?
http://www.ptitvl.com – Ngân Hàng Đề Thi
Câu hỏi 15
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?
Câu hỏi 16
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 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 đỉ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?
Câu hỏi 17
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
http://www.ptitvl.com – Ngân Hàng Đề Thi
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?
Câu hỏi 18
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 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 0 0 0 1 0 0 1 0 1 0
9 0 0 0 0 1 0 1 1 0 1
0 1 1 0 0 1 1 1 0 1 0
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 một đường đi ít cạnh nhất từ đỉnh 3 đến
đỉnh 9 của đồ thị G, chỉ rõ kết quả tại mỗi bước thực hiện theo thuật toán?
Câu hỏi 19
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 bao trùm của đồ thị G, chỉ rõ kết
quả tại mỗi bước thực hiện theo thuật toán?
http://www.ptitvl.com – Ngân Hàng Đề Thi
Câu hỏi 20
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 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 0 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
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 cây khung của đồ thị G, bắt đầu từ u =
3 chỉ rõ kết quả tại mỗi bước thực hiện theo thuật toán?
Câu hỏi 21
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
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 ít cạnh nhất từ đỉnh
2 đến đỉnh 8 của đồ thị G, chỉ rõ kết quả tại mỗi bước thực hiện theo thuật toán?
http://www.ptitvl.com – Ngân Hàng Đề Thi
Câu hỏi 22
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
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) Chứng minh rằng G là đồ thị liên thông yếu nhưng không liên thông mạnh?
Câu hỏi 23
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
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 chứng minh rằng G là đồ thị liên
thông mạnh?
Câu hỏi 24
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 0 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
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?
http://www.ptitvl.com – Ngân Hàng Đề Thi
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?
Câu hỏi 25
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?
Câu hỏi 26
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?
Câu hỏi 27
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
http://www.ptitvl.com – Ngân Hàng Đề Thi
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
Câu hỏi 28
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) Trình bày thuật toán tìm một đường đi Euler của đồ thị?
b) Áp dụng thuật toán, tìm một đường đi Euler 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
Câu hỏi 29
Cho đa đồ 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 4 1 0 1 0 0 0 0 0
2 4 0 1 0 1 0 0 0 0 0
3 1 1 0 1 0 0 1 0 0 0
4 0 0 1 0 0 1 2 0 0 0
5 1 1 0 0 0 0 0 1 1 0
6 0 0 0 1 0 0 1 0 0 0
7 0 0 1 2 0 1 0 0 0 0
8 0 0 0 0 1 0 0 0 2 1
9 0 0 0 0 1 0 0 2 0 1
0 0 0 0 0 0 0 0 1 1 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?
Câu hỏi 30
Cho đa đồ 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 2 0 2 0 0 0 0 0 0
2 2 0 1 1 0 0 0 0 0 0
3 0 1 0 1 1 0 0 0 0 0
4 2 1 1 0 2 0 0 0 0 0
5 0 0 1 2 0 2 1 0 0 0
http://www.ptitvl.com – Ngân Hàng Đề Thi
6 0 0 0 0 2 0 0 2 0 0
7 0 0 0 0 1 0 0 1 0 0
8 0 0 0 0 0 2 1 0 1 2
9 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 2 1 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?
Câu hỏi 31
Cho đa đồ 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 4 1 0 1 0 0 0 0 0
2 4 0 1 0 1 0 0 0 0 0
3 1 1 0 1 0 0 1 0 0 0
4 0 0 1 0 0 1 2 0 0 0
5 1 1 0 0 0 0 0 1 1 0
6 0 0 0 1 0 0 1 0 0 0
7 0 0 1 2 0 1 0 0 0 0
8 0 0 0 0 1 0 0 0 2 1
9 0 0 0 0 1 0 0 2 0 1
0 0 0 0 0 0 0 0 1 1 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 6,
chỉ rõ kết quả tại mỗi bước thực hiện theo thuật toán?
Câu hỏi 32
Cho đa đồ 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 2 0 2 0 0 0 0 0 0
2 2 0 1 1 0 0 0 0 0 0
3 0 1 0 1 1 0 0 0 0 0
4 2 1 1 0 2 0 0 0 0 0
5 0 0 1 2 0 2 1 0 0 0
6 0 0 0 0 2 0 0 2 0 0
7 0 0 0 0 1 0 0 1 0 0
8 0 0 0 0 0 2 1 0 1 2
9 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 2 1 0
Hãy thực hiện:
a) Trình bày thuật toán tìm một đường đi Euler của đồ thị?
a) Áp dụng thuật toán, tìm một đường đi Euler 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?
http://www.ptitvl.com – Ngân Hàng Đề Thi
Câu hỏi 33
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
Hãy thực hiện:
a) Phát biểu điều kiện cần và đủ để một đồ thị cô hướng là đồ thị Euler?
b) Chứng minh đồ thị G đã cho là đồ thị Euler?
http://www.ptitvl.com – Ngân Hàng Đề Thi
Câu hỏi 34
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 0 0 1 0 0 0 0 0
2 0 0 1 1 0 1 0 0 0 0
3 0 0 0 1 0 0 0 0 0 0
4 0 0 0 0 0 1 1 0 0 0
5 0 0 0 0 0 0 0 1 1 0
6 0 0 0 0 1 0 1 0 0 0
7 0 0 0 0 0 0 0 1 0 1
8 1 0 0 0 0 0 0 0 0 0
9 0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0
Hãy thực hiện:
a) Phát biểu điều kiện đủ để một đồ thị cos hướng là đồ thị nửa Euler?
b) Chứng minh đồ thị G đã cho là đồ thị nửa Euler?
http://www.ptitvl.com – Ngân Hàng Đề Thi
c)
Câu hỏi 35
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
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?
http://www.ptitvl.com – Ngân Hàng Đề Thi
Câu hỏi 36
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 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 0 1 0 1 0 0 0
7 0 0 0 0 1 0 0 1 1 1
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 1 0 0 0
Hãy thực hiện:
a) Trình bày thuật toán tìm một đường đi Euler của đồ thị?
b) Áp dụng thuật toán, tìm một đường đi Euler 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?
Câu hỏi 37
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 1 0 1 0 0 1 0 0 1
9 1 1 0 0 0 0 0 1 0 1
0 1 1 1 0 0 0 0 1 1 0
Hãy thực hiện:
a) Trình bày thuật toán quay lui để tìm một chu trình Hamilton của đồ thị?
b) Áp dụng thuật toán quay lui tìm một chu trình Hamilton của đồ thị G đã cho bắt đầu
từ đỉnh 1, khi có nhiều khả năng lựa chọn các đỉnh luôn ưu tiên chọn đỉnh có chỉ số
nhỏ nhất và giải thích các bước thực hiện?
Câu hỏi 38
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 1 0 0 0 0 1 1 1 0 0
6 0 0 0 0 0 0 1 1 0 0
7 0 0 0 0 1 0 0 1 0 0
8 1 0 0 0 1 0 0 0 0 0
http://www.ptitvl.com – Ngân Hàng Đề Thi
9 0 0 0 0 0 0 0 0 0 1
0 1 0 0 1 0 0 0 0 0 0
Hãy thực hiện:
a) Trình bày thuật toán quay lui để tìm một chu trình Hamilton của đồ thị?
b) Áp dụng thuật toán quay lui tìm một chu trình Hamilton của đồ thị G đã cho bắt đầu
từ đỉnh 1, khi có nhiều khả năng lựa chọn các đỉnh luôn ưu tiên chọn đỉnh có chỉ số
nhỏ nhất và giải thích các bước thực hiện?
Câu hỏi 39
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
0
20
5
17
2
20
0
1
1
3
5
0
25
3
10
4
17
1
25
0
15
5
6
10
1
7
1
1
1
2
3
4
5
6
7
3
15
0
1
0
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?
Câu hỏi 40
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
0
2
3
4
5
6
1
7
30
45
3
25
0
1
2
3
4
5
6
7
10 15 20
0
10 25
2
1
3
35
0
3
0
25
0
1
0
3
1
30
1
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?
Câu hỏi 41
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
0
2
15
0
7
3
8
0
4
5
6
1
7
9
1
1
2
3
4
5
4
0
2
1
0
10
http://www.ptitvl.com – Ngân Hàng Đề Thi
6
7
14
2
2
0
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
Câu hỏi 42
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
0
25
27
2
25
0
1
3
4
27
15
0
25
5
1
3
25
0
6
30
1
0
7
15
1
1
2
3
4
5
6
7
0
15
3
1
15
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 2 đến đỉnh 6 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
Câu hỏi 43
Cho đơn đồ thị G = <V, E> gồm 6 đỉnh được biểu diễn dưới dạng ma trận trọng số như sau
1
2
3
4
5
6
1 0 15 5 20
50
70
10
2
3
1
0
1
10
17
2
0
0
0
4 15
5 20 30
18
10
23
6
20 0
Hãy thực hiện:
a) Trình bày thuật toán Floyd tìm đường đi ngắn nhất giữa các cặp đỉnh trong đồ thị?
b) Áp dụng thuật toán Floyd, tìm đường đi ngắn nhất giữa các cặp đỉnh (1, 2), (1, 3), (3,
4), (4, 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?
Câu hỏi 44
Cho đơn đồ thị G = <V, E> gồm 6 đỉnh được biểu diễn dưới dạng ma trận trọng số như sau
1
2
3
4
5
6
1 0
15
0
1
1
0
5
20
30
7
1
0
20
7
2
5
1
3 15
4
5
20 20
0
5
5
0
6 20 30 20
Hãy thực hiện:
a) Trình bày thuật toán Floyd tìm đường đi ngắn nhất giữa các cặp đỉnh trong đồ thị?
http://www.ptitvl.com – Ngân Hàng Đề Thi
b) Áp dụng thuật toán Floyd, tìm đường đi ngắn nhất giữa các cặp đỉnh (1, 2), (1, 6), (2,
5), (5, 6) 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?
Câu hỏi 45
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 trọng số như
sau
1 2 3 4 5 6 7 8 9 0
1 0 4 1 1 2 9
5 4 7
2 4 0 2
3 1 2 0 7
4 1 7 0 1 7
5 2 9
6 9 1 6 7 3 0 3 1 1 5
5 6 4 3 0 4 5
9 1 5
6
6 6 1 1 9
6
1 0 3 4 3 1 2
7
8 5
9 4 6 1
0 7
1 6 3 1 4 0 4 2
1 1 5 4 0 4
2 5
9
2 4 0
Hãy thực hiện:
a) Trình bày thuật toán Kruskal tìm cây khung nhỏ nhất trên đồ thị vô hướng, liên thông,
có trọng số?
b) Áp dụng thuật toán Kruskal, tìm cây khung nhỏ nhất 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?
Câu hỏi 46
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 trọng số như
sau
1 2 3 4 5 6 7 8 9 0
1 0 4 1 1 2 9
5 4 7
2 4 0 2
3 1 2 0 7
4 1 7 0 1 7
5 2 9
6 9 1 6 7 3 0 3 1 1 5
5 6 4 3 0 4 5
9 1 5
6
6 6 1 1 9
6
1 0 3 4 3 1 2
7
8 5
9 4 6 1
0 7
1 6 3 1 4 0 4 2
1 1 5 4 0 4
2 5
9
2 4 0
Hãy thực hiện:
a) Trình bày thuật toán Prim tìm cây khung nhỏ nhất bắt đầu từ đỉnh s = 1 trên đồ thị vô
hướng, liên thông, có trọng số?
b) Áp dụng thuật toán Prim tìm cây khung nhỏ nhất 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?
http://www.ptitvl.com – Ngân Hàng Đề Thi
Tải về để xem bản đầy đủ
24 trang
26580
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài tập ôn thi môn Toán rời rạc", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_tap_on_thi_mon_toan_roi_rac.pdf
