Đồ thị trong cuộc sống hằng ngày – Đồ thị và Mạng lưới – Mathigon

Thời gian đọc : ~ 20 minQua 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 những đồ thị lại là trọng tâm của nhiều đồ vật và khái niệm hằng ngày quanh tất cả chúng ta .Ví dụ như mạng internet là một đồ thị ảo cực lớn. Mỗi đỉnh là một website, và mỗi cạnh là đường liên kết giữa hai trang. Ghi nhớ rằng những đường dẫn internet chỉ đi một phía, vậy đồ thị này là đồ thị, và đồ thị này rất, rất, lớn .

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ỏ những servers được liên kết vào internet :© LyonLabs, LLC and Barrett Lyon, năm trướcTrong khi những website và đường dẫn tạo nên một đồ thị ảo, có cả những đồ thị vật lý của những máy tính, servers, routers, đường điện thoại thông minh và đường cáp .Mỗi lần bạn triển khai một cuộc gọi hay mở một website, những tổng đài trong mạng lưới phải tìm cách liên kết 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 liên kết. Lý thuyết đồ thị và lý thuyết Phần Trăm giúp ta có được dịch vụ an toàn và đáng tin cậy, ví dụ như tìm đường dẫn khác khi 1 số ít liên kết bị bận .Lý thuyết đồ thị cũng có vai trò quan trọng trong giao thông vận tải và khuynh hướng. Tất cả những chuyến bay, chuyến tàu, và mạng lưới hệ thống tàu điện ngầm tạo nên đồ thị, được sử dụng để sắp xếp thời hạn biểu một cách hiệu suất cao. 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ả những con đường và đường cao tốc cùng tạo nên một đồ thị lớn, được sử dụng bởi những dịch vụ xác định 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 bộc lộ mạng lưới những chuyến bay qua Bắc Âu .Có vô vàn những đồ thị khác trong khoa học kỹ thuật và đời sống hằng ngày :

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 đời sống hằng ngày của tất cả chúng ta : mạng xã hội. Ở đây những đỉnh tượng trưng cho và những cạnh tượng trưng cho mối quan hệ bè bạn, ĐK, hay theo dõi .

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 năm trước, Facebook có tổng số 1.4 tỷ người sử dụng tích cực và có hơn 200 tỷ liên kết. Nửa số người sử dụng Facebook có hơn 200 người bạn, và chính do mỗi người bạn của tất cả chúng ta cũng có khoảng chừng chừng đó số bạn, tất cả chúng ta thuận tiện có được cả ngàn người bạn của bạn .Một câu hỏi mê hoặc đặ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 những người bạn liên kết trực tiếp là, và khoảng cách giữa bạn với bạn của bạn là, v … v …

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 quốc tế, 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 vận dụng cho cả người nổi tiếng, chính trị gia và người trong hoàng tộc …

Năm 1929, khi một tách giả người Hungary Frigyes Karinthy tiên phong đưa ra sáng tạo độc đáo “ 6 Độ Cách Biệt ”, lúc đó chưa có internet hay mạng xã hội, nhưng quốc tế đã trở nên liên kết thoáng đãng hơn khi nào hết .Năm 1967, Stanley Milgram triển khai thí nghiệm khảo nghiệm tiên phong, trong đó 296 người tham gia sống ở Nebraska và Kansas được nhu yếu giao một bức thư cho một người đơn cử sống ở Boston, Massachusetts. Người tham gia phải chọn một người bạn họ biết để chuyền tay bức thư đó và chuyển tiếp cho một người khác. Mỗi bước, lá thư chuyển dời đến gần Boston hơn. Milgram tìm ra rằng, trung bình, chỉ có 5.2 bạn trung gian – 5.2 độ cách biệt .Ngày nay, mỗi tất cả chúng ta là một phần của vô vàn những đồ thị vô hình dung, là gốc của những liên kết xã hội, du lịch, internet và khoa học, kỹ thuật và còn nhiều hơn thế nữa .

5/5 - (1 vote)
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments