Bài toán bảy chiếc cầu và bài toán vẽ liền một nét?

Vấn đề bảy chiếc cầu nảy sinh vào thế kỉ XVIII tại thành phố Kơnichxbec (Kửnigsberg), vào thời đó Kơnichxbec thuộc Đức, còn ngày nay là thành phố Kaliningrat (Kaliningrad) thuộc Cộng hoà Liên bang Nga.

Vào thời đó ở thành phố Kơnichxbec có một con sông có hai hòn đảo nhỏ. Các hòn đảo nối với bờ nhờ bảy chiếc cầu như ở hình vẽ 1. Trên hình A, D là hai hòn đảo, còn C, B là đôi bờ. Cư dân của thành phố Kơnichxbec thường đến dạo chơi trên đảo. Lâu dần nảy sinh câu hỏi: Liệu có thể xuất phát từ một điểm, không bỏ sót cũng không đi qua cầu hai lần mà trở về chỗ cũ? Vấn đề này về sau được gọi là bài toán bảy cây cầu.

Nếu lược bỏ điều kiện “lại trở về chốn cũ” mà chỉ còn hỏi: “Liệu một du khách có thể không bỏ sót mà lại có thể chỉ qua cầu một lần? thì sẽ biến thành vấn đề vẽ liền một nét.

Nếu vấn đề giải được, ta nói bài toán “có lời giải”; nếu ngược lại, ta nói vấn đề “không có lời giải”.

Vào thời đó, nhà toán học Thuỵ Sĩ Ơle (L. Euler) đang sống tại Kơnichxbec và bài toán bảy cây cầu đã gây cho ông nhiều hứng thú. Năm 1736, Ơle đã công bố luận văn giải quyết được bài toán bảy cây cầu và sáng tạo ra ngành “toán đồ” là một ngành của toán học. Luận văn này của Ơle là luận văn đầu tiên về toán đồ.

Theo phương pháp toán đồ, để dễ xem xét thảo luận thường người ta dùng phương pháp đơn giản hoá các hình vẽ. Ta biểu diễn các đảo A, D và đôi bờ C, B thành các điểm đỉnh như hình 2. Bảy cây cầu được biểu diễn bằng bảy nét liền, cũng được gọi là bảy đường viền. Nếu một đỉnh có nối với số lẻ các đường viền ta gọi đó là đỉnh lẻ, còn đỉnh nối với các số chẵn các đường viền, ta gọi đó là đỉnh chẵn. Nếu từ hình vẽ ta bắt đầu từ một điểm đỉnh liên tiếp qua điểm, đường, điểm...đến liên tiếp một đỉnh điểm bất kì, người ta nói hình này là liên thông. Ơle đã chứng minh “quy tắc phán định”.

Với một hình vẽ được bằng một nét liền thì hình đó là liên thông và là những hình mà trừ điểm đầu và điểm cuối thì các điểm khác phải là điểm chẵn.

Yêu cầu để một bài toán đi về vẽ liền một nét có lời giải là phải liên thông và bất kì điểm đỉnh nào cũng phải là điểm chẵn.

Bài toán bảy cây cầu là bài toán vẽ nét liền đi và về, vì bốn đỉnh A, B, C, D của hình 2 đều là đỉnh lẻ nên bài toán không có lời giải. Bất kì một khách du lịch nào cũng không thể từ một điểm xuất phát lại quay về chốn cũ mà không bỏ sót hoặc đi qua một cây cầu nào đó hai lần.

Với hình 2 không chỉ là việc yêu cầu quay về chốn cũ mà ngay việc vẽ nét liền cũng không thực hiện được mà không bỏ qua hoặc lặp lại hai lần.

Như vậy từ bài toán bảy cây cầu, chúng tôi đã giới thiệu bài toán vẽ nét liền. Bài toán vẽ nét liền nếu đặt một cách chính xác thì phải phát biểu như sau: Cho một hình phẳng, liệu có thể giữ cho bút không rời mặt giấy mà xuất phát từ một điểm, các đường chỉ được bút vẽ một lần mà hoàn thành được hình vẽ. Còn nếu yêu cầu sau khi vẽ xong hình thì bút phải quay về vị trí ban đầu thì đó là bài toán vẽ nét liền đi và về. Bạn hãy theo quy tắc Ơle để phán đoán xem hình 3 có thể là một hình: 1) Vẽ liền được một nét; 2) Nếu là hình vẽ được một nét thì có thể đi và về được không? Mời các bạn làm thử.

Có phải ngủ gối càng cao càng tốt không?

Con người dành 1/3 cuộc đời cho ngủ, mà giấc ngủ gắn liền với cái gối, cho nên cái gối có vai trò rất quan trọng đối với sức khỏe.

Bài toán “một trăm con gà” thế nào?

Vào thế kỉ thứ V ở Trung Quốc có bộ sách toán nổi tiếng là “Sách toán Trương Khâu Kiện” trong đó có bài toán trăm con gà. Đem 100 đồng mua 100 con gà,...

Vì sao Nhật Bản và quần đảo Hawai đặc biệt nhiều núi lửa?

Thái Bình Dương rộng lớn, chiếm 1/3 diện tích Trái Đất, Dưới đáy Thái Bình Dương có nhiều vùng lõm sâu trên 8.000 m.

Có phải tôm he (tôm đôi) sống thành đôi cái đực với nhau không?

Nhắc đến tôm he, không ít người cho rằng tôm he đực và tôm he cái sống với nhau, gắn bó như hình với bóng, giống như đôi uyên ương vậy, cho nên nó có tên gọi khác là tôm đôi. Thực tế đây là một sự hiểu nhầm.

Hồng triều là thế nào?

Hồng triều (thuỷ triều đỏ) do các sinh vật phù du sống trong nước biển gặp được điều kiện môi trường thích hợp mà sinh sôi nảy nở nhanh chóng, hoặc...

Tại sao mèo thích ăn cá và chuột?

Thì ra mèo hoạt động về ban đêm, trong cơ thể của mèo có một chất cần thiết để tăng thị lực nhìn đêm, đó là axit diaminethanosunfonic C2H7NO3S, tên thương mại là taurin.

Vì sao nói Mặt Trời là hằng tinh phổ thông?

Mặt Trời là thiên thể mà ta quen thuộc nhất. Nó là thiên thể trung tâm của hệ Mặt Trời, khối lượng đạt 2 tỉ tỉ tỉ tấn, nhiều hơn 33 vạn lần khối lượng...

Tại sao cần phải bảo vệ các kiến trúc cổ của thành phố?

Kiến trúc cổ của thành phố là một tài sản vô giá, một loại biểu trưng, một giai đoạn lịch sử, nó ghi lại bối cảnh văn hoá và sự uyên thâm về tinh thần...

Tại sao âm nhạc do máy CD phát lại sống động hơn caset?

Âm nhạc phát từ máy CD (compact disc player: máy hát laze, máy quay đĩa compac) sống động hơn máy caset (radio cassette rocorder). Đó là nguyên lí và...