Thế
giới của chúng ta rộng lớn hay bé nhỏ?
Phan
Thị Hà Dương
LĐO | 08/05/2021 |
17:31
https://laodong.vn/lao-dong-cuoi-tuan/the-gioi-cua-chung-ta-rong-lon-hay-be-nho-906630.ldo
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ế.
https://media-cdn.laodong.vn/Storage/NewsPortal/2021/5/7/906630/IMG_6033-01.jfif
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ị.
https://media-cdn.laodong.vn/Storage/NewsPortal/2021/5/7/906630/Konigsberg--1905-13.jpg
Bản đồ thành phố Konigsberg...
https://media-cdn.laodong.vn/Storage/NewsPortal/2021/5/7/906630/Dothi7caycau.jpg
...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ị.
https://media-cdn.laodong.vn/Storage/NewsPortal/2021/5/7/906630/Lien-Ket.png
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 đó?”.
VIDEO : https://media-cdn.laodong.vn/Storage/NewsPortal/2021/5/7/906630/videos/Video.mp4
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.
(*) Bài viết sử dụng hơn 30 tài liệu tham khảo.
PHAN THỊ HÀ DƯƠNG
No comments:
Post a Comment