Vẽ bàn cờ bằng 7 nét - Liệu có thể? Đường đi EULER - Bài toán 7 cây cầu Euler - Lý thuyết đồ thị

Toán Thú Vị
29 người theo dõi
Vẽ bàn cờ bằng 7 nét - Liệu có thể? Đường đi EULER - Bài toán 7 cây cầu Euler - Lý thuyết đồ thị #toanthuvi#dinhlyEuler#vebancobang7net 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.
Vẽ bàn cờ bằng 7 nét
Điều này có thể không các bạn?
Và tại sao lại như vậy?
Các bạn hãy đưa ra đáp án của mình ở dưới phần bình luận
Đây là một câu hỏi mà bạn Benben đã gửi đến cho mình
Sau một hồi tìm kiếm trên mạng
Mình đã thấy vấn đề này trên diễn đàn họcmãi.vn
Các bạn đã đưa ra một số kết quả
Nhưng chưa có sự giải thích hợp lý
Đây là một bài toán kinh miện trong lý thuyết đổi thị
Bài toán tìm chu trình và đường DIY trong đổi thị vô hướng
Bạn có thể áp dụng thuật toán này
Để tìm số nét vẽ tối thiểu một đổi thị vô hướng
Mà các nét vẽ không trùng lên nhau
Trước khi đi vào vấn đề này
Chúng ta hãy cùng xem đường DIY là gì?
Trong lý thuyết đổi thị
Một đường đi trong đổi thị được gọi là đường DIY
Nếu nó đi qua tất cả các cạnh của đổi thị
Mỗi cạnh đúng một lần
Đường DIY có đỉnh cuối cùng trùng với đỉnh xuất phát gọi là chu trình DIY
Khái niệm chu trình DIY xuất phát
Từ bài toán 7 cây cầu do DIY 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 DIY
Đổi thị vô hướng liên thông G bằng XE
Có chu trình Euler khi và chỉ khi G không có đỉnh bậc lẻ
Đổi thị vô hướng liên thông G bằng XE
Có đường DIY khi và chỉ khi G có đúng 2 đỉnh bậc lẻ
Nếu G có 2 đỉnh bậc lẻ
Thì đường DIY có 2 đầu đường đi 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
Hãy xem bài toán 7 cây cầu Euler nổi tiếng
Bài toán phát sinh từ một địa điểm cụ thể
Thành phố Pittsburgh, nay là Kaliningrad, Nga
Nằm trên sông Prager
Bao gồm 2 hòn đảo lớn nối với nhau và với đất nghiền bởi 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
Dựa vào các kiến thức vừa đề cập ở trên
Các bạn nghĩ rằng nhiệu có tuyến đường nào đáp ứng điều kiện để bài không?
Chúng ta sẽ mô hình lại bài toán về dạng khoảng như này
Mỗi chấm xanh là một nút
Mỗi đường đi qua nút là một bậc
Vậy ta sẽ có bậc của tất cả các nút ở đây
Tổng là 3 nút bậc 3, 1 nút bậc 5
Như vậy, theo định lý Euler thì không thể vẽ một đường đi qua tất cả các điểm
Để quay về vị trí ban đầu sao cho các đường không chùng nhau
Kể cả khi ta nhìn thực tế thì cũng không thể tìm được đường đi phù hợp đó
Quay trở lại vấn đề ban đầu của chúng ta
Với một bàn cờ tương đối rắc rối như này, thì làm sao ta có thể giải quyết nó?
Chúng ta hãy làm từng bước cơ bản
Cần xác định các nút và bậc của chúng
Hãy xem lần lượt ở đây
Chúng ta có 12 nút bậc 3, 4 nút bậc 5, 4 nút bậc 4, và 4 nút bậc 8
Chúng ta có tổng cộng 16 nút có bậc lẻ, 8 nút bậc chẵn
Đến đây, ta chỉ quan tâm đến số nút có bậc lẻ
Dựa vào đồ thị có đường DIL khi và chỉ khi nó có đúng 2 đỉnh bậc lẻ
Thì với 16 nút có bậc lẻ, ta sẽ có 8 đường DIL
Hay cần tối thiểu 8 đường để vẽ bàn cờ
Con số 7 là chưa đủ
Đó là theo lý thuyết, đôi khi ta muốn kiểm chứng xem nó đúng không?
Chúng ta hãy dựa vào định lý IL để vẽ bàn cờ bằng 8 nét
Hãy nhớ đường DIL có khi, và chỉ khi đồ thị vô hướng liên thông có đúng 2 đỉnh bậc lẻ
Tôi sẽ vẽ nét 1 như này
Đến nét thứ 2
Nét thứ 3 đơn giản hơn
Vẽ tiếp 5 nét với 5 đường thẳng này
Vậy tổng cộng 8 nét ta có thể vẽ được hình bàn cờ
Nếu ai có đáp án khác, hãy chia sẻ ở dưới phần bình luận
Cảm ơn các bạn đã theo dõi
Hãy để lại những chia sẻ phía dưới và đăng ký kênh để cập nhật các video hấp dẫn
