Trang chủ Chuyện bên lề Thế giới của chúng ta rộng lớn hay bé nhỏ?

Thế giới của chúng ta rộng lớn hay bé nhỏ?

Sự rộng lớn hay bé nhỏ của một không gian được đo bằng khoảng cách. Vậy đâu là khoảng cách giữa mọi người trên thế giới này: Đó là hàng nghìn cây số xuyên qua các lục địa, các đại dương và những đường biên giới; hay đấy là khoảng cách của các mối quan hệ được kết nối bởi tình bạn, bởi sự lan tỏa và sẻ chia?

1. Để trả lời câu hỏi đó, chúng ta hãy tìm hiểu về một lý thuyết đang phát triển như vũ bão và thâm nhập vào mọi mặt của Khoa học công nghệ và cuộc sống – Lý thuyết đồ thị. Ta sẽ đi dọc theo lịch sử của Lý thuyết đồ thị từ hơn 300 năm trước với nhà Toán học lỗi lạc Leonard Euler – người đã có số tác phẩm toán học được coi là đồ sộ nhất trong lịch sử nhân loại, đến nhà toán học đương thời László Lovász – người vừa được nhận giải thưởng Abel (được ví như giải Nobel Toán học) năm 2021. Một số công trình của họ, dù có bề sâu suy tư và sự phức tạp tính toán phía sau thế nào, thì ý nghĩa của chúng lại hoàn toàn có thể diễn giải một cách trong sáng và thực tế.

PGS Phan Thị Hà Dương (Viện Toán học – VAST và Quỹ Đổi mới sáng tạo VINIF) trình bày về bài toán 7 cây cầu nổi tiếng ở Konigsberg và Lý thuyết đồ thị tại Ngày Toán học mở do Viện nghiên cứu cao cấp về Toán, Hệ thống giáo dục FPT và Sở GD ĐT Đà Nẵng tổ chức trung tuần tháng Tư vừa qua. Ảnh từ BTC.

Euler sinh ra ở Thụy Sĩ, ông đã bôn ba qua nhiều thành phố và đất nước Đức, Pháp rồi đến Nga – và chính tại đây năm 1736, ông đã giải bài toán 7 cây cầu nổi tiếng ở Konigsberg, từ đó khai sinh ra lý thuyết đồ thị. Thành phố Konigsberg có một dòng sông, với những hòn đảo và 7 cây cầu, làm thế nào để từ nhà mình đi dạo chơi qua các cây cầu, mỗi cầu đúng một lần rồi lại quay về nhà? Euler đã đơn giản tấm bản đồ của thành phố bằng một hình vẽ như sau: Có 4 đỉnh tượng trưng cho 4 miền đất A, B, C, D; và mỗi cây cầu nối hai vùng đất là một đường (gọi là một cạnh) nối hai đỉnh. Dễ thấy rằng mỗi khi ta đến một đỉnh thì phải dùng một cạnh và đi khỏi nó thì dùng cạnh khác. Vậy cứ mỗi lần đến rồi đi khỏi một đỉnh ta lại dùng chẵn cạnh. Kết luận của Euler là ta có một đường đi qua các cây cầu (sau này gọi là chu trình Euler) khi và chỉ khi mỗi đỉnh đều có chẵn cạnh.

Vậy đó, chỉ đơn giản vậy thôi, các đỉnh A, B, C, D đều có lẻ cạnh nên không đi được; vậy mà bao năm trước Euler người ta không nghĩ ra. Chính là vì Euler đã sáng tạo ra cách mô hình hóa một vấn đề thực tế bằng một cấu trúc toán học đơn giản và đẹp đẽ: Đồ thị.

Bản đồ thành phố Konigsberg
…và khi được đơn giản hóa thành đồ thị.

Vào thế kỷ 18 của Euler, thế giới rộng lớn và kiến thức truyền đi bằng những trang giấy cũng thật chậm. Phải 100 năm sau mới có khái niệm về chu trình Hamilton, rồi dần dần có Ramsey với lý thuyết tô màu, Erdos ông tổ của tổ hợp, Bruijn với những đường kẻ ứng dụng sâu xa trong sinh học, hóa học, Berge với những cuốn sách về Đồ thị và Siêu đồ thị như cuốn cẩm nang của sinh viên, Reyni đồng nghiệp xuất sắc của Erdos với mô hình sinh đồ thị ngẫu nhiên, Biggs với trò chơi Dollar Game trong Toán kinh tế, và Lovász – nhà toán học xuất chúng với các trò chơi trên đồ thị.

