Đồ thị phân đôi đầy đủ K_n,m có số màu bằng:

-2

Trả lời:

Đáp án đúng: C

Đồ thị phân đôi đầy đủ K_n,m là đồ thị mà tập đỉnh của nó có thể chia thành hai tập rời nhau X và Y, sao cho |X| = n và |Y| = m, và mọi đỉnh trong X đều kề với mọi đỉnh trong Y. Để tô màu cho đồ thị này, ta có thể sử dụng hai màu. Một màu cho tất cả các đỉnh trong X và một màu khác cho tất cả các đỉnh trong Y. Vì không có cạnh nào nối giữa hai đỉnh trong cùng một tập (X hoặc Y), nên không có hai đỉnh kề nhau nào có cùng màu. Do đó, số màu cần thiết là 2.

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 10

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 35:

Theo định lý Ford – Fulkerson giá trị luồng cực đại từ điểm phát s đến điểm thu t.

Lời giải:

Đáp án đúng: A

Định lý Ford-Fulkerson phát biểu rằng giá trị luồng cực đại từ điểm phát s đến điểm thu t bằng khả năng thông qua (capacity) của lát cắt hẹp nhất (minimum cut) tách điểm s và t. Lát cắt hẹp nhất là lát cắt có tổng khả năng thông qua nhỏ nhất trong tất cả các lát cắt tách s và t. Vì vậy, đáp án A là đáp án chính xác.

Câu 36:

Nếu G = (V, E) là một đơn đồ thị vô hướng thì: (Chọn phương án đúng)

Lời giải:

Đáp án đúng: A

Trong một đơn đồ thị vô hướng G = (V, E), ma trận kề biểu diễn mối quan hệ giữa các đỉnh. Vì đồ thị là vô hướng, nên nếu có một cạnh nối đỉnh i và đỉnh j, thì cũng có một cạnh nối đỉnh j và đỉnh i. Điều này có nghĩa là phần tử ở hàng i, cột j của ma trận kề sẽ bằng phần tử ở hàng j, cột i. Do đó, ma trận kề của một đơn đồ thị vô hướng là một ma trận đối xứng qua đường chéo chính.

Phương án A đúng vì nó phản ánh tính chất đối xứng của ma trận kề trong đồ thị vô hướng.

Phương án B sai vì nó khẳng định ma trận kề không đối xứng.

Phương án C sai vì các phần tử trên đường chéo chính của ma trận kề bằng 1 khi có một vòng lặp (cạnh nối một đỉnh với chính nó), nhưng trong một đơn đồ thị (không có vòng lặp), các phần tử này thường bằng 0.

Phương án D sai vì không có quy tắc nào quy định các phần tử trên đường chéo phụ phải bằng 1.

Câu 37:

Trong biểu diễn đồ thị bởi danh sách kề, mỗi đỉnh của đồ thị có một danh sách:

Lời giải:

Đáp án đúng: C

Trong biểu diễn đồ thị bằng danh sách kề, mỗi đỉnh của đồ thị sẽ có một danh sách chứa các đỉnh kề với nó. Đỉnh kề là đỉnh có cạnh nối trực tiếp với đỉnh đang xét. Vì vậy, đáp án C là đáp án chính xác.

Các phương án khác không đúng vì:

* A. Các cạnh kề với đỉnh đó: Danh sách kề lưu trữ các đỉnh, không phải các cạnh.
* B. Các bậc của đỉnh kề với đỉnh đó: Bậc của đỉnh là số lượng cạnh nối với đỉnh đó, không phải là nội dung được lưu trong danh sách kề.
* D. Các cạnh kề với cạnh đó: Cạnh không có danh sách kề trong biểu diễn đồ thị bằng danh sách kề. Danh sách kề dùng để biểu diễn quan hệ giữa các đỉnh.

Câu 38:

Đồ thị lập phương Q_n là đồ thị:

Lời giải:

Đáp án đúng: C

Đồ thị lập phương Q_n là một đồ thị có 2^n đỉnh. Mỗi đỉnh của đồ thị được biểu diễn bởi một xâu bit có độ dài n. Hai đỉnh được coi là kề nhau nếu và chỉ nếu hai xâu bit tương ứng của chúng khác nhau đúng một bit.

* Phương án A: Sai vì thiếu thông tin quan trọng là các đỉnh được biểu diễn bằng xâu bit độ dài n.
* Phương án B: Sai vì hai đỉnh kề nhau chỉ khác nhau một bit, không phải nhiều nhất hai bit.
* Phương án C: Đúng, đây là định nghĩa chính xác của đồ thị lập phương Q_n.
* Phương án D: Sai vì đồ thị lập phương Q_n có 2^n đỉnh, không phải n đỉnh.

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

Câu 39:

Chu trình Euler đi qua mỗi đỉnh của đồ thị:

Lời giải:

Đáp án đúng: C

Chu trình Euler là một chu trình đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần. Do đó, một đỉnh có thể được thăm nhiều lần trong chu trình Euler, miễn là mỗi cạnh kề với đỉnh đó được đi qua đúng một lần.

Câu 40:

Đồ thị G được gọi là nửa Hamilton nếu tồn tại đường đi đi qua tất cả các đỉnh của đồ thị.

Lời giải: