TTV: Giải mê cung tam giác bằng đường đi Euler | Định lý về đường đi Euler và chu trình Euler

Toán Thú Vị
29 người theo dõi
5 Lượt xem video·27 thg 5, 2025
Mọi người đừng quên đăng ký kênh để cập nhật những Video hấp dẫn, Cảm ơn mọi người. Toán thú vị: Kênh chia sẻ về những điều lý thú trong toán học như: câu đố vui, các phương pháp tính toán, mẹo tính toán, bài toán nhanh, IQ test, những bài toán vui, hóc búa và cả những sai lầm trong toán học.
Quay trở lại thôi, lâu lắm rồi lại làm toán thôi các bạn
Một bài toán rất hay từ bạn Trường Phát đã leo
Một mê cung có các phòng bố trí như hình vẽ, mỗi tam giáp có một cạnh chung tương ứng với một cánh cửa
Kiểu như này đây
A. Chứng minh một người không thể đi hết các phòng bằng cách đi qua mỗi căn phòng một lần
B. Tính số phòng một người có thể đi nhiều nhất nếu mỗi căn phòng chỉ đi qua một lần
Vừa đọc đài bài xong, mình nghĩ ngay tới nó liên quan đến một cái gì đó mang tên Euler
Nghĩ lại, chính xác, nó là đường đi Euler
Các bạn có thể xem lại vấn đề đường đi Euler ở video này
Mình sẽ để ở phía dưới phần mô tả
Vậy các bạn thử nghĩ xem vấn đề của chúng ta ở đây sẽ giải quyết như thế nào
Và cùng đưa ra ở phía dưới phần bình luận nhé
Trước khi đi vào giải bài toán này, hãy cùng nhắc lại một chút về đường đi Euler
Trong lý thuyết đồ thị, một đường đi trong đồ thị được gọi là đường đi Euler
Nếu nó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần
Đường đi Euler có đỉnh cuối cùng chung với đỉnh xuất phát được gọi là chu trình Euler
Khái liệm chu trình Euler xuất phát từ bài toán 7 cây cầu do Euler giải quyết vào khoảng năm 1737
Cùng xem một số định lý Euler về chu trình và đường đi Euler
Đồ thị vô hướng niên thông G bằng XE có chu trình Euler khi và chỉ khi G không có đỉnh bậc lẻ
Đồ thị vô hướng niên thông G bằng XE có đường đi Euler khi và chỉ khi G có đúng 2 đỉnh bậc lẻ
Nếu G có 2 đỉnh bậc lẻ, thì đường đi Euler có 2 đầu đường nằm ở 2 đỉnh bậc lẻ
Các bạn hãy ghi nhớ kỹ điều này, nó rất quan trọng để giải quyết vấn đề ban đầu của chúng ta
Trước khi vào giải bài toán của chúng ta, hãy xem lại bài toán 7 cây cầu Euler nổi tiếng là tiền đề cho đường đi Euler này
Bài toán phát sinh từ một địa điểm cụ thể, thành phố Kolingberg, nay là Kaliningrad, Nga, làm trên sông Breger
Bao gồm 2 hòn đảo lớn đối với nhau và với bất liệt bằng 7 cây cầu
Bài toán đặt ra là tìm một tuyến đường mà đi qua mỗi cây cầu một lần và chỉ đúng một lần để người đi về đúng vị trí ban đầu
Hãy xem bài toán này đưa về dạng thẳng sẽ nào như thế này
Mỗi châm xanh là một lút, mỗi đường đi có một lút là một bậc
Vậy, ta sẽ có bậc của tất cả các lút ở đây
Tổng là 3 lút bậc 3, 1 lút bậc 5
Với 4 lút lẻ thì theo định nghĩa Euler về đường đi Euler
Thì ta cần tới 2 đường đi để đi qua tất cả các lút, mỗi lút chỉ đi qua đúng một lần
Sau khi có được bài toán này rồi, các bạn thấy nó giống với bài toán ban đầu của chúng ta đưa ra chưa?
Mỗi tam giác có một cạnh chung tương ứng với một cánh cửa
Nên hãy coi mỗi cánh cửa đó là một cái cầu như bài toán 7 cây cầu
Thì chúng ta sẽ đưa nó được về dạng thẳng như thế này
Mỗi tam giác là một lút, mỗi cánh cửa kết nối 2 tam giác là một cây cầu
Nhìn rất đẹp
Có ai thấy nó giống với một mô hình nguyên tử hoa học không?
Đẹp ra phết
Đến đây, ta hãy xác định số bậc của các lút
1
2
3
2
3
2
Cứ như vậy, ta sẽ có 3 lút bậc 1, 6 lút bậc 2 và 7 lút bậc 3
Tổng cộng sẽ là 10 lút bậc lẻ
Như vậy, để đi hết tất cả các phòng thì theo định lý Euler
Ta cần tối thiểu 5 đường đi để đi qua tất cả các phòng chỉ một lần
Hay nói cách khác, một người không thể đi hết các căn phòng bằng cách đi qua mỗi cánh cửa một lần
Cần phải có 5 lần thì một người mới có thể đi hết các căn phòng bằng cách đi qua mỗi căn phòng một lần
Vấn đề tiếp theo là số phòng mà một người đi nhiều nhất nếu mỗi căn phòng chỉ đi qua một lần
Đến đây, vẫn là định lý Euler về đường đi Euler
Ta có 10 lút lẻ
Như vậy, để có một đường đi hoàn chỉnh, ta cần loại bỏ đi 8 lút bậc lẻ còn lại
Ví dụ như, khi ta bỏ lút bậc lẻ này
Thì mô hình bây giờ đã loại bỏ được tổng cộng là 8 lút bậc lẻ
Như vậy, chỉ còn lại 2 lút bậc lẻ
Và ta có thể hoàn thành đường đi Euler, tức là đi qua tất cả các phòng một lần
Như vậy, tối đa một người sẽ đi được qua 13 phòng với điều kiện là đi qua mỗi phòng chỉ một lần
Thật tuyệt vời
Hy vọng video này giúp ích cho các bạn
Hãy để lại những ý kiến của mình ở phần dưới phần bình luận nhé
Đã theo dõi, hãy nhận những chia sẻ phía dưới và đăng ký kênh để cập nhật các video hấp dẫn
