Các nhà toán học hoàn thiện "bánh sandwich đồ thị" sau hai thập kỷ

Minh họa bánh sandwich đồ thị trong lý thuyết đồ thị

Các nhà toán học vừa hoàn thành chứng minh cho một phỏng đoán đã tồn tại hơn hai thập kỷ, mở đường cho cách tiếp cận mới trong việc phân tích các mạng phức tạp. Kết quả này không chỉ giải quyết một bài toán lý thuyết mà còn cung cấp công cụ mạnh mẽ để suy ra hàng loạt tính chất của đồ thị chỉ từ một cấu trúc đơn giản hơn.

Bánh sandwich đồ thị là gì?

Trong lý thuyết đồ thị, đồ thị là tập hợp các điểm (gọi là đỉnh) và các đường nối giữa chúng (gọi là cạnh). Đồ thị có thể biểu diễn mọi thứ, từ mạng xã hội, internet cho đến các nơ-ron trong não bộ.

Vào năm 2004, hai nhà toán học đặt ra giả thuyết về một dạng "bánh sandwich" đặc biệt. Ý tưởng là kẹp một loại đồ thị khó phân tích vào giữa hai đồ thị đơn giản hơn, theo một cách chặt chẽ về mặt toán học. Nếu chứng minh được sự tồn tại của chiếc bánh sandwich này, họ không chỉ chứng minh được một tính chất của đồ thị ở giữa, mà còn chứng minh được tất cả các tính chất quan trọng của nó.

"Khái niệm này quá đẹp. Điều cuốn hút tôi nhất chính là vẻ đẹp của nó," Pu Gao, nhà toán học tại Đại học Waterloo (Canada), chia sẻ.

Hai loại đồ thị ngẫu nhiên

Sơ đồ minh họa các loại đồ thị ngẫu nhiên

Vào cuối thập niên 1950, nhà toán học người Mỹ Edgar Gilbert nghiên cứu mạng điện thoại tại Bell Labs. Để hiểu rõ hơn về các mạng này, ông xây dựng một mô hình đơn giản về đồ thị "ngẫu nhiên", trong đó các đỉnh kết nối với nhau một cách ngẫu nhiên.

Để tạo loại đồ thị này, ta bắt đầu với một tập đỉnh. Chọn một cặp đỉnh bất kỳ và tung một đồng xu (có thể không cân bằng). Nếu ra mặt ngửa, ta vẽ một cạnh nối hai đỉnh đó. Lặp lại với mọi cặp đỉnh, ta thu được đồ thị nhị thức ngẫu nhiên.

Loại đồ thị này tương đối dễ phân tích và các nhà toán học đã chứng minh được nhiều kết quả thú vị về chúng. Tuy nhiên, chúng chưa phải là mô hình tốt nhất cho các mạng thực tế.

Một loại đồ thị khác là đồ thị chính quy ngẫu nhiên, trong đó mọi đỉnh đều có cùng số cạnh. Loại đồ thị này mô phỏng mạng thực tế chính xác hơn nhiều, nhưng vì các cạnh của chúng có cấu trúc ràng buộc và phụ thuộc lẫn nhau, việc phân tích chúng cũng khó hơn rất nhiều.

Ý tưởng cốt lõi của bánh sandwich

Minh họa cấu trúc bánh sandwich đồ thị

Câu hỏi đặt ra là: liệu có thể xấp xỉ đồ thị chính quy ngẫu nhiên bằng đồ thị nhị thức ngẫu nhiên hay không? Nếu được, các nhà toán học có thể suy ra nhiều tính chất khó chứng minh của đồ thị chính quy từ đồ thị nhị thức tương ứng — mà không tốn thêm công sức.

Vào đầu thập niên 2000, Jeong Han Kim (khi đó tại Microsoft Research) và Van Ha Vu (khi đó tại Đại học California, San Diego) đã chỉ ra cách làm điều này bằng một chiếc bánh sandwich đồ thị.

Ý tưởng, nói một cách đơn giản, là tìm ra một công thức duy nhất — một quá trình ngẫu nhiên — để xây dựng đồng thời cả đồ thị nhị thức và đồ thị chính quy. Công thức này không chỉ cần tạo ra đúng loại đồ thị mà còn phải đảm bảo chúng khớp với nhau theo cách phù hợp.

• Nửa dưới của bánh sandwich: Đồ thị chính quy chứa đồ thị nhị thức. Nếu đồ thị nhị thức có tính chất nào đó dễ xuất hiện hơn khi thêm cạnh, thì đồ thị chính quy cũng có tính chất đó.
• Nửa trên của bánh sandwich: Đồ thị chính quy nằm trong đồ thị nhị thức. Nếu đồ thị nhị thức lớn hơn có tính chất dễ xuất hiện hơn khi bớt cạnh, thì đồ thị chính quy cũng có tính chất đó.

