Bài viết này đi sâu vào một khía cạnh thú vị của lý thuyết đồ thị: **đồ thị Nguyen Huy Xuong** và khả năng nhúng chúng vào các bề mặt khác nhau. Chúng ta sẽ khám phá những thách thức và kết quả liên quan đến việc nhúng đồ thị này, đồng thời làm sáng tỏ ý nghĩa của nó trong lĩnh vực toán học này. Hiểu được những khái niệm này sẽ mở ra những hướng tiếp cận mới cho các bài toán liên quan đến lý thuyết đồ thị và hình học.
Trong lý thuyết đồ thị, việc **nhúng một đồ thị** vào một bề mặt là biểu diễn đồ thị trên bề mặt đó sao cho các cạnh chỉ giao nhau tại các đỉnh. Một loại nhúng đặc biệt là **nhúng vòng tròn (circular embedding)** hay còn gọi là nhúng mạnh (strong embedding), trong đó mỗi mặt của hình nhúng được giới hạn bởi một chu trình của đồ thị. Giả thuyết nhúng vòng tròn (Circular Embedding Conjecture) cho rằng mọi đồ thị 2-liên thông đều có một hình nhúng vòng tròn trên một bề mặt nào đó. Tuy nhiên, giả thuyết này không đảm bảo rằng hình nhúng sẽ nằm trên bề mặt có genus tối thiểu.
Nguyễn Huy Xuong đã đưa ra một ví dụ về một đồ thị toroidal 2-liên thông (toroidal graph) mà không có hình nhúng vòng tròn nào nằm trên một hình xuyến (torus). Điều này cho thấy genus của một đồ thị không nhất thiết phải giống với genus cần thiết cho một hình nhúng mạnh của đồ thị đó. Đây là một phát hiện quan trọng, làm nổi bật sự phức tạp trong mối quan hệ giữa cấu trúc đồ thị và các đặc tính tô pô của các bề mặt mà chúng có thể được nhúng vào.
Đồ thị Nguyen Huy Xuong là một ví dụ cụ thể cho thấy sự khác biệt giữa genus của một đồ thị và genus của bề mặt tối thiểu cần thiết cho một hình nhúng mạnh. Đồ thị này có 12 đỉnh và 18 cạnh. Việc tìm một chu trình bao phủ kép (cycle double cover) cho đồ thị này, bao gồm 6 chu trình, dẫn đến một mâu thuẫn thú vị. Theo một bài báo khác, các chu trình từ một chu trình bao phủ kép của một đồ thị cubic 2-liên thông, như đồ thị Xuong, phải tương ứng với các mặt của một hình nhúng nào đó.
Tuy nhiên, với 6 mặt, đồ thị Xuong có đặc trưng Euler (Euler's characteristic) bằng 0, và do đó, genus bằng 1. Điều này tương ứng với genus của đồ thị, như được thể hiện bởi hình nhúng toroidal. Vậy điều gì đang xảy ra? Ngay cả khi đồ thị Xuong không có hình nhúng vòng tròn trên hình xuyến, liệu nó có hình nhúng vòng tròn trên một bề mặt có genus 1 không? Điều này mâu thuẫn với tuyên bố rằng genus của bề mặt không được tối thiểu hóa. Mâu thuẫn này làm nổi bật sự cần thiết phải hiểu sâu hơn về các điều kiện cần và đủ để một đồ thị có hình nhúng vòng tròn trên một bề mặt nhất định.
Nói chung, genus của một đồ thị được định nghĩa là genus *hướng được* của nó: giá trị *g* nhỏ nhất sao cho đồ thị có một hình nhúng trong một hình xuyến *g*-lỗ (một hình cầu, nếu *g* = 0). Đồ thị *G* trong câu hỏi không có hình nhúng toroidal, nhưng lại có một hình nhúng trong hình xuyến, vì vậy nó có genus 2. Chu trình bao phủ kép (double cover) trong câu hỏi cho ta một hình nhúng của *G* trên bình Klein (Klein bottle). Ta có thể nhận biết điều này vì:
Theo quy ước, bình Klein được cho là có genus không hướng được là 2, bởi vì nó là tổng kết nối của hai mặt phẳng xạ ảnh (giống như một bề mặt có genus hướng được-2 là tổng kết nối của hai hình xuyến). Vì vậy, ngay cả khi chúng ta xét genus không hướng được, chúng ta cũng không nói rằng *G* có một hình nhúng mạnh của genus 1. Nếu điều này không thỏa mãn, Mohar (2010) đưa ra các ví dụ về đồ thị trên 18*n* − 6 đỉnh với genus 1 mà genus tối thiểu của một hình nhúng mạnh (trên một bề mặt hướng được *hoặc* không hướng được!) có genus ít nhất là *n*.
Nghiên cứu về đồ thị Nguyen Huy Xuong có ý nghĩa quan trọng trong việc hiểu các giới hạn của giả thuyết nhúng vòng tròn và mối quan hệ phức tạp giữa cấu trúc đồ thị và tô pô bề mặt. Những phát hiện này có ứng dụng trong:
Việc tiếp tục nghiên cứu các đồ thị như đồ thị Nguyen Huy Xuong sẽ giúp chúng ta có được những hiểu biết sâu sắc hơn về lý thuyết đồ thị và các ứng dụng tiềm năng của nó trong nhiều lĩnh vực khác nhau. Các nghiên cứu này đóng vai trò quan trọng trong việc khám phá những giới hạn và tiềm năng của lý thuyết đồ thị, từ đó mở ra những con đường mới cho nghiên cứu và ứng dụng trong tương lai.
Bài viết liên quan