PGS.TSKH Phan Thị Hà Dương: “Chỉ cần đi qua 6 bước thì 2 người xa lạ sẽ đến được với nhau”

Với bài giảng “Thế giới của chúng ta rộng lớn hay bé nhỏ”, PGS.TSKH Phan Thị Hà Dương đã chứng minh Toán học không hề khô khan, xa vời mà rất thực tế và thú vị. Đặc biệt, chị Hà Dương đã có một câu kết luận khiến rất nhiều người trong hội trường hứng thú và tâm đắc: “Chỉ cần đi qua 6 bước thì 2 người xa lạ sẽ đến được với nhau”.

Leonhard Euler – “Cha đẻ” của lý thuyết đồ thị với bài toán 7 cây cầu ở Konigsberg

PGS.TSKH Phan Thị Hà Dương đã bắt đầu bài giảng “Thế giới của chúng ta rộng lớn hay bé nhỏ?” bằng câu chuyện về nhà toán học lỗi lạc Leonhard Euler và bài toán 7 cây cầu ở Konigsberg.

Konigsberg là một thành phố cổ có 1 dòng sông và 7 chiếc cầu, mỗi cây cầu sẽ nối liền 2 bờ sông hoặc một bờ sông với một trong hai cù lao, hoặc nối 2 cù lao với nhau. Người dân ở đây đã đặt ra một câu đố mà chưa từng có ai giải được: "Liệu có thể đi một lần qua tất cả 7 chiếc cầu mà không phải lặp lại hay không (hay mỗi cây cầu chỉ được đi qua một lần duy nhất)?".

Năm 1735, nhà toán học lỗi lạc Leonhard Euler đã tình cờ nghe được câu chuyện này khi tới nơi đây và chứng minh được bài toán này không có lời giải hay không thể thực hiện được. Chính việc giải bài toán đã giúp Euler mở ra một nhánh mới trong toán học: Lý thuyết đồ thị.

Đầu tiên, Euler tìm cách "mô hình hóa" bài toán một cách trừu tượng nhất thông qua việc biểu diễn các cù lao hay bờ sông bằng các điểm còn các cây cầu là đoạn thẳng. Như vậy, Euler đã có một mô hình đơn giản nhất của bài toán 7 cây cầu, cách biểu diễn bằng các điểm và đoạn thẳng chính là bước đầu của sự ra đời lý thuyết đồ thị ngày nay.

Euler đã giải bài toán bằng cách sử dụng số cạnh của các điểm. Cụ thể hơn, ở bài toán 7 cây cầu có 3 điểm có cạnh bằng 3 và một điểm có cạnh là 5. Tuy nhiên, Euler lại chứng minh bài toán chỉ có thể giải được khi không có số lẻ hay nói cách khác bài toán vô nghiệm.

Ứng dụng lý thuyết đồ thị vào đời sống hiện tại

Từ những viên gạch đầu tiên về lý thuyết đồ thị của Euler, các nhà khoa học đã quan tâm, phát triển và ứng dụng định lý này trong các lĩnh vực Sinh học, Hóa học, Vật lý, Tin học…

Cả hội trường đã ồ lên thích thú khi PGS.TSKH. Phan Thị Hà Dương cho thấy ứng dụng của lý thuyết đồ thị trong đời sống. Theo đó, đồ thị ở khắp mọi nơi và ở đâu xuất hiện mối quan hệ giữa 2 đối tượng thì sẽ có sự tồn tại của đồ thị.

Chẳng hạn như mạng xã hội Facebook, nếu như mỗi trang Facebook là 1 điểm, 2 trang Facebook kết bạn với nhau được tính là đã kết nối. Mỗi người có thể có đến 5.000 người bạn thì như vậy những đường nối sẽ vô cùng phức tạp. Tiếp đó, đồ thị này không đều đặn vì những người có tầm ảnh hưởng sẽ có nhiều bạn bè, nhiều người theo dõi sẽ trở thành trung tâm của đồ thị, trái ngược lại với những người sống khép kín hơn, ít bạn bè và ít kết nối.