Kim và Vu phỏng đoán rằng chỉ cần đồ thị chính quy có số cạnh hợp lý, gần như luôn có thể xây dựng được chiếc bánh sandwich này. Nhưng việc chứng minh đầy đủ thì không hề dễ dàng.

Chứng minh hoàn chỉnh

Năm 2023, ba nhà toán học — Richard Montgomery (Đại học Warwick), Natalie Behague (nghiên cứu sinh sau tiến sĩ của ông khi đó) và Daniel Iľkovič (nghiên cứu sinh tiến sĩ của ông) — bắt đầu tìm cách xây dựng đồ thị chính quy và đồ thị nhị thức ngẫu nhiên từng cạnh một, đảm bảo ở mỗi bước đồ thị chính quy luôn chứa đồ thị nhị thức.

Cách tiếp cận này giống như làm bánh sandwich từ những mẩu phô mai vụn nhỏ, đặt từng mẩu lên bánh mì, thay vì đặt cả lát phô mai cùng lúc.

Quy trình cụ thể như sau:

1. Bắt đầu với hai tập đỉnh không có cạnh. Một tập sẽ trở thành đồ thị nhị thức, tập kia thành đồ thị chính quy.
2. Xây dựng đồ thị nhị thức theo cách thông thường: chọn một cặp đỉnh và tung đồng xu có trọng số.
3. Nếu ra mặt ngửa, thêm cạnh vào cả đồ thị nhị thức lẫn đồ thị chính quy.
4. Nếu ra mặt sấp, không thêm cạnh vào đồ thị nhị thức, nhưng tung thêm một đồng xu thứ hai để quyết định có thêm cạnh vào đồ thị chính quy hay không.
5. Trọng số của đồng xu thứ hai thay đổi dần trong quá trình xây dựng, được tính toán khéo léo để đảm bảo đồ thị cuối cùng thực sự chính quy.

Để xây dựng nửa trên của bánh sandwich, nhóm nghiên cứu đảo ngược toàn bộ quá trình: bắt đầu với hai đồ thị chứa mọi cạnh có thể, sau đó loại bỏ dần từng cạnh cho đến khi thu được đồ thị chính quy và đồ thị nhị thức chứa nó.

Ý nghĩa đối với ngành công nghệ

Kết quả này mang ý nghĩa quan trọng vượt ra ngoài toán học thuần túy. Trong lĩnh vực học máy và trí tuệ nhân tạo, các mô hình dựa trên đồ thị như mạng nơ-ron đồ thị (GNN) đang ngày càng được sử dụng để phân tích dữ liệu có cấu trúc phức tạp — từ mạng xã hội, hệ thống gợi ý cho đến dự đoán cấu trúc protein.

Việc hiểu rõ hơn về mối quan hệ giữa các loại đồ thị ngẫu nhiên khác nhau có thể giúp các kỹ sư thiết kế thuật toán hiệu quả hơn, đặc biệt trong các bài toán tối ưu hóa mạng lưới như định tuyến internet, phân tích mạng lưới giao thông hay tối ưu hóa hạ tầng điện toán đám mây.

Với việc phỏng đoán bánh sandwich đã được chứng minh, các nhà toán học không còn phải chứng minh từng tính chất của đồ thị chính quy ngẫu nhiên từ đầu. Họ có thể tận dụng kho tàng kết quả phong phú đã có về đồ thị nhị thức ngẫu nhiên và thu được vô số tính chất một cách tự động.

"Phỏng đoán này theo một cách nào đó rất tự nhiên. Thật khó chịu khi nó vẫn chưa được chứng minh," Michael Krivelevich, nhà toán học tại Đại học Tel Aviv, nhận xét. Khi chứng kiến kết quả mới, ông cảm thấy "nhẹ nhõm phần nào".

Tương lai phía trước

Chứng minh này, được Gil Kalai (Đại học Hebrew ở Jerusalem) gọi là một "meta-định lý", cung cấp một bộ phương pháp mới giúp "làm giàu hộp công cụ" của giới toán học. Những phương pháp này có thể cho phép các nhà nghiên cứu hiểu sâu hơn về cấu trúc mạng lưới so với mục tiêu ban đầu.

Trong tương lai, các nhà nghiên cứu hy vọng có thể xây dựng những chiếc bánh sandwich phức tạp hơn, với nhiều lớp xen kẽ giữa đồ thị nhị thức và đồ thị chính quy, hoặc với các "nguyên liệu" khác. Qua đó, họ tiếp tục khám phá cách mà những quá trình ngẫu nhiên tưởng chừng rất khác nhau — một bị ràng buộc chặt chẽ, một hoàn toàn tự do — lại có nhiều điểm tương đồng hơn ta tưởng.

"Mối liên hệ sâu sắc giữa hai loại đồ thị đó dường như quá tốt để có thể là thật," Behague nói. "Nhưng nó lại là thật."