Số học trên bản đồ địa lý

23

Một trong những chương của cuốn sách xuất sắc về lý thuyết đồ thị *) bắt đầu bằng phần mô tả … vấn đề:

“Giả thuyết bốn màu có thể được gọi một cách chính đáng là “căn bệnh bốn màu”, vì nó có nhiều điểm giống với căn bệnh này. Nó rất dễ lây lan. Đôi khi nó tiến triển tương đối dễ dàng, nhưng trong một số trường hợp, nó trở nên kéo dài hoặc thậm chí đe dọa. Không có vắc xin nào chống lại nó…”

Tuyên bố này của nhà toán học người Mỹ F. Harari, rất giống với bản ghi nhớ của một nhà dịch tễ học, rất đáng được bổ sung vào nhà toán học và giáo viên nổi tiếng O. Ore:

“Niebaulier nổi tiếng trong số này bài toán **) - bài toán bốn màu, lần đầu tiên được De Morgan đặt ra cho các nhà toán học vào khoảng năm 1850. Không có khoảng trống nào khác đã tạo ra nhiều công trình khéo léo và nhiều như vậy trong lý thuyết đồ thị. Nhờ công thức đơn giản và tính khó nắm bắt nổi bật của nó, nó vẫn mang lại sự kích thích mạnh mẽ cho việc nghiên cứu các tính chất khác nhau của đồ thị” ***).

*) F. Harari, Lý thuyết đồ thị, dịch từ tiếng Anh. Nhà xuất bản “Mir”, M., 1973.
**) Điều này đề cập đến lý thuyết đồ thị bài toán. - Xấp xỉ. biên tập.
***) O. Ore, Lý thuyết đồ thị, dịch từ tiếng Anh, Nxb Nayka, M., 1968.

Rõ ràng, chính “sự khó nắm bắt khó chịu” của giả thuyết vấn đề này là tác nhân chính gây ra căn bệnh được F. Harari mô tả; Về “công thức đơn giản”, có lẽ hầu hết độc giả đều biết: bất kỳ bản đồ nào trên quả cầu đều có thể được tô màu không quá bốn màu, hoa anh túc, sao cho hai phiên bất kỳ của đất nước đều được sơn bằng các màu khác nhau.

Tất nhiên, điều này đề cập đến một bản đồ lý tưởng hóa: trên bản đồ địa lý, một màu (xanh lam) luôn tương ứng với bề mặt nước. Chúng tôi sẽ cho rằng chúng không có trên bản đồ của chúng tôi, cũng như không có quốc gia nào bao gồm hai hoặc nhiều phần không liên quan đến nhau (ví dụ như trường hợp của Danna và tỉnh Greenland ở nước ngoài). Những ví dụ này cho thấy khái niệm bản đồ cần được làm rõ.

Mục tiêu của chúng tôi là nói về một trong những cách tiếp cận sớm nhất và có lẽ là khéo léo nhất đối với lời giải vấn đề này - nó thường có thể được gọi là tranh luận; công việc theo hướng này vẫn tiếp tục và khái niệm này vẫn tiếp tục, và câu chuyện của chúng ta sẽ hầu như không giống với sự trình bày cá nhân về những khám phá cá nhân.

Các điều kiện của nhiệm vụ, lời giải được đưa ra ở cuối vấn đề, thực chất là một phần của văn bản; một số trong số chúng không phức tạp hơn những bức ảnh trong album “Color It Yourself”.

24

Bản đồ trên quả cầu
Chúng ta sẽ gọi bản đồ trên một hình cầu là bất kỳ sự phân chia nào của hình cầu bằng các đoạn đường cong trơn thành một số hữu hạn các khu vực—các quốc gia trên bản đồ. Về các đoạn đường cong này, những điều sau đây được giả định một cách tự nhiên:

