Đường đi và chu trình Euler – bài toán bảy cây cầu Königsberg

Chuyên đề Làm quen với lí thuyết đồ thị (Toán 11) bắt đầu từ bài toán bảy cây cầu Königsberg mà Euler giải năm 1736: có thể đi qua mỗi cây cầu đúng một lần hay không? Mô phỏng biểu diễn vùng đất bằng đỉnh, cây cầu bằng cạnh, cho phép nhiều cạnh nối cùng hai đỉnh. Bậc của từng đỉnh hiện ngay trên hình (đỏ là lẻ, xanh là chẵn) cùng tổng các bậc bằng hai lần số cạnh; từ số đỉnh bậc lẻ, mô phỏng kết luận đồ thị liên thông có chu trình Euler (không đỉnh lẻ), có đường đi Euler (đúng hai đỉnh lẻ) hay không có. Học sinh chọn đồ thị có sẵn (Königsberg, phong bì vẽ không nhấc bút, hai tam giác chung đỉnh, K5) hoặc trang trống, rồi thêm, nối, kéo, xoá đỉnh và cạnh. Ở chế độ Tự đi đường, học sinh chạm từng cạnh để thử đi qua mỗi cạnh đúng một lần và thấy mình bị kẹt khi xuất phát sai chỗ. Nút Chạy tự động và Từng bước cho thuật toán Fleury (luôn tránh cạnh cầu) hoặc Hierholzer (đi đến khi kẹt rồi ghép thêm vòng) tìm đường, đánh số thứ tự các cạnh. Câu hỏi gợi ý: – Vì sao không thể đi qua bảy cây cầu Königsberg, mỗi cầu đúng một lần? – Cần thêm hoặc bớt ít nhất mấy cây cầu để có đường đi Euler, và nên đặt ở đâu? – Với đúng hai đỉnh bậc lẻ, vì sao đường đi phải bắt đầu ở một đỉnh lẻ và kết thúc ở đỉnh lẻ kia?