Lý thuyết đồ thị - Xác định số lộ trình từ A qua các đường chỉ 1 lần rồi quay lại A |Chu trình Euler

Một bài toán thú vị liên quan đến lý thuyết đồ thị mà một bạn đã gửi cho AD. Một thành phố có sáu khu vực quan trọng được nối với nhau bằng 12 con đường như hình bên. Một tài xế taxi bắt đầu từ khu vực A và muốn đi qua tất cả các khu vực khác, nhưng không được đi qua con đường nào quá một lần trước khi quay trở lại khu vực A. Hỏi có bao nhiêu lộ trình thỏa mãn? Nó giống như một số câu đố làm vẽ các đường đi qua tất cả các đỉnh nhưng không được chủng nhau. Hãy thử xem. Không được rồi. Hãy thử cách khác. Vẫn không được. Thử đổi đỉnh xem sao. À, bây giờ thì được rồi. Ê nhưng nó không quay lại điểm ban đầu. Nếu cứ làm như này thì không biết khi nào ta có thể tìm được lộ trình phù hợp. Nên hãy cùng tìm hiểu lý do. Chúng ta có lẽ đã rất quen thuộc với bài toán 7 cây cầu. Không có tuyến đường nào mà đi qua mỗi cây cầu một lần và chỉ một lần để người đi về đúng vị trí ban đầu. Để có thể dễ hiểu, hãy đưa bài toán về dạng phẳng. Mỗi chấm xanh là một lút. Mỗi đường đi qua lút là một bậc. Từ đó ta có thể tính được bậc của tất cả các lút ở đây. Là 3, 3, 3, 5. 4 lút bậc lẻ. Mà trong lý thuyết đồ thị, một đường đi trong đồ thị được gọi là đường đi Euler. Nếu đó đ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 điểm xuất phát được gọi là chu trình Euler. Ta có các định lý 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ó bậ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ẻ. Bây giờ hãy áp dụng vào bài toán của chúng ta. Chúng ta xác định các bậc ở các đỉnh ở đây. Là 4, 4, 4, 5, 5, 2. Như vậy có 2 đỉnh bậc lẻ. Theo những điều chúng ta vừa leo, thì đồ thị của chúng ta không có chu trình Euler, mà chỉ có đường đi Euler. Tức là chúng ta có thể đi từ đỉnh bậc lẻ thứ nhất rồi đi qua tất cả các đường chỉ 1 lần. Và kết thúc ở đỉnh lẻ thứ 2. Như vậy sẽ không có lộ trình nào thỏa mãn xuất phát từ A đi qua tất cả các khu vực, nhưng không được đi qua con đường nào có 1 lần trước khi quay trở lại khu vực A. Đáp án ở đây là không. Rất đơn giản phải không nào? Các bạn hãy ghi nhớ kiến thức thú vị này nhé. 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.