1. mỗi đường đều không có giao điểm riêng;
2. bất kỳ hai trong số chúng hoặc không giao nhau chút nào hoặc cắt nhau ở điểm cuối của chúng;
3. điểm cuối của bất kỳ đoạn nào trong số chúng đều nằm trong số điểm cuối của một hoặc nhiều đoạn khác, tức là chúng không “treo”.
   Rõ ràng là mỗi đoạn này cùng nhau tạo nên ranh giới của bản đồ, là một phần biên giới của hai quốc gia (hoặc toàn bộ biên giới này); Chúng tôi cũng sẽ gọi các nước láng giềng. Nhân tiện, chúng ta hãy lưu ý rằng việc chứng minh chặt chẽ cho phát biểu bắt đầu ở trên bằng từ “rõ ràng là…” và được gọi là định lý Jordan là cực kỳ cồng kềnh, bất chấp vẻ ngoài rất rõ ràng của nó.
   Thật thuận tiện khi vẽ bản đồ hình cầu dưới dạng một “lục địa” được chia thành các quốc gia, được bao quanh bởi một “đại dương” - một trong các quốc gia (trong Hình 1).

Cơm. 1. Bản đồ (các nước từ A đến N), được tô màu chính xác bằng bốn màu.

Cơm. 2. Bản đồ trong đó số phần không liên kết của đồ thị ranh giới (số lượng “đảo” trong “đại dương” A) bằng trem (Krp = 3).

ke 1 nước A; Có thể có một số “lục địa”, như trong Hình 2). Nước M và E trong Hình 1 không phải là nước láng giềng dù có chung một điểm biên giới; quốc gia D và E thậm chí còn có hai phần riêng biệt trên một đường biên giới chung.

Chúng tôi cũng yêu cầu không có quốc gia nào trên bản đồ chỉ có một nước láng giềng (“đảo” trong “đại dương”); Tất nhiên, bản đồ với các quốc gia như vậy không khó tô màu hơn, nhưng cách trình bày rất phức tạp bởi các ngoại lệ và giải thích.

Trang màu thẻ
Việc tô màu bản đồ bằng n màu được gọi là tô màu n thông thường nếu bất kỳ cặp quốc gia láng giềng nào được tô màu khác nhau. Sau khi vẽ một số bản đồ hình cầu và tô màu chúng, bạn có thể dễ dàng nhận thấy rằng mặc dù có những bản đồ mà ba hoặc thậm chí hai màu là đủ để tô màu phù hợp, nhưng những bản đồ đó là “không điển hình” - cần tổng cộng bốn màu.

Nhiệm vụ 1. Vẽ bản đồ bốn quốc gia không thể tô màu chính xác bằng hai hoặc ba màu.

Bài tập 2. a) n đường tròn được cho trên một mặt phẳng. Chứng minh rằng với mọi cách sắp xếp này

25

độc lập tìm thấy bằng chứng về thực tế này, được thiết lập vào cuối thế kỷ 19.

đồ thị bản đồ

Bất kỳ hệ thống điểm và đường nào nối một số điểm này và không giao nhau theo cặp đều được gọi là đồ thị; điểm gọi là đỉnh, đường thẳng gọi là cạnh của đồ thị.

Như có thể thấy từ định nghĩa và tính chất 1) - 3) của bản đồ trên hình cầu, nó được đặc trưng bởi đồ thị biên của nó; các đỉnh của nó là những điểm mà tại đó ít nhất ba quốc gia hội tụ, các cạnh của nó là các phần của ranh giới giữa các đỉnh (Hình 3). Chúng tôi cũng sẽ xác định biểu đồ vốn và lộ trình; các đỉnh của nó là “thủ đô” của các quốc gia (các điểm tùy ý nhưng cố định, được chọn theo nội địa của mỗi quốc gia), các cạnh là “những con đường” nối thủ đô của các quốc gia láng giềng (mỗi cặp láng giềng một thủ đô) và đi qua phần biên giới giữa chúng (Hình 4, 5).

Màu của bản đồ có thể được thay thế bằng màu của các đỉnh của đồ thị vốn và đường của bản đồ này; tính đúng đắn của việc tô màu có cùng ý nghĩa nếu các điều kiện là hai đỉnh của bất kỳ đồ thị nào

