Cho đồ thị vô hướng G= (V, E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E = {(1,2), (1,3), (1,6), (2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Hỏi G có phải là đồ thị đầy đủ không?
Trả lời:
Đáp án đúng: A
Đồ thị đầy đủ là đồ thị mà giữa hai đỉnh bất kỳ đều có cạnh nối.
Trong đồ thị G đã cho, ta thấy đỉnh 1 không kề với đỉnh 4 và đỉnh 3 không kề với đỉnh 4 và đỉnh 3 không kề với đỉnh 5. Như vậy, đồ thị G không phải là đồ thị đầy đủ.
Câu hỏi liên quan
Lời giải:
Đáp án đúng: B
Duyệt đồ thị theo chiều sâu (DFS - Depth First Search) bắt đầu từ đỉnh 1. Theo thứ tự từ điển, ta chọn đỉnh kề nhỏ nhất chưa được thăm.
1. Bắt đầu từ đỉnh 1, các đỉnh kề là 2, 3, 6. Chọn đỉnh 2.
2. Từ đỉnh 2, các đỉnh kề chưa thăm là 3, 5, 6. Chọn đỉnh 3.
3. Từ đỉnh 3, các đỉnh kề chưa thăm là 6. Chọn đỉnh 6.
4. Từ đỉnh 6, các đỉnh kề chưa thăm là 4, 5. Chọn đỉnh 4.
5. Từ đỉnh 4, đỉnh kề chưa thăm là 5. Chọn đỉnh 5.
Vậy thứ tự duyệt là: 1, 2, 3, 6, 4, 5.
1. Bắt đầu từ đỉnh 1, các đỉnh kề là 2, 3, 6. Chọn đỉnh 2.
2. Từ đỉnh 2, các đỉnh kề chưa thăm là 3, 5, 6. Chọn đỉnh 3.
3. Từ đỉnh 3, các đỉnh kề chưa thăm là 6. Chọn đỉnh 6.
4. Từ đỉnh 6, các đỉnh kề chưa thăm là 4, 5. Chọn đỉnh 4.
5. Từ đỉnh 4, đỉnh kề chưa thăm là 5. Chọn đỉnh 5.
Vậy thứ tự duyệt là: 1, 2, 3, 6, 4, 5.
Lời giải:
Đáp án đúng: A
Chu trình Hamilton là chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần, trừ đỉnh đầu tiên (cũng là đỉnh cuối cùng).
Xét từng phương án:
- Phương án A: 1 – 3 – 2 – 5 – 4 – 6 – 1. Chu trình này đi qua tất cả các đỉnh {1, 2, 3, 4, 5, 6} mỗi đỉnh đúng một lần (trừ đỉnh 1 lặp lại ở cuối). Đây là một chu trình Hamilton.
- Phương án B: 1 – 2 – 3 – 1 – 5 – 4 – 6 – 1. Đỉnh 1 xuất hiện 3 lần, đỉnh 5, 4, 6 mỗi đỉnh xuất hiện 1 lần, đỉnh 2, 3 xuất hiện 1 lần, không phải chu trình Hamilton.
- Phương án C: 3 – 2 – 1 – 5 – 2 – 6 – 5 – 4 – 6 – 1. Các đỉnh 2, 5, 6 xuất hiện nhiều hơn 1 lần. Không phải chu trình Hamilton.
Vậy, phương án A là đáp án đúng.
Lời giải:
Đáp án đúng: B
Ta sẽ thực hiện duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh 1 (do không có đỉnh nào được chỉ định trước). Khi duyệt, ta sẽ ưu tiên thăm các đỉnh theo thứ tự từ điển (tức là số nhỏ hơn được thăm trước).
1. Bắt đầu từ đỉnh 1: Đưa 1 vào hàng đợi và đánh dấu đã thăm.
2. Các đỉnh kề của 1: Các đỉnh kề của 1 là 2, 3, và 6. Theo thứ tự từ điển, ta thăm 2, sau đó 3, sau đó 6. Đưa 2, 3, 6 vào hàng đợi.
3. Thăm đỉnh 2: Các đỉnh kề của 2 là 1, 3, 5, và 6. 1 đã thăm. 3 và 6 đã được đưa vào hàng đợi. Vậy ta chỉ cần đưa 5 vào hàng đợi.
4. Thăm đỉnh 3: Các đỉnh kề của 3 là 1 và 2, cả hai đều đã thăm.
5. Thăm đỉnh 6: Các đỉnh kề của 6 là 1, 2, 4, 5. 1 và 2 đã thăm. 5 đã được đưa vào hàng đợi. Ta đưa 4 vào hàng đợi.
6. Thăm đỉnh 5: Các đỉnh kề của 5 là 2, 4, 6. Cả 3 đều đã thăm.
7. Thăm đỉnh 4: Các đỉnh kề của 4 là 5, 6. Cả 2 đều đã thăm
Như vậy, thứ tự các đỉnh được thăm là: 1, 2, 3, 6, 5, 4.
1. Bắt đầu từ đỉnh 1: Đưa 1 vào hàng đợi và đánh dấu đã thăm.
2. Các đỉnh kề của 1: Các đỉnh kề của 1 là 2, 3, và 6. Theo thứ tự từ điển, ta thăm 2, sau đó 3, sau đó 6. Đưa 2, 3, 6 vào hàng đợi.
3. Thăm đỉnh 2: Các đỉnh kề của 2 là 1, 3, 5, và 6. 1 đã thăm. 3 và 6 đã được đưa vào hàng đợi. Vậy ta chỉ cần đưa 5 vào hàng đợi.
4. Thăm đỉnh 3: Các đỉnh kề của 3 là 1 và 2, cả hai đều đã thăm.
5. Thăm đỉnh 6: Các đỉnh kề của 6 là 1, 2, 4, 5. 1 và 2 đã thăm. 5 đã được đưa vào hàng đợi. Ta đưa 4 vào hàng đợi.
6. Thăm đỉnh 5: Các đỉnh kề của 5 là 2, 4, 6. Cả 3 đều đã thăm.
7. Thăm đỉnh 4: Các đỉnh kề của 4 là 5, 6. Cả 2 đều đã thăm
Như vậy, thứ tự các đỉnh được thăm là: 1, 2, 3, 6, 5, 4.
Lời giải:
Đáp án đúng: D
Tập lũy thừa của một tập A, ký hiệu P(A), là tập hợp tất cả các tập con của A, kể cả tập rỗng (∅) và chính tập A. Trong trường hợp này, A = {ôtô, Lan}.
Vậy, các tập con của A bao gồm:
- Tập rỗng: ∅
- Tập chứa một phần tử: {ôtô}, {Lan}
- Tập chứa hai phần tử: {ôtô, Lan}
Do đó, tập lũy thừa của A là P(A) = {∅, {ôtô}, {Lan}, {ôtô, Lan}}.
So sánh với các phương án:
- Phương án A thiếu tập rỗng và có chứa phần tử "táo" không thuộc tập A.
- Phương án B thiếu tập rỗng.
- Phương án C thiếu tập {ôtô, Lan}.
- Phương án D đầy đủ tất cả các tập con của A, bao gồm cả tập rỗng và chính tập A.
Vậy đáp án đúng là D.
Vậy, các tập con của A bao gồm:
- Tập rỗng: ∅
- Tập chứa một phần tử: {ôtô}, {Lan}
- Tập chứa hai phần tử: {ôtô, Lan}
Do đó, tập lũy thừa của A là P(A) = {∅, {ôtô}, {Lan}, {ôtô, Lan}}.
So sánh với các phương án:
- Phương án A thiếu tập rỗng và có chứa phần tử "táo" không thuộc tập A.
- Phương án B thiếu tập rỗng.
- Phương án C thiếu tập {ôtô, Lan}.
- Phương án D đầy đủ tất cả các tập con của A, bao gồm cả tập rỗng và chính tập A.
Vậy đáp án đúng là D.
Lời giải:
Đáp án đúng: D
Vì A là tập con của B (A⊆B), tức là tất cả các phần tử của A đều nằm trong B. Do đó, khi hợp hai tập A và B (A∪B), ta chỉ nhận được tập B, vì tất cả các phần tử của A đã có trong B. Vậy |A∪B| = |B| = 200.
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP
Lời giải:
Bạn cần đăng ký gói VIP để làm bài, xem đáp án và lời giải chi tiết không giới hạn. Nâng cấp VIP

Bộ Đồ Án Tốt Nghiệp Ngành Trí Tuệ Nhân Tạo Và Học Máy
89 tài liệu310 lượt tải

Bộ 120+ Đồ Án Tốt Nghiệp Ngành Hệ Thống Thông Tin
125 tài liệu441 lượt tải

Bộ Đồ Án Tốt Nghiệp Ngành Mạng Máy Tính Và Truyền Thông
104 tài liệu687 lượt tải

Bộ Luận Văn Tốt Nghiệp Ngành Kiểm Toán
103 tài liệu589 lượt tải

Bộ 370+ Luận Văn Tốt Nghiệp Ngành Kế Toán Doanh Nghiệp
377 tài liệu1030 lượt tải

Bộ Luận Văn Tốt Nghiệp Ngành Quản Trị Thương Hiệu
99 tài liệu1062 lượt tải
ĐĂNG KÝ GÓI THI VIP
- Truy cập hơn 100K đề thi thử và chính thức các năm
- 2M câu hỏi theo các mức độ: Nhận biết – Thông hiểu – Vận dụng
- Học nhanh với 10K Flashcard Tiếng Anh theo bộ sách và chủ đề
- Đầy đủ: Mầm non – Phổ thông (K12) – Đại học – Người đi làm
- Tải toàn bộ tài liệu trên TaiLieu.VN
- Loại bỏ quảng cáo để tăng khả năng tập trung ôn luyện
- Tặng 15 ngày khi đăng ký gói 3 tháng, 30 ngày với gói 6 tháng và 60 ngày với gói 12 tháng.
77.000 đ/ tháng