2. Phải đến giữa TK 20 khi tin học bắt đầu manh nha thì người ta mới sử dụng mạnh mẽ đồ thị để mô hình hóa hàng loạt bài toán và đưa vào tính toán trên máy tính. Và sự bùng nổ của Lý thuyết đồ thị đã thật sự đáng kinh ngạc vào thế kỷ 21 khi đồ thị ở khắp nơi nơi, đặc biệt nhất là trong Mạng xã hội. Hãy cùng xét một vài ví dụ.

Đồ thị các đường bay: Mỗi thành phố là một đỉnh và mỗi đường bay là một cạnh nối giữa hai đỉnh. Rõ ràng là đồ thị của Vietnam Airline đơn giản hơn nhiều khi so sánh với đồ thị của Northwest Airway, một hãng hàng không có nhiều đường bay hơn hẳn.

Đồ thị tình bạn: Mỗi người là một đỉnh còn mỗi tình bạn là một cạnh nối hai người bạn. Đồ thị đồng tác giả: Mỗi nhà khoa học là một đỉnh còn mỗi cạnh nối giữa hai tác giả nếu họ có viết chung bài báo với nhau. Đồ thị đóng chung phim: Mỗi diễn viên là một đỉnh và một cạnh nối giữa hai diễn viên có đóng chung phim với nhau. Đồ thị COVID để biểu thị mối quan hệ giao tiếp, ví dụ người F3 là người có khoảng cách 3 đến người bị bệnh F0. Và khổng lồ nhất là đồ thị hàng tỷ đỉnh Facebook, mỗi trang cá nhân là một đỉnh và một cạnh nối hai trang cá nhân nếu họ là bạn (friend) của nhau.

Bất cứ khi nào chúng ta có một mối quan hệ hai bên thì ta có thể biểu diễn bằng đồ thị.

Khổng lồ nhất là đồ thị hàng tỉ đỉnh Facebook, mỗi trang cá nhân là một đỉnh và một cạnh nối hai trang cá nhân nếu họ là bạn (friend) của nhau. Hình dáng của nó sẽ có dạng như hình trong ảnh. Ảnh từ BTC
Khổng lồ nhất là đồ thị hàng tỉ đỉnh Facebook, mỗi trang cá nhân là một đỉnh và một cạnh nối hai trang cá nhân nếu họ là bạn (friend) của nhau. Hình dáng của nó sẽ có dạng như hình trong ảnh. Ảnh từ BTC

Đồ thị đã khác xa về kích thước, không còn là 4 đỉnh là 7 cạnh nhỏ xinh nữa mà là hàng trăm, nghìn, triệu, tỷ đỉnh. Không còn là một hình vẽ bất động nữa mà là một đồ thị có thể biến động theo từng tích tắc: Mỗi một giây bao nhiêu tình bạn được kết nối và bao nhiêu trang cá nhân ra đời. Những vấn đề ta quan tâm cũng khác: Ta đâu còn nghĩ đến chuyện đi vòng quanh tất cả các đường bay nữa, ta chỉ đi từ nơi xuất phát đến thành phố ta mong muốn thôi; ta đâu còn quan tâm một người có chẵn hay lẻ bạn nữa bởi vì họ thêm bớt bạn dễ dàng lắm; ta chỉ quan tâm họ ít hay nhiều bạn thôi, họ có tầm ảnh hưởng lớn hay họ là một người cô đơn ít chia sẻ.

Ta sẽ tập trung vào câu hỏi tự nhiên nhất: Làm sao để đi đến được với nhau thật nhanh? Liệu chúng ta có biết đường đi ngắn nhất có bao nhiêu cạnh không? Hàng nghìn ư, hay hàng trăm? Thật đáng kinh ngạc, độ dài chỉ luôn nhỏ hơn vài chục, và thường được ví với số 6.

