“VẼ LIỀN MỘT NÉT” VÀ MẠNG LIÊN THÔNG
Một người bưu tá hàng ngày đi đưa đưa bưu kiện. Anh ta phải đi hết các đường ngang ngõ tắt trong phạm vi phục vụ của mình. Xét xem anh ta nên đi con đường nào là đường ngắn nhất?
Đương nhiên là người bưu tá phải đi từ bưu cục, qua hết các đường lớn, ngõ ngách mỗi nơi đi qua một lần, cuối cùng lại quay về bưu cục, đó là đường ngắn nhất.
Vấn đề là không phải lúc nào cũng tìm được con đường như vậy. Ví như hai con đường vẽ trong hình dưới đây. Bắt đầu xuất phát từ điểm A rồi đi theo A B C D E F G B E H IJ A.
dù có đi theo cách nào thì có những đoạn nếu không đi lặp lại thì không đến được nơi đó.
Thế thì với điều kiện nào ta có thể tìm được con đường ngắn nhất? Ta có thể giải quyết nếu dựa vào bài toán ''vẽ liền một nét'' trong toán học.
Bài toán ''vẽ liền một nét'' do nhà toán học Ơle đưa ra và đã giải quyết. Sở dĩ bài toán màng tên ''bài toán vẽ liền một nét'' vì với một hình khi vẽ; ngòi bút không dời khỏi mặt giấy mà không lặp lại nét vẽ.
Ơle đã nghiên cứu các đặc trưng kết cấu của hình vẽ liền một nét. Đường vẽ liền một nét có điểm khởi đầu và điểm kết thúc (với đường khép kín thì điểm đầu và điểm cuối phải trùng nhau). Tại mỗi điểm trung gian thì nét vẽ sẽ đi vào từng điểm và từ điểm đó đi ra. Vì vậy trừ điểm đầu và điểm cuối các điểm khác trên hình phải là số chẵn các đường nối nhau. Các điểm mà nối liền số chẵn đường gọi là điểm chẵn, còn các điểm nối số lẻ đường gọi là điểm lẻ.
Đồng thời, hình vẽ một nét phải hội đủ điều kiện là các điểm cuối phải do một số hữu hạn các đường tạo nên (gọi là mạng lưới), mà nếu với mạng lưới bất kỳ có hai điểm đỉnh có thể nới với nhau bằng một đường, các mạng như vậy gọi là mạngliên thông. Ví dụ mạng lưới hình chữ phẩm ''. . . . . . . . . . . . .''' là mạng lưới không liên thông. Hình này không thể vẽ liền một nét.
Cuối cùng Ơle đi đến kết luận: một đường có thể vẽ liền một nét phải là đường liên thông, số điểm lẻ chỉ có thể là 0 hoặc 2. Đó là định lý Ơle nổi tiếng.
Nhờ định lý này bài toán con đường cho bưu tá đã được giải quyết. Con đường ngắn nhất cho người bưu tá trong phạm vi các đường đi lối lại mà anh phải phục vụ là con đường liên thông với số điểm lẻ là 0 hoặc 2.
