Kết hợp toán học

Các ứng dụng của lý thuyết đồ thị

Đồ thị phẳng

Đồ thị G được gọi là phẳng nếu nó có thể được biểu diễn trên mặt phẳng theo kiểu sao cho các đỉnh đều là các điểm khác biệt, các cạnh là các đường cong đơn giản và không có hai cạnh nào gặp nhau ngoại trừ tại các đầu cuối của chúng. Ví dụ, K ₄, đồ thị hoàn chỉnh trên bốn đỉnh, là mặt phẳng, như Hình 4A chỉ ra.

Hai biểu đồ được gọi là đồng nhất nếu cả hai có thể thu được từ cùng một biểu đồ bằng cách chia các cạnh. Ví dụ, các đồ thị trong Hình 4A và Hình 4B là hình dạng đồng nhất.

Biểu đồ K _{m, n} là một biểu đồ trong đó tập đỉnh có thể được chia thành hai tập con, một có m đỉnh và cái kia có n đỉnh. Bất kỳ hai đỉnh của cùng một tập hợp con là không liền kề, trong khi bất kỳ hai đỉnh của các tập hợp con khác nhau đều liền kề nhau. Nhà toán học người Ba Lan Kazimierz Kuratowski năm 1930 đã chứng minh định lý nổi tiếng sau:

Một điều kiện cần và đủ để đồ thị G trở thành mặt phẳng là nó không chứa biểu đồ đồng nhất của biểu đồ con với K ₅ hoặc K _3,3 như trong Hình 5.

Một sự co rút cơ bản của đồ thị G là sự biến đổi của G thành đồ thị mới G ₁, sao cho hai đỉnh liền kề u và υ của G được thay thế bằng một đỉnh mới w trong G ₁ và w liền kề trong G ₁ với tất cả các đỉnh mà u hoặc υ liền kề trong G. Một đồ thị G * được gọi là sự co của G nếu G * có thể được lấy từ G bằng một chuỗi các cơn co thắt cơ bản. Sau đây là một đặc điểm khác của đồ thị phẳng do nhà toán học người Đức K. Wagner năm 1937.

Một đồ thị là phẳng nếu và chỉ khi nó không hợp đồng với K ₅ hoặc K _3,3.

Vấn đề bản đồ bốn màu

Trong hơn một thế kỷ, giải pháp cho vấn đề bản đồ bốn màu đã lảng tránh mọi nhà phân tích đã thử nó. Vấn đề có thể đã thu hút sự chú ý của Möbius, nhưng tài liệu tham khảo đầu tiên về nó dường như là một bức thư của một Francis Guthrie gửi cho anh trai mình, một học sinh của Augustus De Morgan, vào năm 1852.

Vấn đề liên quan đến các bản đồ phẳng, đó là, các phần của máy bay thành các vùng không chồng lấn giới hạn bởi các đường cong kín đơn giản. Trong các bản đồ địa lý, nó đã được quan sát theo kinh nghiệm, trong nhiều trường hợp đặc biệt đã được thử, rằng, nhiều nhất, cần có bốn màu để tô màu cho các vùng để hai vùng có chung một ranh giới luôn được tô màu khác nhau và trong trường hợp nhất định mà ít nhất bốn màu là cần thiết. (Các khu vực chỉ gặp nhau tại một điểm, chẳng hạn như các tiểu bang Colorado và Arizona ở Hoa Kỳ, không được coi là có ranh giới chung). Một sự chính thức hóa của quan sát thực nghiệm này cấu thành nên cái gọi là định lý bốn màu. Vấn đề là để chứng minh hoặc bác bỏ khẳng định rằng đây là trường hợp của mọi bản đồ phẳng. Ba màu đó sẽ không đủ dễ dàng được chứng minh, trong khi đó, đủ năm màu được chứng minh vào năm 1890 bởi nhà toán học người Anh, PJ Heawood.

Năm 1879 AB Kempe, một người Anh, đã đề xuất một giải pháp cho vấn đề bốn màu. Mặc dù Heawood cho thấy lập luận của Kempe là thiếu sót, hai trong số các khái niệm của nó đã tỏ ra có kết quả trong cuộc điều tra sau này. Một trong số đó, được gọi là không thể tránh khỏi, nêu chính xác sự bất khả thi của việc xây dựng bản đồ trong đó cứ một trong bốn cấu hình là không có (các cấu hình này bao gồm một vùng có hai hàng xóm, một với ba, một với bốn và một với năm). Khái niệm thứ hai, về tính dễ giảm, lấy tên từ bằng chứng hợp lệ của Kempe rằng nếu có một bản đồ yêu cầu ít nhất năm màu và có một vùng có bốn (hoặc ba hoặc hai) hàng xóm, thì phải có một bản đồ yêu cầu năm màu sắc cho một số vùng nhỏ hơn. Nỗ lực của Kempe để chứng minh khả năng thu nhỏ của một bản đồ có một khu vực với năm nước láng giềng là sai lầm, nhưng nó đã được sửa chữa trong một bằng chứng được công bố năm 1976 bởi Kenneth Appel và Wolfgang Haken của Hoa Kỳ. Bằng chứng của họ đã thu hút một số lời chỉ trích vì nó đòi hỏi phải đánh giá 1.936 trường hợp riêng biệt, mỗi trường hợp có tới 500.000 hoạt động logic. Appel, Haken và các cộng tác viên của họ đã nghĩ ra các chương trình giúp cho một máy tính kỹ thuật số lớn có thể xử lý các chi tiết này. Máy tính cần hơn 1.000 giờ để thực hiện nhiệm vụ và bằng chứng chính thức thu được dài hàng trăm trang.

Chu kỳ Euler và vấn đề cầu Königsberg

Một đa số G bao gồm một đỉnh V (G) không trống và một tập hợp con E (G) của tập hợp các cặp phần tử riêng biệt của V (G) không có thứ tự f-1 được gắn vào mỗi cặp. Nếu cặp (x ₁, x ₂) có tần số f thuộc E (G), thì các đỉnh x ₁ và x ₂ được nối bởi các cạnh f.

Một chu trình Euler của đa chữ G là một chuỗi khép kín trong đó mỗi cạnh xuất hiện chính xác một lần. Euler đã chỉ ra rằng một đa lớp sở hữu một chu kỳ Euler khi và chỉ khi nó được kết nối (ngoài các điểm bị cô lập) và số đỉnh của mức độ lẻ là 0 hoặc 2.

Vấn đề này đầu tiên phát sinh theo cách sau. Sông Pregel, được hình thành bởi hợp lưu của hai nhánh của nó, chảy qua thị trấn Königsberg và chảy ở hai bên đảo Kneiphof. Có bảy cây cầu, như trong Hình 6A. Người dân thị trấn tự hỏi liệu có thể đi dạo và băng qua từng cây cầu một lần hay không. Điều này tương đương với việc tìm một chu trình Euler cho đa hình trong Hình 6B. Euler cho thấy điều đó là không thể vì có bốn đỉnh của thứ tự lẻ.