Bạn đã bao giờ thử trò chơi trí tuệ sau đây trong đó bạn phải nối các dấu chấm để tạo thành một đường thẳng và phác thảo một ngôi nhà chỉ trong một nét mà không vượt qua đường kẻ đó chưa? Hoặc có thể bạn đã nhấp vào đề xuất kết bạn trên Facebook hoặc chơi Settlers of Catan. Nếu vậy thì bạn đã từng trải nghiệm một dạng lý thuyết đồ thị, một lĩnh vực toán học khiến Tiến sĩ Xujun Liu của Đại học Xi'an Jiaotong ở Trung Quốc mê hoặc.
Lý thuyết đồ thị được sử dụng để hiểu các mạng phức tạp. Những tiến bộ gần đây trong nghiên cứu "tô màu" cung cấp cái nhìn sâu sắc về việc tối ưu hóa cấu trúc mạng và hệ thống truyền thông tiềm năng. Tiến sĩ Liu Xujun và các cộng sự của ông đã giải quyết thành công một vấn đề thu hút sự chú ý rộng rãi trong lĩnh vực này.
Nối các dấu chấm để tạo thành một đường thẳng và phác thảo đường viền của ngôi nhà bằng một nét mà không vượt qua đường kẻ. Nguồn ảnh:
Vậy đồ họa là gì?
Giả sử bạn muốn tìm ra cách hiệu quả nhất để di chuyển bằng tàu hỏa giữa London và Vienna. Bạn có thể vẽ mỗi thành phố dưới dạng một điểm (gọi là đỉnh trong toán học) và các tuyến đường giữa các thành phố dưới dạng đường thẳng hoặc đường cong (gọi là cạnh). Sự kết hợp của các đỉnh và các cạnh tạo thành một đồ thị. Bản đồ này sau đó có thể được sử dụng để nghiên cứu các kết nối và tuyến đường giữa hai thành phố. Lý thuyết đồ thị giúp các nhà toán học lập mô hình và phân tích các mạng phức tạp trong nhiều lĩnh vực khác nhau như khoa học máy tính và kỹ thuật điện.
Di chuyển từ Luân Đôn đến Vienna bằng tàu hỏa: Sơ đồ hiển thị các tuyến đường có thể đi qua các thành phố nhỏ hơn. Nguồn:
Nghiên cứu của nhóm liên quan đến một khía cạnh của lý thuyết đồ thị, đó là tô màu. Lý thuyết tô màu giải quyết vấn đề dán nhãn các phần nhất định của biểu đồ để tuân theo các quy tắc nhất định và tránh những xung đột nhất định.
Ví dụ: hãy tưởng tượng rằng bạn muốn tô màu từng điểm bên dưới để không bao giờ có hai điểm cùng màu cạnh nhau - đây là một ví dụ về tô màu.
Nếu không có hai điểm cùng màu liền kề thì bốn điểm cần ít nhất hai màu. Nguồn hình ảnh: Giữa chúng phải có ít nhất một khoảng cách nhất định và khoảng cách tối thiểu cần thiết cho mỗi tần số là khác nhau. Một câu hỏi nảy sinh từ vấn đề này là 'Số tần số tối thiểu cần thiết cho việc phân bổ này là bao nhiêu? Nguồn:
Bài toán này liên quan đến việc phân vùng các đồ thị khối con, trong đó mỗi đỉnh (điểm) được nối với nhau bằng tối đa ba cạnh (đường). Xét rằng có hai loại cạnh khác nhau, nhiệm vụ là xác định cách chia các cạnh thành nhiều loại:
Loại I - yêu cầu mỗi cặp cạnh không có chung một điểm cuối (mỗi cạnh có hai điểm cuối).
Loại II-Yêu cầu mỗi cặp cạnh không những không dùng chung một điểm cuối mà các điểm cuối của chúng cũng không được kết nối bởi một cạnh khác.
Câu hỏi mà nhóm nghiên cứu đặt ra là liệu có thể giữ cố định số lượng Lớp Is ở một trong khi giảm thiểu số lượng Lớp II hay không.
Ví dụ về hai cạnh không có chung điểm cuối và điểm cuối của chúng không được kết nối bởi một cạnh khác. Nguồn hình ảnh:
Vì Tiến sĩ Liu quyết định theo đuổi bằng Tiến sĩ về lý thuyết đồ thị dưới sự giám sát của Giáo sư Alexander Kostochka tại Đại học Illinois, ông đã giải quyết thành công một số giả thuyết, trong đó có một bài toán do Szemerédi, người đoạt giải Abel năm 2012 và các đồng tác giả của ông đặt ra.
Tiến sĩ Liu cho biết ông sẽ tiếp tục giải quyết nhiều vấn đề hơn trong lĩnh vực này. "Tôi dự định tiếp tục nghiên cứu các vấn đề tô màu đồ thị, tập trung khám phá việc tô màu gói thông qua nhiều phương pháp hơn, chẳng hạn như phương pháp tổ hợp Nullstellensatz và phương pháp xác suất. Tôi hy vọng sẽ có những đóng góp có ý nghĩa cho lĩnh vực này thông qua các hướng nghiên cứu này.