Đồ thị G vô hướng nào trong các đồ thị sau là tồn tại nếu các đỉnh có số bậc lần lượt là:
Đáp án đúng: B
Để xác định xem một dãy số có thể là bậc của các đỉnh trong một đồ thị vô hướng hay không, ta sử dụng định lý sau: Một dãy số nguyên không âm d±ợc sắp xếp theo thứ tự giảm dần d1, d2, ..., dn là dãy bậc của một đồ thị vô hướng khi và chỉ khi Σdi chẵn.
A. 2 + 4 + 3 + 1 + 4 + 2 + 5 = 21 (lẻ) - không tồn tại
B. 3 + 4 + 2 + 1 + 4 + 2 + 6 = 22 (chẵn)- có thể tồn tại
C. 5 + 2 + 2 + 1 + 3 + 2 + 4 = 19 (lẻ) - không tồn tại
D. 2 + 1 + 4 + 3 + 4 + 2 + 7 = 23 (lẻ) - không tồn tại
Vậy, chỉ có B là có thể tồn tại.
Câu hỏi liên quan
Đoạn suy diễn "Là phi công thì phải biết lái máy bay. An là phi công nên An biết lái máy bay" tuân theo quy tắc Modus Ponens, hay còn gọi là luật khẳng định. Quy tắc này có dạng: Nếu P thì Q. P xảy ra. Vậy Q xảy ra. Trong trường hợp này, P là "là phi công" và Q là "biết lái máy bay". Vì An là phi công (P xảy ra), suy ra An biết lái máy bay (Q xảy ra). Các đáp án khác không phù hợp vì luật cộng liên quan đến việc thêm một mệnh đề vào một mệnh đề đã cho, luật rút gọn liên quan đến việc loại bỏ một phần của một mệnh đề, và luật phủ định liên quan đến việc phủ định một mệnh đề.
- P: Trường chất lượng cao
- Q: Có cán bộ giảng dạy giỏi
- R: Có sinh viên giỏi
Suy diễn đã cho tuân theo đúng cấu trúc của luật tam đoạn luận. Các lựa chọn khác không phù hợp:
- Luật khẳng định (Modus Ponens): Nếu P thì Q, và P đúng, vậy Q đúng.
- Luật phủ định (Modus Tollens): Nếu P thì Q, và Q sai, vậy P sai.
- Luật tam đoạn luận rời: Liên quan đến các mệnh đề rời rạc (hoặc...hoặc), không phù hợp với cấu trúc suy luận này.