3. Đó chính là một tính chất đặc biệt của các đồ thị khổng lồ, của các mạng xã hội – khoảng cách giữa hai con người là rất bé. Ý tưởng về khoảng cách nhỏ trong các đồ thị mạng xã hội đã được nhen nhúm từ đầu thế kỷ 20, nhưng đến năm 1977, Milgram một nhà khoa học xã hội đã hiện thực hóa nó bằng một thí nghiệm nổi tiếng. Ông đã làm gần 300 bức thư và viết các địa chỉ thật vào các phong bì, trao cho những người khác nhau xa lạ. Mỗi người khi nhận được phong bì sẽ xem địa chỉ, nếu họ biết người nhận họ sẽ gửi thư cho người nhận, nếu họ không biết, họ sẽ gửi thư ấy cho một người bạn của họ. Rất có thể người bạn này cũng chẳng biết gì cả và cũng sẽ lại gửi thư đi như thế. Sau một thời gian dài, hầu hết các bức thư gửi ngẫu nhiên như vậy không tới đích, nhưng có khoảng hơn 60 bức thư tới đích và chúng thường tới rất nhanh, chỉ sau 5 hay 6 lần gửi thư. Milgram đã giả thuyết rằng trong một mạng lưới dày đặc các mối quan hệ bạn bè trong xã hội, khoảng cách giữa người gửi đầu tiên và người nhận cuối cùng chỉ là một số rất nhỏ, tỷ dụ như 6 mà thôi. Và ví dụ đó chính là minh họa của thuật ngữ “thế giới nhỏ”.

Tuy nhiên, cũng chính qua ví dụ của Milgram mà ta nhận thấy nếu những bức thư được gửi đi hú họa, thì rất có thể sẽ chẳng bao giờ đến nơi. Nhưng ta sẽ hiểu thế nào về sự hú họa đấy? Đó lại chính là một công trình của Lovász, bài báo “Tổng quan về Bước đi ngẫu nhiên” của ông đã thu hút hàng nghìn nhà khoa học. Bước đi ngẫu nhiên chính là việc gửi thư không suy nghĩ, nó được ví như một người vô định trên đường, khi ở ngã tư anh ta sẽ chọn hú họa một trong bốn con đường với xác xuất bằng 1/4, cứ thế mà đi loăng quăng trong đồ thị. Lovász đã chỉ ra rằng: “Bước đi ngẫu nhiên có một phân phối ổn định duy nhất là phân phối tỷ lệ thuận với bậc của đỉnh”. Phát biểu thuần toán học này hoàn toàn có thể giải thích cho những em bé mẫu giáo ngây thơ đang tin vào các câu chuyện cổ tích. Ý nghĩa của nó là: Nếu vào Giáng sinh, các ông già Noel đi chia quà, các ông cứ đi ngẫu nhiên, gặp ngôi nhà nào thì cho một gói quà, đi mãi đi mãi lòng vòng cũng được; thì khi đó những em bé nào nhà ở chỗ đông đúc sẽ nhận được nhiều quà hơn các em bé xa xôi, cụ thể là em bé ở ngã tư sẽ nhận được số quà gấp 4 lần em bé trong ngõ cụt. Tư tưởng này có nghĩa là nếu cứ đi ngẫu nhiên như vậy thì sẽ rất không công bằng, và các điểm trong ngõ nhỏ sẽ rất khó đi đến, đường đi đến chúng sẽ rất dài.

4. Vậy thì phải có các cách đi thông minh, có sự quan tâm để có thể tìm ra đường đi ngắn nhất. Các thuật toán tìm đường đi ngắn nhất đã được phát triển mạnh mẽ trong TK 20, mà nổi tiếng nhất là thuật toán Dijkstra. Tuy nhiên thuật toán này với các đồ thị mạng xã hội khổng lồ của TK21 thì sẽ chạy rất lâu và có khả năng treo máy. Vậy nên TK 21 đã chứng kiến hàng trăm công trình tính toán gần đúng các đường đi ngắn nhất trên đồ thị khổng lồ. Rất nhiều ý tưởng đã được đề xuất. Trong đó nổi bật là ý tưởng “landmark algorithm”: Chọn một số các đỉnh đặc biệt quan trọng – những đỉnh có nhiều cạnh. Tính khoảng cách từ các đỉnh đặc biệt đó đến các đỉnh khác. Nếu muốn tìm đường ngắn nhất từ đỉnh A đến đỉnh B thì ta xét các đường đi qua các đỉnh đặc biệt. Giả sử ta chọn đỉnh đặc biệt X, ta sẽ quan tâm đường đi từ A đến X rồi từ X đến B, hai con đường nhỏ này đã được tính từ trước nên ghép của hai con đường nhỏ này sẽ cho ta một con đường khá hợp lý từ A đến B. Ta cũng có thể thay đỉnh đặc biệt X bằng đỉnh đặc biệt Y khác nếu thấy nó cho kết quả tốt hơn. Ý tưởng này hay ở chỗ thường thì khoảng cách từ các đỉnh đặc biệt đến các đỉnh khác là nhỏ, nên ghép hai con đường nhỏ lại ta có 1 con đường hợp lý, hơn là ta cứ tìm đường đi zic zắc qua các đỉnh nhỏ thì có thể sẽ rất lâu.

