Không ai đi được một vòng qua bảy cây cầu của thành phố Königsberg mà mỗi cầu chỉ qua đúng một lần, và lý do nằm ở một phép đếm rất đơn giản: cả bốn vùng đất đều có số cầu lẻ. Nhà toán học Euler chứng minh điều này vào thế kỷ mười tám, và cách nghĩ của ông về sau thành cả một ngành gọi là lý thuyết đồ thị.
Chào bạn, đây là Nhà Toán Học. Hồi nhỏ chắc bạn từng chơi trò vẽ cái phong bì bằng một nét không nhấc bút. Tập này mình kể vì sao có hình vẽ được, có hình vẽ mãi không ra, và vì sao câu trả lời giống hệt chuyện bảy cây cầu ở một thành phố châu Âu gần ba trăm năm trước.
Bài toán ra đời ở thành phố nào?
Königsberg là một thành phố ở Đông Phổ thời đó, nay là thành phố Kaliningrad của Nga. Dòng sông chảy qua thành phố chia đất liền thành hai bờ, giữa sông có hai hòn đảo. Bảy cây cầu nối các vùng đất đó với nhau.
Người dân có một câu đố truyền miệng: liệu có thể đi dạo một vòng, qua mỗi cây cầu đúng một lần, không bỏ sót cầu nào và không qua cầu nào hai lần. Nhiều người thử, không ai làm được, nhưng cũng không ai chứng minh được là không thể.
Euler nghe tới câu đố và giải nó vào giữa những năm một nghìn bảy trăm ba mươi. Điều làm ông khác người là ông không thử thêm đường nào. Ông hỏi: những gì trong bản đồ này thật sự quan trọng.
Câu hỏi đó là chìa khoá của cả câu chuyện.
Euler bỏ đi gần hết bản đồ
Euler nhận ra hình dạng đảo, chiều dài cầu, khoảng cách giữa các cầu đều không quan trọng. Chỉ có hai thứ quan trọng: có những vùng đất nào, và cây cầu nào nối vùng nào với vùng nào.
Vậy thì vẽ mỗi vùng đất thành một chấm, mỗi cây cầu thành một đường nối hai chấm. Bản đồ cả thành phố biến thành bốn chấm và bảy đường. Ngày nay người ta gọi kiểu hình vẽ này là đồ thị, chấm là đỉnh, đường nối là cạnh.
Bước bỏ đi những thứ không quan trọng này nghe đơn giản, nhưng đó là một bước nhảy về tư duy. Trước Euler, hình học là chuyện độ dài, góc, diện tích. Euler cho thấy có những bài toán mà chỉ việc cái gì nối với cái gì mới quyết định tất cả.
Đây cũng là bài học cho người học toán: bài khó thường dễ lên khi mình dám vứt bớt chi tiết.
Vì sao đỉnh có số cạnh lẻ lại quyết định?
Hãy nghĩ về một vùng đất mà bạn đi ngang qua giữa hành trình. Mỗi lần đến vùng đó, bạn đi vào bằng một cầu và đi ra bằng một cầu khác. Vậy mỗi lần ghé qua dùng hết hai cây cầu. Một vùng chỉ đi ngang qua thì số cầu nối với nó phải là số chẵn.
Chỉ có hai vùng được phép có số cầu lẻ: nơi bắt đầu và nơi kết thúc, vì ở đó bạn chỉ đi ra mà không vào, hoặc chỉ đi vào mà không ra. Nếu bắt đầu và kết thúc cùng một chỗ thì không vùng nào được lẻ cả.
Ở Königsberg, đếm ra một vùng có năm cầu, ba vùng còn lại mỗi vùng có ba cầu. Cả bốn vùng đều lẻ. Nhiều hơn hai vùng lẻ, nên không có cách đi nào thoả mãn câu đố, bất kể bạn xuất phát từ đâu.
Kết luận gói trong một câu: một hình vẽ được bằng một nét khi nó liền một khối và có không hoặc đúng hai đỉnh mang số cạnh lẻ. Có hai đỉnh lẻ thì phải bắt đầu ở một đỉnh lẻ và kết thúc ở đỉnh lẻ kia.
Áp dụng ngay vào trò vẽ cái phong bì
Cái phong bì quen thuộc gồm một hình vuông, hai đường chéo và một mái nhọn ở trên. Đếm số đường đi ra ở mỗi góc, bạn sẽ thấy hai góc dưới mỗi góc có ba đường, các điểm còn lại đều chẵn.
Có đúng hai đỉnh lẻ, nên vẽ được bằng một nét. Nhưng phải bắt đầu ở một trong hai góc dưới. Đây chính là lý do nhiều bạn nhỏ thử mãi không ra: bắt đầu từ đỉnh mái nhà thì chắc chắn kẹt.
Bây giờ bỏ cái mái đi, chỉ còn hình vuông với hai đường chéo. Lúc này cả bốn góc đều có ba đường, bốn đỉnh lẻ, không thể vẽ bằng một nét. Thêm một nét nhỏ đã đổi hẳn kết quả.
Bạn có thể đố con hoặc em mình bằng mẹo này. Đưa một hình, nhìn qua đếm đỉnh lẻ, nói ngay vẽ được hay không, và nếu được thì chỉ luôn điểm xuất phát. Trông như ảo thuật, nhưng chỉ là phép đếm của Euler.
Từ bảy cây cầu tới bản đồ đường phố hôm nay
Ý tưởng của Euler giờ có mặt ở khắp nơi. Ứng dụng chỉ đường trên điện thoại coi các ngã tư là đỉnh và đoạn đường là cạnh. Mạng điện, mạng nước, mạng internet đều được mô hình hoá bằng đồ thị.
Có một bài toán họ hàng gần gọi là bài toán người đưa thư: làm sao đi qua mọi con đường trong một khu, đường nào cũng ít nhất một lần, mà tổng quãng đường ngắn nhất. Xe quét rác, xe tưới cây, người giao báo buổi sáng đều gặp đúng câu hỏi này.
Lời giải của nó bắt đầu bằng chính câu hỏi của Euler: có bao nhiêu ngã tư có số đường lẻ. Những chỗ lẻ là chỗ phải đi lặp lại một đoạn, và nghệ thuật là chọn đoạn lặp ngắn nhất.
Còn thành phố Königsberg thì sao. Nhiều cây cầu cũ đã bị phá trong chiến tranh thế giới thứ hai, bố cục cầu bây giờ đã khác. Bạn thử đoán xem: nếu được xây thêm đúng một cây cầu năm xưa, nên xây nối hai vùng nào để câu đố có lời giải.
Câu hỏi thường gặp
Lý thuyết đồ thị là gì?
Lý thuyết đồ thị là ngành toán nghiên cứu các điểm và các đường nối giữa chúng. Nó không quan tâm hình dáng hay độ dài mà quan tâm cái gì nối với cái gì, nên dùng được cho mạng lưới giao thông, mạng xã hội, mạch điện và rất nhiều bài toán sắp xếp.
Đường đi Euler và chu trình Euler khác nhau thế nào?
Đường đi Euler đi qua mỗi cạnh đúng một lần, điểm đầu và điểm cuối có thể khác nhau, cần không hoặc hai đỉnh lẻ. Chu trình Euler còn phải quay về đúng điểm xuất phát, khi đó mọi đỉnh đều phải có số cạnh chẵn.
Có hình nào có đúng một đỉnh lẻ không?
Không thể có. Mỗi cạnh góp vào số cạnh của hai đỉnh, nên tổng số cạnh tính theo từng đỉnh luôn là số chẵn. Vì thế số đỉnh lẻ trong mọi hình vẽ luôn là số chẵn: không, hai, bốn và cứ thế.
Euler là ai?
Leonhard Euler là nhà toán học người Thuỵ Sĩ sống ở thế kỷ mười tám, một trong những người viết nhiều nhất trong lịch sử toán học. Ông để lại dấu ấn ở hầu hết các ngành toán thời đó, và nhiều ký hiệu quen thuộc ngày nay do ông phổ biến.
Bài bảy cây cầu học ở đâu trong chương trình phổ thông?
Bài này hay xuất hiện ở các chuyên đề toán rời rạc dành cho học sinh khá giỏi và trong các hoạt động trải nghiệm toán. Nó là cửa vào nhẹ nhàng cho lý thuyết đồ thị, vốn học sâu hơn ở bậc đại học.
