Bài toán 7 cây cầu

Câu chuyện bắt đầu vào thế kỉ 18, tại thị trấn Konigsberg yên bình của nước Phổ, bên bờ sông Pregel.

Bạn đang xem: Bài toán 7 cây cầu

Năm 1254, các hiệp sĩ Teuton thành lập thành phố Konigsberg dưới sự trị vì của vị vua Bohemian Ottoker II sau cuộc chinh chiến thứ hai trước người Phổ. Thời Trung Đại, Konigsberg trở thành thành phố trọng điểm và là trung tâm giao dịch với vị trí đắc địa bên bờ sông. Các bức họa của thế kỉ 18 cho thấy Konigsberg là thành phố phồn thịnh, với hàng trăm tàu cập bến trải sông Pregel với những thương vụ mang lại lợi ích cho người dân địa phương và gia đình của họ. Nền kinh tế ổn định này giúp thành phố xây dựng bảy cây cầu, phần lớn nối với đảo Kneiphof.

*

– BÀI TOÁN BẢY CÂY CẦU CỦA KONIGSBERGCâu chuyện bắt đầu vào thế kỉ 18, tại thị trấn Konigsberg yên bình của nước Phổ, bên bờ sông Pregel. Năm 1254, các hiệp sĩ Teuton thành lập thành phố Konigsberg dưới sự trị vì của vị vua Bohemian Ottoker II sau cuộc chinh chiến thứ hai trước người Phổ. Thời Trung Đại, Konigsberg trở thành thành phố trọng điểm và là trung tâm giao dịch với vị trí đắc địa bên bờ sông. Các bức họa của thế kỉ 18 cho thấy Konigsberg là thành phố phồn thịnh, với hàng trăm tàu cập bến trải sông Pregel với những thương vụ mang lại lợi ích cho người dân địa phương và gia đình của họ. Nền kinh tế ổn định này giúp thành phố xây dựng bảy cây cầu, phần lớn nối với đảo Kneiphof, như hình bên dưới.

*

Với dòng sông chảy bao quanh Kneiphof, và một hòn đảo khác, nó chia thành phố thành 4 vùng. Theo kể lại, người dân thường dành ngày Chủ Nhật dạo quanh thành phố xinh đẹp này. Lúc này, họ nảy ra một ý tưởng, một trò chơi để tìm ra câu trả lời cho câu hỏi:“Có đường đi nào cho phép một người đi qua cả bảy cây cầu, mà mỗi cây cầu chỉ đi qua một lần?”Kết quả là không ai có thể làm được điều này và họ cũng không chứng minh được rằng điều đó là không khả thi. May mắn thay, thị trấn của họ không xa St. Petersburg, nơi có nhà toán học thiên tài Leonard Euler.Tại sao Euler lại quan tâm đến một vấn đề hoàn toàn không liên quan gì tới toán học? Tại sao nhà toán học thiên tài này lại dành nhiều thời gian cho một vấn đề nhỏ nhặt như thế này? Ban đầu, Euler đã từ chối vì nghĩ rằng nó chẳng liên quan gì đến toán học cả, theo như bức thư phản hồi đề nghị giải quyết của Carl Leohard Gottlieb Ehler năm 1736:“… Thưa ngày, lời giải cho vấn đề này không liên quan đến toán học và tôi cũng không hiểu tại sao ngài lại mong một nhà toán học giải quyết nó, khi mà lời giải có thể dựa vào lý luận mà không phụ thuộc bất kì nguyên tắc toán học nào.”Tuy thế, Euler vẫn cảm thấy hứng thú về nó.

Xem thêm: Không Xuất Được Video Trong Proshow Producer Chất Lượng Cao Full Hd, 2K,4K

