English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtĐồ thị và Mạng lướiĐồ thị trong cuộc sống hằng ngày
Qua khóa học này chunsg ta nhìn thấy được ứng dụng của nhiều lý thuyết đồ thị khác nhau, dù có sự sắp xếp. Hóa ra các đồ thị lại là trọng tâm của nhiều vật dụng và khái niệm hằng ngày quanh chúng ta.
Ví dụ như mạng internet là một đồ thị ảo cực lớn. Mỗi đỉnh là một trang web, và mỗi cạnh là đường kết nối giữa hai trang. Ghi nhớ rằng các đường dẫn internet chỉ đi một phía, vậy đồ thị này là đồ thị
Một số trang web, như Wikipedia hay Facebook, có rất nhiều đường dẫn, trong khi các trang web khác có ít đường dẫn hơn. Đây là nguyên tắc chính để Google sắp xếp các kết quả tìm kiếm.
Các trang web với nhiều đường dẫn tới thường sẽ có chất lượng cao hơn và được đưa lên đầu trang kết quả tìm kiếm. Ví dụ, khi gõ tìm "London", các trang web chính thức về du lịch London được đưa lên trước những trang bán hàng ở London, hay các trang blog của những người sống ở London. Ý tưởng đơn giản này xuất phát từ lý thuyết đồ thị, thuật toán xếp hạng trang (Page Rank Algorithm), đã làm cho Google trở thành công cụ tốt hơn nhiều so với các công cụ tìm kiếm ra đời lúc ban đầu.
Mạng internet là mạng lớn nhất được con người tạo ra từ trước đến nay. Hình ảnh dưới đây minh họa cho một phần rất nhỏ các servers được kết nối vào internet:
Trong khi các trang web và đường dẫn tạo nên một đồ thị ảo, có cả các đồ thị vật lý của các máy tính, servers, routers, đường điện thoại và đường cáp.
Mỗi lần bạn thực hiện một cuộc gọi hay mở một trang web, các tổng đài trong mạng lưới phải tìm cách kết nối người gửi và người nhận, mà không làm quá tải từng đường cáp hay đường truyền kết nối. Lý thuyết đồ thị và lý thuyết xác suất giúp ta có được dịch vụ tin cậy, ví dụ như tìm đường dẫn khác khi một số kết nối bị bận.
Lý thuyết đồ thị cũng có vai trò quan trọng trong giao thông và định hướng. Tất cả các chuyến bay, chuyến tàu, và hệ thống tàu điện ngầm tạo nên đồ thị, được sử dụng để sắp xếp thời gian biểu một cách hiệu quả. Một trong những đồ thị dễ nhận ra nhất là Bản đồ Tàu điện ngầm ở London:
Tất cả các con đường và đường cao tốc cùng tạo nên một đồ thị lớn, được sử dụng bởi các dịch vụ định vị như Google Maps khi tìm đường đi ngắn nhất giữa hai vị trí.
Trong tương lai, Các hệ thống vận chuyển thông minh sẽ giảm thiểu kẹt xe và tai nạn bằng cách hướng dẫn xe đi một cách hiệu quả hơn, sử dụng địa điểm thu thập được từ những chiếc điện thoại thông minh hay xe tự lái. Điều này có thể giúp tiết kiệm hàng triệu giờ phí phạm mỗi năm trên đường, giảm thiểu ô nhiễm và giúp các dịch vụ khẩn khấp di chuyển nhanh hơn.
Ảnh này thể hiện mạng lưới các chuyến bay qua Bắc Âu.
Có vô vàn các đồ thị khác trong khoa học kỹ thuật và cuộc sống hằng ngày:
Kết nối nguyên tử giữa các phân tử và lưới tinh thể tạo nên đồ thị.
Sự lây truyền bệnh và đại dịch cũng được mô tả sử dụng đồ thị.
Trong Sin học, cây tiến hóa cho thấy tổ tiên của các loài kết nối với nhau tạo nên đồ thị.
Các thành phần khác nhau của các mạch điện và các con chips máy tính tạo nên mạng lưới.
Cấu trúc ngữ pháp của các ngôn ngữ có thể được minh học sử dụng đồ thị, ví dụ để tạo nên các thuật toán dịch ngôn ngữ.
Đồ thị cũng có nhiều ứng dụng khác trong xác suất, lý thuyết trò chơi and các bài toán tài chính.
Mạng xã hội
Cuối cùng, hãy nghĩ về một ví dụ rất tốt sử dụng đồ thị trong cuộc sống hằng ngày của chúng ta: mạng xã hội. Ở đây các đỉnh tượng trưng cho
Khi chúng ta vẽ các mạng xã hội, chúng ta có thể thấy rõ các cụm (clusters) của những người bạn chung, những người học cùng nhau hay sống trong cùng một thành phố. Chúng ta cũng xác định được trung tâm của mỗi người, tùy thuộc vào việc các đỉnh kết nối tốt với nhau như thế nào, và có thể đo lường được mức độ nổi tiếng của người đó trên mạng xã hội. figure: x-img(lightbox src="/content/graph-theory/images/social-network.png" width=720 height=500)
Năm 2014, Facebook có tổng cộng 1.4 tỷ người sử dụng tích cực và có hơn 200 tỷ kết nối. Nửa số người sử dụng Facebook có hơn 200 người bạn, và bởi vì mỗi người bạn của chúng ta cũng có khoảng chừng đó số bạn, chúng ta dễ dàng có được cả ngàn người bạn của bạn.
Một câu hỏi thú vị đặt ra là nối bạn chọ ngẫu nhiên hai người sử dụng Facebook bất kỳ, có bao nhiêu "cạnh mối quan hệ" bạn đi theo để nối với nhau? Ví dụ, khoảng cách giữa các người bạn kết nối trực tiếp là
Dựa theo một nghiên cứu Facebook thực hiện vào năm 2016, bạn, trung bình, kết nối với bất kỳ người nào trên FB thông qua nhiều nhất 3.57 người khác: chúng ta gọi là 3.57 độ cách biệt.
Nói cách khác, nếu bạn chọn ngẫu nhiên bất kỳ người nào trong hàng tỷ người sử dụng Facebook trên thế giới, người đó sẽ có một người bạn của một người bạn biết một người bạn của một trong những người bạn của bạn. Và điều này áp dụng cho cả người nổi tiếng, chính trị gia và người trong hoàng tộc...
Geographic visualisation of all Facebook friendships in 2010.
Năm 1929, khi một tách giả người Hungary
Năm 1967,
Ngày nay, mỗi chúng ta là một phần của vô vàn các đồ thị vô hình, là gốc của những kết nối xã hội, du lịch, internet và khoa học, kỹ thuật và còn nhiều hơn thế nữa.