Cơm. 3. Bản đồ đồ thị ranh giới.

các vòng tròn, bản đồ mà chúng tạo thành có thể được tô màu chính xác bằng hai màu.

b) Tạo điều kiện cần và đủ để bản đồ được tô đúng hai màu.

Kết quả của nhiều năm làm việc ngắn ngủi, người ta đã chứng minh được rằng bất kỳ bản đồ nào chứa không quá 41 quốc gia đều có 4 màu chính xác. Từ đó, rõ ràng là nếu có một ví dụ bác bỏ giả thuyết của chúng tôi thì rất khó để xây dựng nó. Đồng thời, tồn tại 5 màu thông thường cho bất kỳ bản đồ hình cầu nào. Thử

Cơm. 4. Các nước từ A đến N, thủ đô và đường sá của các nước đó.

Cơm. 5. Đồ thị thủ đô và bản đồ đường đi và 4 màu thông thường.

26

Cơm. 6. Các đường màu đỏ mô tả các cạnh; đồ thị thủ đô, đường của bản đồ Hình 1 đủ để đạt tới đồ thị tam giác; Các cạnh này có thể được xây dựng theo một cách khác (ví dụ: ME cùng với NI, v.v.).

fa được coi là liền kề khi chúng được nối với nhau bằng một cạnh.

Bắt đầu tô màu các đỉnh của đồ thị thủ đô và đường của bản đồ trên hình cầu, chúng ta hãy kiểm tra xem có thể bổ sung một cạnh không cắt các cạnh khác của đồ thị hay không và nếu có thì chúng ta sẽ bổ sung nó (ví dụ: đồ thị ở Hình 5 có cạnh AK). Bất kỳ cách tô màu 4 đúng nào của biểu đồ thu được cũng sẽ đúng với biểu đồ gốc; nói chung thì điều ngược lại là không đúng - hai đỉnh không liên kết với nhau đã trở nên liền kề và phải có màu khác nhau. Chúng ta sẽ tiếp tục quá trình thêm các cạnh này.

Bài tập 3. Chứng minh rằng quá trình này kết thúc tại thời điểm đồ thị chia hình cầu thành các phần đùn cong. (Hình 6 hiển thị một biểu đồ xuất phát từ biểu đồ trong Hình 5.)

Đồ thị như vậy được gọi là đồ thị tam giác hình cầu *) và hình tam giác được gọi là các cạnh của đồ thị. Hình 7 biểu diễn đồ thị các đỉnh và các cạnh (theo cách hiểu hình học truyền thống của các từ này - “đỉnh của một tứ diện”, “cạnh của một khối lập phương”) của một khối 2 mặt đều - icosahedron; Đường 20 trông giống phần bên ngoài của tam giác XYZ.

Bài tập 4. Bản đồ phải như thế nào để đồ thị của nó có thể phẳng và trở thành đồ thị tam giác?

Bài tập 5. a) Chứng minh rằng đồ thị các đỉnh và cạnh của một hình bát diện đều - một hình mặt đều - có thể được tô màu đúng theo số ba.

b) Lập điều kiện cần và đủ để đồ thị tam giác có 3 màu.

Sách tô màu hình học

Việc tô màu 4 chính xác các đỉnh của bất kỳ đồ thị tam giác nào của hình cầu có thể có ý nghĩa hình học đơn giản và màu đỏ. Điều này giải thích mong muốn của chúng tôi là chuyển từ biểu đồ thủ đô và đường của bản đồ sang biểu đồ tam giác của nó, mặc dù bản thân màu bài toán thoạt nhìn chỉ là một điều kiện.

Chúng ta hãy xem xét một tứ diện neoctor, trong đó bốn đỉnh của nó được tô màu riêng của nó (Hình 8, e). Giả sử bây giờ đồ thị không có tác nhân tam giác hình cầu một cách chính xác

*) Tam giác (thuật ngữ trắc địa) - chia địa hình thành các hình tam giác.