Trong một lá thư gửi cùng năm cho Giovanni Marioni, một nhà toán học và kỹ sư người Ý, Euler nói:“Vấn đề này thật nhàm chán, nhưng tôi cho rằng đáng được để tâm vì cả hình học, lẫn đại số, lẫn phương pháp đếm đều chưa đủ để giải quyết nó.”Euler tin rằng vấn đề này liên quan đến một chủ để mà Gottfried Wilhelm Leibniz từng bàn luận và mong mỏi được nghiên cứu cùng, gọi là geometria situs, hay hình học của vị trí. Đó là tiền thân của lý thuyết đồ thị, một mảng toán học được quan tâm nghiên cứu rất nhiều hiện nay.Để giải quyết bài toán, đầu tiên, Euler nhận định rằng đường đi cụ thể là không quan trọng và có thể giản lược thành 4 điểm, gọi là các đỉnh, với các đoạn thẳng nối chung tượng trưng cho các cây cầu, gọi là các cạnh. Đồ thị này cho phép ta tính toán bậc của các đỉnh, hay số cạnh nối với nó.Để ý rằng, khi đi qua một vùng, người đi phải qua một cây cầu rồi rời đi qua một câu cầu khác. Do đó, luôn tồn tại một cặp cạnh đến và đi và vì vậy mà bậc của một đỉnh luôn là số chẵn, chỉ trừ khi đó là điểm bắt đầu và điểm kết thúc.Trong bài toán bảy câu cầu, để ý rằng tất cả đỉnh đều có bậc lẻ và do đó sẽ luôn có một cây cầu phải đi qua hai lần, bất kể đi thế nào.Euler cũng tìm ra kết quả tổng quát cho các đồ thị có nhiều hơn hai đỉnh. Một đường đi qua tất cả các cạnh và mỗi cạnh chỉ đi qua một lần được gọi là đường đi Euler, và chỉ tồn tại khi đồ thị thỏa mãn:1/ Chỉ tồn tại hai đỉnh có bậc lẻ là hai đỉnh bắt đầu và kết thúc, các đỉnh còn lại có bậc chẵn2/ Tất cả các đỉnh đều có bậc chẵn, đường đi này có điểm đầu và điểm cuối trùng nhau và được gọi là chu trình EulerEuler cũng chỉ ra một cách để tạo đường đi Euler cho bài toán này là bỏ đi một cây cầu trong số bảy cây. Trên thực tế, lịch sử đã làm chuyện này và số phận của thành phố Konigsberg không được huy hoàng như bài toán đặt tên theo nó.Năm 1875, người dân Konigsberg quyết định ây một cây cầu mới nối hai bờ sông, tăng bậc của hai đỉnh này lên 4 và do đó chỉ còn hai đỉnh có bậc lẻ, vấn đề đã được giải quyết. Tuy nhiên, có lẽ việc xây dựng cây cầu không liên quan đến mong muốn giải quyết bài toán nổi tiếng này. Năm 1944, chỉ 4 ngày trong tháng tám, quân đội Anh đã đánh bom thành phố này. Đầu năm 1945, khu vực xung quanh Konigsberg bị vây quanh bởi quân đội Nga. Người Đức bắt đầu di tản nhưng quá muộn, hàng ngàn người chết khi cố gắng vượt qua dòng sông băng giá. Tháng 4/1945, Hồng Quân chiếm lĩnh Konigsberg khi nó chỉ còn là đống tro tàn.Cho tới nay, thị trấn đã trải qua nhiều thay đổi. Phần lớn cây cầu đã bị phá hủy trong cuộc đánh bom và bài toán nổi tiếng thời ấy trở nên không tồn tại. Thị trấn được đổi tên thành Kaliningrad và sống Pregal trở thành Pregolya. Tuy không còn Konigsberg sẽ luôn được ghi nhận là nơi đã hình thành nên một hướng đi hoàn toàn mới của toán học: lý thuyết đồ thị.Tham khảo:+ Leonard Euler”s Solution to the Konigsberg Bridge Problem, Teo Paolettihttp://www.maa.org/press/periodicals/convergence/leonard-eulers-solution-to-the-konigsberg-bridge-problem+ How the Königsberg bridge problem changed mathematics, Dan Van der Vierenhttps://www.youtube.com/watch?v=nZwSo4vfw6c

Leave A Reply