Ngoài ra, PGS.TSKH. Phan Thị Hà Dương cũng lấy ví dụ về các dạng đồ thị khác, gồm: Đồ thị mạng lưới các đường bay: Các đỉnh là thành phố, các cạnh là các chuyến bay giữa 2 thành phố. Nếu mạng lưới càng phức tạp thì chứng tỏ hãng hàng không này càng phát triển, có nhiều đường bay; Đồ thị tình bạn: Mỗi người là một đỉnh, mỗi cạnh là một mối quan hệ. Những người có tầm ảnh hưởng, quảng giao sẽ tạo nên đồ thị phức tạp và ngược lại; Đồ thị đồng tác giả bài báo: Mỗi đỉnh là 1 nhà khoa học, 2 đỉnh sẽ nối với nhau nếu 2 nhà khoa học viết chung bài báo (hợp tác khoa học.

PGS.TSKH. Phan Thị Hà Dương cũng nhấn mạnh, đồ thị và khoa học công nghệ hiện đại có mối quan hệ chặt chẽ. Chúng có tới hàng trăm nghìn đến hàng triệu, tỉ đỉnh và liên tục thay đổi, khó đoán vì mỗi giây có hàng trăm đỉnh mới, hàng ngàn cạnh mới sinh ra hoặc mất đi.

Đồ thị của ngày hôm nay cũng khác với đồ thị của thời cổ đại. Thay vì giải đáp những câu hỏi sơ khai về câu cầu thì chúng ta dùng đồ thị để giải đáp các câu hỏi xã hội. Chẳng hạn như làm sao để bay từ một thành phố này đến thành phố khác với số chặng bay ít nhất, làm sao để 2 người xa lạ có thể làm quen với nhau thông qua 1 người bạn chung, làm sao để truyền thông tin đi nhanh nhất, ai là người có nhiều ảnh hưởng nhất…

Sau khi phân tích ví dụ về tìm đường đi và khoảng cách tối đa, số Erdos, số Bacon hay khoảng cách Covid, PGS.TSKH. Phan Thị Hà Dương rút ra kết luận: Tìm ra khoảng cách ngắn nhất là điều rất quan trọng. Điều này được áp dụng trong việc tìm ra các chặng bay, các hành trình tối ưu để tiết kiệm thời gian, năng lượng cho nhân loại hay xác định nhóm bệnh nhân F0 – F1 – F2… để đề ra phương pháp tránh lây lan dịch bệnh.

Chỉ cần đi qua 6 bước thì 2 người xa lạ sẽ đến được với nhau

Câu chuyện của PGS.TSKH. Phan Thị Hà Dương tiếp tục đưa người nghe tới những vùng kiến thức mới mẻ và lý thú. Quay ngược lại ví dụ 7 cây cầu ở Konigsberg, PGS.TSKH. Phan Thị Hà Dương đặt ra câu hỏi tại sao Euler lại cho rằng số đỉnh tối đa của đồ thị chỉ là 6.

Trong giới nghiên cứu, nếu các nhà khoa học nghi ngờ sẽ tiến hành nghiên cứu để chứng minh, trong đó nổi bật là thí nghiệm của Milgram (1974). Cụ thể, ông đã gửi 200 bức thư có địa chỉ người nhận đến các thành phố khác nhau và người nhận thư với người được ghi tên trên phong bì thư không quen nhau. Kết quả, hầu như các bức thư không được gửi tới đích, những bức thư được gửi tới đích thường trải qua 5 – 6 bước (người nhận thư thấy tên trên phong bì thư là người quen nên chuyển cho họ hoặc họ biết đây là người quen của người quen nên chuyển trao tay cho nhau tới đích cuối cùng). Vì thế, ông nhận ra đồ thị có tính giới hạn, dù lớn đến đâu thì số đỉnh cũng chỉ là 6. Cũng từ đây, khái niệm “thế giới nhỏ” ra đời.

Qua ví dụ này, PGS.TSKH. Phan Thị Hà Dương đã đưa ra một kết luận thú vị khi đối chiếu về các mối quan hệ của con người: Chỉ cần đi qua 6 bước (bước trung gian) thì 2 người xa lạ sẽ đến được với nhau.

Bùng nổ các thuật toán tìm đường đi ngắn nhất giữa 2 đỉnh trong đồ thị

Nếu đồ thị có 100 đỉnh, 3.000 cạnh thì mất khoảng hàng chục nghìn bước. Nếu đồ thị có tỷ định, trăm tỷ cạnh thì mất khoảng hàng nghìn tỉ bước. Khi áp dụng thuật toán kinh điển Dijkstra, người ta nhận ra việc tìm đường đi ngắn nhất một cách chính xác mất rất nhiều thời gian nên “thuật toán xấp xỉ” được sử dụng phổ biến hơn để thay thế.

Lý giải về điều này, PGS.TSKH. Phan Thị Hà Dương lấy ví dụ về đồ thị có hàng triệu đỉnh thì người ta phải tìm ra tất cả các cạnh của nó để xác định đường đi ngắn nhất. Thuật toán lớn sẽ bỏ quên những đỉnh rất nhỏ, khoảng cách rất nhỏ và chúng ta không thể đánh đổi thời gian để tìm những thứ rất nhỏ đó.

Để khép lại bài giảng đại chúng “Thế giới của chúng ta rộng lớn hay bé nhỏ?”, PGS.TSKH. Phan Thị Hà Dương mượn lời của tác phẩm văn học “6 bước trung gian” như sau:

“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 tình này. Ông tổng thống Mỹ. Một người chèo thuyền Gondola ở Venise. Tôi thấy được an ủi sau 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 đó?”.

Huệ Anh (tường thuật)

Tổ chức Giáo dục FPT – fpt.edu.vn