Lời giải của Euler

Để chứng minh kết quả, Euler đã phát biểu bài toán bằng các thuật ngữ của lý thuyết đồ thị. Ông loại bỏ tất cả các chi tiết ngoại trừ các vùng đất và các cây cầu, sau đó thay thế mỗi vùng đất bằng một điểm, gọi là đỉnh hoặc nút, và thay mỗi cây cầu bằng một đoạn nối, gọi là cạnh hoặc liên kết. Cấu trúc toán học thu được được gọi là một đồ thị.→→Hình thù của đồ thị có thể bị bóp méo theo đủ kiểu nhưng không làm đồ thị bị thay đổi, miễn...
Nội dung trích xuất từ tài liệu:
Lời giải của Euler Lời giải của EulerĐể chứng minh kết quả, Euler đã phát biểu bài toán bằngcác thuật ngữ của lý thuyết đồ thị. Ông loại bỏ tất cả cácchi tiết ngoại trừ các vùng đất và các cây cầu, sau đó thaythế mỗi vùng đất bằng một điểm, gọi là đỉnh hoặc nút, vàthay mỗi cây cầu bằng một đoạn nối, gọi là cạnh hoặc liênkết. Cấu trúc toán học thu được được gọi là một đồ thị. → →Hình thù của đồ thị có thể bị bóp méo theo đủ kiểu nhưngkhông làm đồ thị bị thay đổi, miễn là các liên kết giữa cácnút giữ nguyên. Việc một liên kết thẳng hay cong, một nútở bên phải hay bên trái một nút khác là không quan trọng.Euler nhận ra rằng bài toán có thể được giải bằng cách sửdụng bậc của các nút. Bậc của một nút là số cạnh nối vớinó; trong đồ thị các cây cầu Königsberg, ba nút có bậcbằng 3 và một nút có bậc 5. Euler đã chứng minh rằngmột chu trình có dạng như mong muốn chỉ tồn tại khi vàchỉ khi không có nút bậc lẻ. Một đường đi như vậy đượcgọi là một chu trình Euler. Do đồ thị các cây cầuKönigsberg có bốn nút bậc lẻ, nên nó không thể có chutrình Euler.Có thể sửa đổi bài toán để yêu cầu một đường đi qua tấtcả các cây cầu nhưng không cần có điểm đầu và điểmcuối trùng nhau. Đường đi như vậy được gọi là mộtđường đi Euler. Một đường đi như vậy tồn tại khi và chỉkhi đồ thị có đúng hai đỉnh bậc lẻ. (Như vậy điều nàycũng không thể đối với bảy cây cầu ở Königsberg.)