Tư tưởng này trong lý thuyết toán học, nhưng cũng có thể nó có nguồn gốc sâu xa từ chính trong cuộc sống hoặc cuộc sống đã áp dụng các tư tưởng toán học. Hãy nghĩ đến Chương trình “Như chưa hề có cuộc chia ly”. Trước chương trình này, mọi người khi tìm người thân thì thường hỏi qua người quen, hay gửi tin lên báo đài; nhưng vì ít người biết nên các cuộc tìm kiếm thường rất lâu và không mấy thành công. Khi chương trình “Như chưa hề có cuộc chia ly” phát sóng, nó đã thu hút được hàng trăm nghìn người xem, rồi lại có hàng nghìn người chia sẻ lại, và thông tin lan tỏa, đến nỗi những thân phận lẻ loi cô đơn ở vùng sâu vùng xa cũng có thể tìm cho mình một cách đi đến với Chương trình và đã có hàng nghìn cuộc hội ngộ diễn ra. Ý tưởng tìm qua chương trình rất giống với tư tưởng thuật toán Landmark nói trên: Chương trình chính là một đỉnh đặc biệt, các trang mạng lớn chia sẻ chương trình cũng là những đỉnh đặc biệt, mà thông qua đó những con đường tìm đến nhau của bao người lưu lạc đã được rút ngắn.

5. Vậy đó, với sự phát triển của đồ thị khổng lồ, bao con người đã được kết nối với nhau; với sự quan tâm, cố gắng tìm ra những phương cách tìm kiếm tốt nhất, khoảng cách giữa bao con người đã trở nên bé lại và ta thấy thế giới dường như bé nhỏ.

Những ý tưởng toán học sâu sắc ấy đã thẩm thấu cả vào văn chương đương đại và được các nhà văn cất lên thành lời. Tác phẩm “Six degree of separation” (1990) của nhà văn John Guare rất nổi tiếng và đã nhận giải Pulitzer khi đề cập đến khoảng cách 6 trong các mạng xã hội, nó đã được dựng thành kịch công diễn trên các sân khấu lớn, dựng thành phim và rất thành công với nhiều đề cử giải thưởng lớn.

Một câu thoại nổi tiếng trong vở kịch đã diễn tả bản chất nhất ý nghĩa toán học của Đồ thị lớn, và thật gần gũi với cuộc đời:

“Tôi đọc ở đâu đó rằng mọi người trên trái đất này chỉ bị ngăn cách bởi 6 người khác. Đó là một ý niệm mới sâu xa làm sao…

Sáu bước trung gian. Giữa chúng ta và mọi người trên hành tinh này. Ông tổng thống Mỹ. Một người chèo thuyền Gondola ở Venice. Tôi thấy được an ủi sao khi nghĩ rằng chúng ta gần nhau biết bao nhưng đồng thời cũng thấy kỳ bí vô cùng vì chúng ta gần nhau đến thế. Bởi vì phải tìm cho ra 6 người kết nối ấy. Không chỉ là những tên tuổi lớn. Đó có thể là bất cứ ai. Một thổ dân trong rừng nhiệt đới. Một người vùng núi lửa. Một người Eskimo…

Làm thế nào để mỗi con người là một cánh cửa mới, mở ra một thế giới khác. 6 người trung gian giữa tôi và mỗi người còn lại trên hành tinh này. Nhưng làm sao, làm sao có thể tìm ra đúng 6 con người đó?”.

(*) Bài viết sử dụng hơn 30 tài liệu tham khảo.

Trích bài giảng đại chúng “Thế giới của chúng ta rộng lớn hay bé nhỏ” của PGS Phan Thị Hà Dương tại Đà Nẵng, 4/2021.

Phan Thị Hà Dương

Bài viết trên Báo Lao động cuối tuần (Báo giấy) và Báo Lao động Online

BÀI MỚI NHẤT

Chân dung hai nhà toán học là chủ nhân giải thưởng Abel 2021

Ngày 17/03/2021, Viện Hàn lâm Khoa học và Văn chương Na Uy quyết định trao tặng giải thưởng Abel 2021 cho hai nhà toán...

BÀI ĐỌC NHIỀU

Chân dung hai nhà toán học là chủ nhân giải thưởng Abel 2021

Ngày 17/03/2021, Viện Hàn lâm Khoa học và Văn chương Na Uy quyết định trao tặng giải thưởng Abel 2021 cho hai nhà toán...