Bài tự luận Một số bài toán thuộc chuyên đề Toán học 10–11–12 · Bài 55
(Sở Hậu Giang 2025) Trong một lần sáp nhập tỉnh, tỉnh A được thành lập gồm có 6 phường và 55 xã. Ta kí hiệu 6 phường này là 1, 2, 3, 4, 5, 6. Giữa các phường có các con đường mới xây dựng và có thể di chuyển bằng ô tô, được biểu diễn bằng các đoạn thẳng hoặc đoạn cong như hình vẽ. Anh Hoàng ở Phường 2, anh định dùng ô tô để đi tham quan tất cả các con đường nói trên sao cho mỗi con đường chỉ đi đúng một lần rồi trở về Phường 2. Nhưng tiếc rằng hiện tại chắc chắn không có cách nào để đi được như thế. Gọi $ ik $là con đường đi trực tiếp từ Phường $ i $ đến Phường $ k $ và không giao nhau với các con đường khác, với $ i,k\in\{1;2;3;4;5;6\},\ i\neq k $. Nếu bạn được phép xây dựng thêm duy nhất một con đường $ ik $ thì hãy cho biết giá trị $ i+k $ bằng bao nhiêu để anh Hoàng có thể thực hiện được ý định nêu trên?
Xem lời giải
Lời giải
Đáp án: 8.
+ Khi Anh Hoàng ở Phường 2, anh định dùng ô tô để đi tham quan tất cả các con đường nói trên sao cho mỗi con đường chỉ đi đúng một lần rồi trở về Phường 2, là Anh Hoàng đã thực hiện một chu trình Ơle.
Điều kiện cần và đủ để một đồ thị có chu trình Ơle là “tất cả các đỉnh đều có bậc chẵn”.
+Trên đồ thị ta chỉ có đỉnh 5 và đỉnh 3 là bậc lẻ, để hai đỉnh này thành bậc chẵn. ta cần xây con đường nối Phường 5 và Phường 3. Vậy để có thể ở Phường 2 đi tham quan được tất cả các con đường nói trên sao cho mỗi con đường chỉ đi đúng một lần rồi trở về Phường 2 thì ta cần xây con đường nối Phường 5 và Phường 3. Do đó $ i+k=5+3=8 $