Bậc của đỉnh trong đồ thị có hướng G là:

Số cạnh đi vào đỉnh đó.

Số cạnh đi ra khỏi đỉnh đó.

Tổng của cạnh đi vào và số cạnh đi ra khỏi đỉnh đó.

Hiệu của cạnh đi vào và cạnh đi ra khỏi đỉnh đó

Trả lời:

Đáp án đúng: C

Trong đồ thị có hướng, bậc của một đỉnh được định nghĩa là tổng số cạnh đi vào đỉnh đó (bán bậc vào) và số cạnh đi ra khỏi đỉnh đó (bán bậc ra). Vì vậy, đáp án C là đáp án chính xác nhất.

500+ câu hỏi trắc nghiệm Toán rời rạc có đáp án kèm giải thích - Phần 3

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 41:

Đồ thị C_n có số đỉnh và số cạnh tương ứng là:

Lời giải:

Đáp án đúng: B

Đồ thị C_n (đồ thị chu trình) là một đồ thị có n đỉnh và n cạnh, trong đó các đỉnh được sắp xếp thành một vòng tròn và mỗi đỉnh được nối với hai đỉnh lân cận của nó. Do đó, số đỉnh của C_n là n và số cạnh của C_n là n.

Câu 42:

Cho mạng G, điểm phát s điểm thu t. Tính cân bằng của luồng f trên mạng G phải thỏa mãn cho:

Lời giải:

Đáp án đúng: D

Trong bài toán luồng cực đại, tính cân bằng của luồng (hay còn gọi là bảo toàn luồng) là một điều kiện tiên quyết. Điều này có nghĩa là, tại mọi đỉnh của mạng (trừ đỉnh phát s và đỉnh thu t), lượng luồng vào phải bằng lượng luồng ra. Đỉnh phát s là nơi luồng được tạo ra, và đỉnh thu t là nơi luồng được hấp thụ. Vì vậy, cân bằng luồng không áp dụng cho hai đỉnh này.

Câu 43:

Cho đồ thị G = (V, E) vô hướng. Bậc của các đỉnh 1, 2, 3, 4, 5 tương ứng là:

Lời giải:

Đáp án đúng: B

Bậc của một đỉnh trong đồ thị vô hướng là số cạnh liên thuộc với đỉnh đó.

Đỉnh 1 có 3 cạnh liên thuộc.
Đỉnh 2 có 4 cạnh liên thuộc.
Đỉnh 3 có 6 cạnh liên thuộc.
Đỉnh 4 có 4 cạnh liên thuộc.
Đỉnh 5 có 4 cạnh liên thuộc.

Vậy, bậc của các đỉnh 1, 2, 3, 4, 5 lần lượt là 3, 4, 6, 4, 4.

Câu 44:

Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(K) là:

Lời giải:

Đáp án đúng: C

Thuật toán DFS (Depth-First Search) hay còn gọi là tìm kiếm theo chiều sâu, là một thuật toán duyệt hoặc tìm kiếm trên các cấu trúc dữ liệu đồ thị. Thuật toán bắt đầu tại một đỉnh gốc (trong trường hợp này là đỉnh K) và khám phá sâu nhất có thể dọc theo mỗi nhánh trước khi quay lui.

Bước 1: Bắt đầu từ đỉnh K.
Bước 2: Chọn đỉnh I (vì I kề với K và chưa được thăm).
Bước 3: Chọn đỉnh A (vì A kề với I và chưa được thăm).
Bước 4: Từ A, ta có thể chọn B hoặc C. Chọn B.
Bước 5: Chọn C.
Bước 6: Chọn D.
Bước 7: Từ D, quay lại C, B, A, I, K (vì tất cả các đỉnh kề đã được thăm).
Bước 8: Từ K, chọn đỉnh chưa được thăm là G.
Bước 9: Chọn H.
Bước 10: Chọn F.
Bước 11: Chọn E.

Vậy thứ tự duyệt đúng là: K, I, A, B, C, D, G, H, F, E.

Câu 45:

Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán DFS(1):

Lời giải:

Đáp án đúng: D

Thuật toán DFS (Depth-First Search - Tìm kiếm theo chiều sâu) xuất phát từ đỉnh 1. Ta duyệt các đỉnh kề theo thứ tự ưu tiên từ trái sang phải theo hình vẽ:
1. Xuất phát từ 1.
2. Đỉnh 1 có các đỉnh kề là 2 và 7. Ưu tiên duyệt đỉnh 2.
3. Đỉnh 2 có đỉnh kề là 3. Duyệt 3.
4. Đỉnh 3 có các đỉnh kề là 6 và 4. Ưu tiên duyệt đỉnh 4.
5. Đỉnh 4 có đỉnh kề là 5. Duyệt 5.
6. Đỉnh 5 có đỉnh kề là 10. Duyệt 10.
7. Quay lại 3. Duyệt 6.
8. Đỉnh 6 có đỉnh kề là 9. Duyệt 9.
9. Quay lại 1. Duyệt 7.
10. Đỉnh 7 có đỉnh kề là 8. Duyệt 8.
Vậy thứ tự duyệt là: 1, 2, 3, 4, 5, 10, 6, 9, 7, 8.

Câu 46:

Cho đồ thị trọng số G = (V, E) như hình vẽ. Cây khung nhỏ nhất H = (V, T) theo thuật toán Prim có tập cạnh:

Lời giải: