Lời giải của Euler

Chia sẻ: Hanh My | Ngày: | Loại File: PDF | Số trang:2

Thêm vào BST

Báo xấu

85
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Để 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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ằ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 là các liên kết giữa các nú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ới nó; trong đồ thị các cây cầu Königsberg, ba nút có bậc bằng 3 và một nút có bậc 5. Euler đã chứng minh rằng mộ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 được
gọi là một chu trình Euler. Do đồ thị các cây cầu Königsberg có bốn nút bậc lẻ, nên nó không thể có chu trình Euler. Có thể sửa đổi bài toán để yêu cầu một đường đi qua tất cả các cây cầu nhưng không cần có điểm đầu và điểm cuố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ày cũng không thể đối với bảy cây cầu ở Königsberg.)