Nếu G = (V,E) là một đồ thị vô hướng thì:

Số đỉnh bậc lẻ và số đỉnh bậc chẵn là một số chẵn

Số đỉnh bậc chẵn là một số chẵn

Số đỉnh bậc lẻ là một số chẵn

Số đỉnh bậc lẻ là một số lẻ

Trả lời:

Đáp án đúng: C

Trong một đồ thị vô hướng G = (V, E), tổng bậc của tất cả các đỉnh bằng hai lần số cạnh (∑deg(v) = 2|E|). Vì 2|E| là một số chẵn, nên tổng bậc của tất cả các đỉnh phải là một số chẵn. Điều này chỉ xảy ra khi số lượng đỉnh bậc lẻ là một số chẵn, vì nếu có một số lẻ các đỉnh bậc lẻ, thì tổng bậc của các đỉnh sẽ là một số lẻ (tổng của một số chẵn và một số lẻ là một số lẻ).

525 câu trắc nghiệm môn Toán rời rạc kèm lời giải chi tiết - Phần 15

Bộ 525 câu hỏi trắc nghiệm ôn thi môn Toán rời rạc có đáp án dưới đây sẽ là tài liệu ôn tập hữi ích dành cho các bạn sinh viên. Mời các bạn cùng tham khảo!

30 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 21:

Cho đồ thị vô hướng G = (V,E), khẳng định nào sau đây là đúng?

Lời giải:

Đáp án đúng: A

Thuật toán DFS (Depth-First Search) xuất phát từ một đỉnh u và duyệt theo chiều sâu đến khi không còn đỉnh nào kề với đỉnh đang xét chưa được duyệt. Khi đó, thuật toán quay lui về đỉnh trước đó và tiếp tục duyệt các đỉnh kề chưa được duyệt khác. Quá trình này tiếp tục cho đến khi tất cả các đỉnh có thể đến được từ đỉnh u đều đã được duyệt. Do đó, DFS(u) duyệt tất cả các đỉnh trong cùng thành phần liên thông với đỉnh u. Các phương án khác không đúng vì DFS(u) chỉ duyệt các đỉnh có thể đến được từ u, không duyệt toàn bộ đồ thị nếu đồ thị không liên thông và cũng không đảm bảo tìm được đường đi giữa hai đỉnh bất kỳ nếu chúng không thuộc cùng thành phần liên thông. DFS(u) cũng có thể không duyệt tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần nếu đồ thị có chu trình.

Câu 22:

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

Lời giải:

Đáp án đúng: A

Đơn đồ thị vô hướng là đồ thị không có khuyên (loop) và không có cạnh bội (multiple edges). Khuyên là cạnh nối một đỉnh với chính nó. Cạnh bội là hai hay nhiều cạnh nối cùng một cặp đỉnh.

Câu 23:

Đồ thị G = (V,E) được gọi là đồ thị vô hướng nếu:

Lời giải:

Đáp án đúng: B

Đồ thị vô hướng là đồ thị mà các cạnh của nó không có hướng. Tức là, nếu có một cạnh nối hai đỉnh u và v, thì cạnh đó chỉ đơn thuần thể hiện mối quan hệ giữa u và v, chứ không chỉ ra chiều đi từ u đến v hay từ v đến u. Do đó, đáp án đúng là "Mọi cạnh của G là cạnh vô hướng". Các phương án khác không đúng vì chúng hoặc là không đầy đủ (chỉ một số cạnh vô hướng) hoặc mâu thuẫn với định nghĩa đồ thị vô hướng (mọi cạnh có hướng).

Câu 24:

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ế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 sẽ đối xứng qua đường chéo chính.

Câu 25:

Đường đi trong đồ thị G vô hướng từ đỉnh s đến đỉnh t là một dãy:

Lời giải:

Đáp án đúng: B

Đường đi trong đồ thị vô hướng từ đỉnh s đến đỉnh t là một dãy các đỉnh kề nhau, bắt đầu từ s và kết thúc tại t. Mỗi cặp đỉnh liên tiếp trong dãy phải kề nhau, và các cạnh nối các đỉnh liên tiếp đó phải phân biệt.

Phương án 1: Sai, vì chỉ nói các cạnh kề nhau mà không đề cập đến đỉnh đầu và đỉnh cuối cũng như tính liên tục của đường đi.
Phương án 2: Đúng, đáp án này mô tả chính xác định nghĩa đường đi trong đồ thị vô hướng. Dãy đỉnh bắt đầu từ s, kết thúc tại t, các đỉnh liên tiếp kề nhau, và các cạnh nối các đỉnh này khác nhau.
Phương án 3: Sai, vì các cạnh phải kề nhau (tức là có đỉnh chung) để tạo thành một đường đi.
Phương án 4: Sai, vì các đỉnh phải kề nhau (tức là có cạnh nối) để tạo thành một đường đi.

Câu 26:

Đa đồ thị liên thông G có chu trình Hamilton nếu:

Lời giải: