Đồ thị nào trong các đồ thị không phẳng sau đây có tính chất: bỏ đi một đỉnh bất kỳ và các cạnh liên thuộc với nó tạo ra một đồ thị phẳng.

Trả lời:

Đáp án đúng: A

Đồ thị K5 (đồ thị đầy đủ với 5 đỉnh) là đồ thị không phẳng. Nếu ta loại bỏ một đỉnh và các cạnh liên thuộc với nó, ta sẽ thu được đồ thị K4, là một đồ thị phẳng. Các đồ thị K2, K6, K7 không thỏa mãn tính chất này. K2 là đồ thị phẳng. Khi loại bỏ một đỉnh khỏi K6 hoặc K7, đồ thị con thu được vẫn là đồ thị không phẳng.

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 6

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 36:

Độ phức tạp của thật toán Floyd là:

Lời giải:

Đáp án đúng: C

Thuật toán Floyd-Warshall được sử dụng để tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị có trọng số. Thuật toán này duyệt qua tất cả các đỉnh để cập nhật khoảng cách ngắn nhất giữa mọi cặp đỉnh. Vì thuật toán này lặp qua tất cả các đỉnh ba lần lồng nhau, độ phức tạp thời gian của nó là O(n^3), trong đó n là số lượng đỉnh trong đồ thị.

Câu 37:

Thuật toán Kruskal áp dụng cho đồ thì G, n đỉnh sẽ dừng khi:

Lời giải:

Đáp án đúng: A

Thuật toán Kruskal là một thuật toán tìm cây khung nhỏ nhất cho một đồ thị liên thông có trọng số. Cây khung nhỏ nhất của một đồ thị với n đỉnh sẽ có đúng n-1 cạnh. Thuật toán Kruskal hoạt động bằng cách duyệt qua các cạnh của đồ thị theo thứ tự tăng dần của trọng số, và thêm cạnh đó vào cây khung nếu nó không tạo thành chu trình. Quá trình này lặp lại cho đến khi cây khung có n-1 cạnh. Vậy đáp án đúng là A.

Câu 38:

Hãy cho biết đồ thị nào dưới đây là một cây?

Lời giải:

Đáp án đúng: C

Câu hỏi này kiểm tra kiến thức về định nghĩa và tính chất của cây trong lý thuyết đồ thị.

Một đồ thị được gọi là một cây nếu nó liên thông và không có chu trình.

Phương án A: Đồ thị này liên thông và không có chu trình, do đó nó là một cây.

Phương án B: Đồ thị này có chu trình (ví dụ: đi từ một đỉnh, qua các cạnh, rồi quay lại đỉnh ban đầu), nên nó không phải là một cây.

Phương án C: Đồ thị này có chu trình, nên nó không phải là một cây.

Phương án D: Đồ thị này có chu trình, nên nó không phải là một cây.

Vậy đáp án đúng là A.

Câu 39:

Trong thuật toán Ford – Fullkerson giải bài toán luồng cực đại, bước tăng luồng thực hiện trên.

Lời giải:

Đáp án đúng: B

Trong thuật toán Ford-Fulkerson để tìm luồng cực đại trong một mạng, ta thực hiện việc tăng luồng dọc theo các đường đi tăng (augmenting paths). Đường đi tăng là một đường đi từ đỉnh phát (source) đến đỉnh thu (sink) mà trên đó ta có thể đẩy thêm một lượng luồng nào đó. Việc tăng luồng này được thực hiện bằng cách điều chỉnh luồng trên các cạnh *nằm trên đường đi đánh dấu* (augmenting path) đó. Vì vậy, đáp án đúng là B. Các cạnh nằm trên đường đi đánh dấu.

Câu 40:

Đỉnh cô lập trên đồ thị G là:

Lời giải:

Đáp án đúng: C

Đỉnh cô lập trên đồ thị là đỉnh không có cạnh nối với bất kỳ đỉnh nào khác. Bậc của một đỉnh là số lượng cạnh liên kết với nó. Do đó, đỉnh cô lập là đỉnh có bậc bằng 0.

Câu 41:

Đường đi Euler đi qua mỗi cạnh của đồ thị:

Lời giải: