BEBRAS 2025 Khối 5-6 Vòng 2 Ext Câu hỏi 7

Alex muốn lắp đặt các camera an ninh cho một thành phố có 10 ngôi nhà, được kết nối với nhau theo các con đường như trong hình dưới đây. Để tiết kiệm, anh ấy muốn sử dụng số lượng camera ít nhất có thể. Biết rằng nếu một camera được lắp đặt ở một ngôi nhà thì ngôi nhà đó và tất cả những ngôi nhà khác được nối với nó bằng một đoạn thẳng trong hình đều được coi là an toàn. Ví dụ, nếu ta lắp đặt camera ở nhà số 1 thì tất cả các ngôi nhà 1,2,3,4 đều an toàn.



Hỏi Alex cần lắp đặt ít nhất bao nhiêu camera để đảm bảo an toàn cho tất cả các ngôi nhà trong thành phố?