Thay đổi ngôn ngữ

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Đăng nhập Mathigon

hoặc là

Tài khoản mới     Đặt lại mật khẩu     

Đồ thị và Mạng lưới
Giới thiệu
Những cây cầu ở Königsberg
Tiệc tùng và hẹn hò
Đồ thị phẳng
Tô màu bản đồ
Bài toán vận chuyển của người bán hàng
Vấn đề lập kế hoạch
Đồ thị trong cuộc sống hằng ngày

Chia sẻ

Đặt lại tiến độ

Thao tác này sẽ xóa tiến trình và dữ liệu trò chuyện của bạn cho tất cả các chương trong khóa học này và không thể hoàn tác!

Bảng chú giải

Chọn một trong những từ khóa bên trái

Đồ thị và Mạng lướiNhững cây cầu ở Königsberg

Thời gian đọc: ~20 min

Một trong những nhà Toán học đầu tiên nghĩ về đồ thị và mạng lưới là Leonhard Euler. Euler rất hứng thú về một bài toán lâu đời ở thị trấn Königsberg gần Biể Baltic.

Con sông Pregel phân chia thị trấn Königsberg thành 4 khu vực khác nhau, được kết nối bởi 7 cây cầu. Liệu có thể có cách nào đi một vòng thành phố và đi qua tất cả 7 cây cầu – và chỉ đi qua mỗi cây cầu đúng 1 lần không? ( Bạn có thể bắt đầu và kết thúc ở bất kỳ điểm nào, không nhất thiết phải cùng một chỗ.)

Tìm giải pháp bằng cách vẽ đường đi trên bản đồ dưới đây:

Map 1

Map 2

Map 3

Map 4

Trong trường hợp của thị trấn Königsberg dường như không có giải pháp nào khả thi cả, nhưng với một số thành phố khác thì có thể thực hiện được. Euler đã tìm ra quy tắc đơn giản sử dụng phương pháp đồ thị để tìm lời giải và có thể áp dụng cho tất cả khác thành phố mà không phải ngồi vẽ nháp thử đi thử lại nhiều lần.

Đầu tiên chúng ta cần chuyển đổi bản đồ thành phố thành đỉnh và cạnh của đồ thị. Mỗi vùng đất được đại diện bởi và mỗi cây cầu kết nối hai vùng đất khác nhau được đại diện bởi tương ứng.

Bây giờ bài toán từ “ đi một vòng thành phố qua tất cả các cây cầu đúng một lần" thành bài toán “vẽ lại đồ thị với một đường duy nhất đi qua các cạnh đúng một lần"

Trên giấy nháp, bạn hãy thử vẽ các đồ thị khác nhau dưới đây và xem đồ thị nào có thể vẽ được bằng một đường liên tục duy nhất.

Cũng như bản đồ ở trên, ta thấy rằng một số đồ thị có giải pháp khả thi trong khi một số khác thì không. Để hiểu vì sao chúng ta có thể đánh số cấp độ của mỗi đỉnh trong đồ thị. :

Giá trị
Nhỏ và lớn
Số nguyên tố và số đa hợp
Chẵn lẽ

Những đồ thị này khả thi:

2 4 3 3 4 4 2 2 4 4 2 2 2 4 4 2 2 2 4 4 2 4 4 8 2 2 4 4 4 4 2

Những đồ thị này không khả thi:

2 3 2 3 4 3 2 3 2 2 2 2 2 3 5 3 3 5 3 3 6 3 3 3 3 3

Khi so sánh các số giữa nhóm đồ thị khả thi và không khả thi, ta thấy dường như có phương án khả thi nếu đồ thị . Điều này có thể giải thích được bằng cách nhìn vào mỗi cạnh trong đồ thị:

Ở đây bạn có một đỉnh của đồ thị được đơn giản hóa và phóng to.
Nếu bạn vẽ đồ thị, sẽ có cạnh đi vào đỉnh này và có một cạnh khác đi ra khỏi đỉnh. Điều này tạo nên hai cạnh gặp nhau ở đỉnh.
Có thể đỉnh này không nằm ở góc mà là điểm giao nhau. Lúc này sẽ có hai cạnh khác đi vào và đi ra khỏi đỉnh. Vậy ta có 4 cạnh.
Và trong một số đồ thị, sẽ có cặp cạnh thứ 3 đi vào và đi ra khỏi đỉnh. Lúc này ta có 6 cạnh.
Hãy để ý rằng dù như thế nào, sẽ luôn có một số chẵn các cạnh gặp nhau ở đỉnh.
Chỉ có hai trường hợp ngoại lệ là đỉnh nơi cạnh bắt đầu và đỉnh nơi cạnh kết thúc nếu khác nhau thì hai đỉnh này có thể có cấp độ lẻ. Nếu đỉnh bắt đầu và đỉnh kết thúc là một cấp độ của các đỉnh là số chẵn.

Nếu bạn quay lại với bản đồ của thị trấn Königsberg, bạn sẽ thấy rằng có hơn hai khu đất với số lẻ những cây cầu. Do đó việc đi qua các cây cầu duy nhất một lần là bất khả thi, và đây chính là quy luật mà Leonard Euler đã phát hiện ra.

Phát hiện này của Euler có vẻ như không hữu ích gì nhiều trong cuộc sống, nhưng đồ thị là nền tảng để giải quyết rất nhiều vấn đề về địa lý, ví dụ như tìm kiếm đường đi giữa hai địa điểm. Chúng ta sẽ khám phá thêm về những ứng dụng này sau.

Archie