27

Cơm. 8. Quá trình chồng bề mặt của một khối bát diện lên trên bề mặt của một khối tứ diện.

được sơn bốn màu giống nhau. Do đó, mỗi đỉnh của nó tương ứng với một đỉnh của tứ diện và bất kỳ hai đỉnh lân cận nào cũng khác nhau. Và điều này có nghĩa là mỗi cạnh và mỗi mặt của đồ thị tương ứng với một cạnh nhất định và một mặt nhất định của tứ diện: một cạnh của đồ thị là một cạnh của tứ diện, các đỉnh của chúng được sơn hai màu giống như các đỉnh của cạnh đồ thị, và các mặt của đồ thị là một mặt được xác định tương tự của tứ diện. Chúng ta có thể hình dung sự tương ứng này như sự chồng chất của bề mặt tam giác được tô màu của một hình cầu lên bề mặt tứ diện của một khối tứ diện, các đỉnh của chúng tượng trưng cho bốn màu tô. Sự chồng chéo này có thể được tìm thấy với bất kỳ đỉnh tam giác nào được tô màu bằng một số màu bằng cách kết hợp nó với một đỉnh tứ diện cùng màu. Di chuyển đến đỉnh liền kề của tam giác và kết hợp nó với đỉnh màu tương ứng của tứ diện (luôn khác với đỉnh đầu tiên!), chúng ta đồng thời thu được sự thẳng hàng của cạnh của tam giác với cạnh của tứ diện. Theo cách tương tự, chúng ta kết hợp mặt tam giác với mặt tứ diện, sau đó, từng bước thêm lớp phủ mong muốn.

Quá trình xếp chồng được mô tả được mô tả trong Hình 8 (a - e) cho bề mặt của một khối tám mặt đều - một khối tám mặt. Sau khi theo dõi cẩn thận các chi tiết của quá trình này bằng cách sử dụng ví dụ trên Hình 8, không khó hiểu tại sao có thể xảy ra sự chồng chéo như vậy với 4 màu và nó xảy ra như thế nào (một phần, bề mặt của hình cầu phải được coi là linh hoạt và cho phép tự giao nhau nếu cần thiết).

Sách tô màu số học

Nếu, khi áp dụng một đỉnh tam giác cụ thể, việc chỉ ra đỉnh của tứ diện mà nó đi qua (tức là màu của màu) là đủ, còn khi áp dụng một mặt cụ thể, việc chỉ ra mặt của tứ diện là đủ - bạn cũng cần biết nó được xếp chồng lên mặt nào trên mặt này - “phía trước” hoặc “phía sau”. Có thể thấy điều này bằng cách sử dụng ví dụ về lớp phủ được hiển thị trong Hình 8. Bây giờ chúng ta hãy hình thành các quy tắc sau.

(*) Nếu khi một mặt của đồ thị gán chồng lên một mặt của khối trung diện, mặt ngoài của nó trùng với cạnh ngoài của mặt của khối trung diện thì ta gán số +1 cho mặt này của đồ thị gán; nếu ở bên trong thì - 1 (xem Hình 8, a).

28

Những con số này được gọi là số tô màu Heawood - để vinh danh nhà toán học người Anh P. Heawood, người tiên phong bài toán về các màu sắc và người phát hiện ra các định luật “số học” trong bài toán bốn màu.

Thuộc tính chính, mặc dù rõ ràng, của số Heawood là như sau:

Bổ đề. Nếu số Heawood của hai mặt liền kề của phép trenagulation bằng nhau thì các mặt này được ánh xạ lên các mặt khác nhau (nhưng tất nhiên là tất cả các mặt lân cận) của khối trung diện; nếu chúng không bằng nhau thì các mặt này sẽ được ánh xạ lên một mặt của khối trung diện, một mặt có mặt “mặt trước”, mặt kia có mặt “xà phòng”.

Bổ đề này chỉ nêu chi tiết định nghĩa của số Heawood; nhưng ba tính chất số học sau đây của những con số này thoạt nhìn khá bất ngờ:

1. Tổng của tất cả các số Heawood tô màu chính xác các đỉnh của đồ thị trenagulation chia hết cho 4 (thuộc tính này mới được biết đến gần đây).

2. Hãy lấy bất kỳ đỉnh nào của trenagulation; tổng số Heawood của các mặt gặp nhau ở đỉnh này chia hết cho 3 (sự kiện cơ bản này được Heawood phát hiện vào năm 1898).

3. Ngược lại, nếu chúng ta chọn được các số ±1 cho các mặt của biểu đồ phân loại sao cho chúng thỏa mãn điều kiện 2), thì bài toán về việc tô màu đã được quyết định - chúng ta có thể áp đặt phân loại trên bề mặt của khối trung diện, tuân theo quy tắc (*); điều kiện 2) sẽ đảm bảo tính khả thi của việc áp đặt đó.

Các câu 1), 2), 3) có thể được minh họa bằng Hình 9, trong đó thể hiện biểu đồ hai mươi mặt và cách tô màu 4 mặt thông thường của nó.

Chúng ta sẽ chỉ chứng minh khẳng định 1); chứng minh khẳng định 2) tương tự và là nội dung của nhiệm vụ 6; bằng chứng 3) không hoàn toàn cơ bản và chúng tôi không trình bày nó. Chúng ta chỉ cần lưu ý rằng khả năng chia hết cho ba là do trong

29

Chúng ta sẽ chứng minh rằng tổng các số Heawood của các mặt trong mỗi nhóm này bằng nhau (nếu một trong các nhóm trống, nghĩa là không chứa một mặt nào, thì đương nhiên coi tổng tương ứng bằng 0; khi đó các tổng khác cũng sẽ bằng 0). Vì tổng của tất cả các số Heawood phân hủy thành tổng của bốn nhóm mặt, nên từ sự bằng nhau của các tổng này trên các nhóm sẽ dẫn đến sự chia hết cho số chẵn.

Chúng ta hãy chọn tùy ý hai mặt của tứ diện. Chúng ta hãy xem xét các nhóm mặt tam giác tương ứng và tính tổng các số Heawood của các mặt cho mỗi nhóm này. Bây giờ chúng ta lấy bất kỳ đồ thị tam giác nào có trong một trong các nhóm này và cạnh của nó ánh xạ tới cạnh chung của hai cạnh của tứ diện mà chúng ta đã chọn lúc đầu. Chúng ta hãy xem xét biểu đồ tam giác có cạnh chung này với cạnh danh nghĩa đầu tiên; Rõ ràng là mặt kết nối như vậy được xác định duy nhất. Hơn nữa, nó chỉ có thể được ánh xạ lên một trong các mặt đã chọn của tứ diện và do đó hoặc thuộc cùng một nhóm mặt với mặt thứ nhất - khi đó, theo bổ đề, số Heawood của các mặt này không bằng nhau, hoặc đi vào mặt thứ hai trong số các nhóm này - và sau đó, theo cùng một bổ đề, số Heawood của hai mặt này bằng nhau. Theo đó, nếu một trong hai tổng mà chúng ta đang xem xét bao gồm một số hạng (số Heawood của một mặt nhất định), thì tổng còn lại bao gồm một số hạng bằng nhau (số Heawood của mặt lân cận duy nhất từ ​​nhóm thứ hai), hoặc tổng đó bao gồm một số hạng có giá trị bằng nhau nhưng ngược dấu (số Heawood lại của mặt lân cận duy nhất, nhưng lần này là từ cùng một nhóm). Sự đẳng thức của hai tổng đã được chứng minh.

Bài 6. Chứng minh tính chất 2) của số Heawood bằng phương pháp tương tự.

Đừng tô màu mà hãy tính toán

Thuộc tính 3) của số Heawood cho phép người ta bắt đầu bài toán tìm cách tô màu 4 thông thường với một số bài toán số học trên đồ thị: tìm giá trị của ẩn số $x$ (Số Heawood)