TAILIEUCHUNG - Bài toán bảy cây cầu Euler

Bản đồ Königsberg thời Euler, mô tả vị trí thực của bay cây cầu và sông Pregel. Bài toán bảy cây cầu Euler, còn gọi là Bảy cầu ở Königsberg nảy sinh từ nơi chốn cụ thể. Thành phố Königsberg, Đức (nay là Kaliningrad, Nga) nằm trên sông Pregel, bao gồm hai hòn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu. | r J r 1 V Ä Tl 1 Bài toán bảy cây câu Euler Bản đồ Königsberg thời Euler mô tả vị trí thực của bay cây cầu và sông Pregel. Bài toán bảy cây câu Euler còn gọi là Bảy câu ở Königsberg nảy sinh từ nơi chốn cụ thể. Thành phố Königsberg Đức nay là Kaliningrad Nga nằm trên sông Pregel bao gồm hai hòn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu. Câu hỏi đặt ra là có thể đi theo một tuyến đường mà đi qua mỗi cây cầu đúng một lần rồi quay lại điểm xuất phát hay không. Năm 1736 Leonhard Euler đã chứng minh rằng điều đó là không thể được. Người ta kể rằng khoảng năm 1750 vào các ngày Chủ nhật những người dân giàu có và học thức của thành phố đã đi dạo quanh để tìm cách giải bài này nhưng đây có lẽ chỉ là một truyền thuyết. 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ó .

Trí Hùng 87 3 pdf

Upload

Bấm vào đây để xem trước nội dung

Tải xuống

TÀI LIỆU LIÊN QUAN

Đề thi thử vào đại học năm 2015 môn: Khoa học tự nhiên - Trường Đại học Quốc gia Hà Nội

9 199 0

Bài giảng môn Khoa học tự nhiên lớp 6 - Bài 1: Giới thiệu về khoa học tự nhiên

18 77 3

Đề tự ôn thi đại học môn toán - Đề số 6

8 207 0

Giáo án Khoa học tự nhiên 7 sách Kết nối tri thức (Bài 1 - Bài 7)

95 137 2

Bài giảng Nhập môn khoa học tự nhiên: Chương trình bồi dưỡng giáo viên môn Khoa học tự nhiên

48 217 64

Bài giảng Khoa học tự nhiên lớp 6 - Bài 1: Giới thiệu về khoa học tự nhiên

22 57 1

Bài giảng môn Khoa học tự nhiên lớp 7 bài 1 sách Kết nối tri thức: Phương pháp và kỹ năng học tập môn khoa học tự nhiên

33 33 1

Bài giảng môn Khoa học tự nhiên lớp 6 - Bài 3: Quy định an toàn trong phòng thực hành. Giới thiệu một số dụng cụ đo sử dụng kính lúp và kính hiển vi quang học

11 71 3

Đề cương ôn tập cuối học kì 1 môn Khoa học tự nhiên lớp 6

9 6 1

Tài liệu tập huấn hướng dẫn thực hiện chương trình môn Khoa học tự nhiên

77 1 1

TÀI LIỆU XEM NHIỀU

Một Case Về Hematology (1)

8 461864 55

Giới thiệu :Lập trình mã nguồn mở

14 22635 59

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 10884 529

Câu hỏi và đáp án bài tập tình huống Quản trị học

14 10064 446

Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”

3 9519 104

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8280 1125

Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức

16 8230 423

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 7864 2220

Đề tài: Dự án kinh doanh thời trang quần áo nữ

17 6686 253

Vật lý hạt cơ bản (1)

29 5770 85

TỪ KHÓA LIÊN QUAN

TÀI LIỆU MỚI ĐĂNG

Đánh giá hao mòn và độ tin cậy của chi tiết và kết cấu trên đầu máy diezel part 3

12 304 0 26-04-2024

Báo cáo khoa học: Loss of kinase activity in Mycobacterium tuberculosis multidomain protein Rv1364c

14 235 0 26-04-2024

extremetech Hacking BlackBerry phần 9

31 248 0 26-04-2024

BeginningMac OS X Tiger Dashboard Widget Development 2006 phần 2

34 211 0 26-04-2024

beginning Ubuntu Linux phần 1

34 212 1 26-04-2024

Bơm máy nén quạt trong công nghệ part 1

20 249 2 26-04-2024

Trading Strategies Profit Making Techniques For Stock_8

23 175 0 26-04-2024

Anh văn bằng C-124

8 175 0 26-04-2024

Management and Services Part 1

10 156 0 26-04-2024

Posted prices versus bargaining in markets_7

23 155 0 26-04-2024

TÀI LIỆU HOT

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 7864 2220

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 5722 1368

Ebook Chào con ba mẹ đã sẵn sàng

112 3767 1231

Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1

62 5319 1136

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8280 1125

Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu

561 3498 643

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 10884 529

Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân

122 3684 525

Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm

274 4046 515

Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe

35 4127 480