Câu hỏi:
11/07/2024 1,552a) Chỉ ra một chu trình Euler của đồ thị G ở Hình 5. Đồ thị này có đỉnh nào bậc lẻ không?
b) Chỉ ra rằng các đồ thị S và T sau đây không có chu trình Euler. Các đồ thị này có đỉnh bậc lẻ không?
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa... kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 70k).
Quảng cáo
Trả lời:
a) Một chu trình Euler của đồ thị G là: AB, a, b, BC, CD, DE, EA.
Ta có d(A) = 2; d(B) = 4; d(C) = 2; d(D) = 2; d(E) = 4.
Vậy đồ thị đã cho không có đỉnh nào là đỉnh bậc lẻ.
b) Đồ thị S không có chu trình Euler vì nếu một đường đi bắt đầu và kết thúc tại cùng một đỉnh thì cạnh CD bắt buộc phải đi qua ít nhất hai lần; nếu một đường đi bắt đầu tại đỉnh này và kết thúc tại đỉnh kia thì không được gọi là chu trình.
Tương tự như vậy, đồ thị T không có chu trình Euler.
Đồ thị S có: d(A) = 2; d(B) = 2; d(C) = 3; d(D) = 1. Suy ra đồ thị S có hai đỉnh bậc lẻ là C, D.
Đồ thị T có: d(A) = 3; d(B) = 2; d(C) = 3; d(D) = 2. Suy ra đồ thị T có hai đỉnh bậc lẻ là A, C.
Vậy cả hai đồ thị S và T đều có đỉnh bậc lẻ.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Mỗi đồ thị sau đây có chu trình Euler không? Nếu có, hãy chỉ ra một chu trình như vậy.
Câu 2:
Thành phố Königsberg thuộc Phổ (nay là Kaliningrad thuộc Nga) có bảy cây cầu nối bốn vùng đất được chia bởi các nhánh sông Pregel như hình dưới.
Vào mỗi sáng Chủ nhật, người dân thành phố thường đi dạo qua các cây cầu. Họ tự hỏi không biết có thể bắt đầu từ một điểm nào đó trong thành phố, đi qua khắp các cây cầu, mỗi cầu chỉ đi qua một lần, rồi quay về điểm xuất phát.
Theo em, có hay không một cách đi như vậy?
Câu 3:
Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.
Câu 4:
Hãy chỉ ra một đường đi Euler trên mỗi đồ thị sau. Mỗi đồ thị có bao nhiêu đỉnh bậc lẻ?
Bài tập Hình học không gian lớp 11 cơ bản, nâng cao có lời giải (P11)
38 câu trắc nghiệm Toán 11 Kết nối tri thức Lôgarit có đáp án
10 Bài tập Tính xác suất của biến cố hợp của hai biến cố bất kì bằng cách sử dụng công thức cộng xác suất và phương pháp tổ hợp (có lời giải)
10 Bài tập Biến cố hợp. Biến cố giao (có lời giải)
10 Bài tập Nhận biết góc phẳng của góc nhị diện và tính góc phẳng nhị diện (có lời giải)
10 Bài tập Nhận biết góc phẳng của góc nhị diện và tính góc phẳng nhị diện (có lời giải)
10 Bài tập Xác định hình chiếu vuông góc của một điểm, một đường thẳng, một tam giác (có lời giải)
20 câu trắc nghiệm Toán 11 Kết nối tri thức Mẫu số liệu ghép nhóm có đáp án
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận