Bài thu hoạch lý thuyết đồ thị môn Toán rời rạc | Đại học Kinh tế Quốc Dân

lOMoAR cPSD| 58569740
BÀI THU HOẠCH LÝ THUYẾT ĐỒ THỊ I. F
- Từ xưa thành phố Konigsberg có 1 dòng sông và 7 cây cầu, người dân
thành phố luôn đặt câu hỏi rằng làm sao để từ nhà của mình tham
quan 7 cây cầu mà mỗi lần chỉ đi qua một cây cầu ? Tuy vậy Euler đã
chứng minh rằng điều đó là không thể.
- Qua đó, Euler đã vô tình chứng minh một phát biểu rằng: “Có một
đường đi qua mỗi cạnh đúng một lần khi và chỉ khi mỗi đỉnh có đúng CHẴN cạnh. II. Đồ thị
- Ví dụ: Đồ thị mạng lưới các đường bay:
• Các đỉnh là các thành phố
• Các cạnh là các chuyến bay giữa hai thành phố
- Ví dụ 2: Đồ thị Facebook:
• Mỗi đỉnh là một trang cá nhân
• Hai đỉnh nối với nhau nếu là Friend (bạn) của nhau
- Ví dụ 3: Đồ thị đồng tác giả bài báo:
• Mỗi đỉnh là một nhà khoa học
• Hai đỉnh nối với nhau nếu hai nhà khoa học viết chung bài báo
1. Đồ thị và khoa học công nghệ hiện đại:
- Đồ thị của các mạng xã hội là cực kì lớn:
• Hàng tram nghìn đến triệu, hàng tỷ đỉnh
• Thay đổi liên tục: mỗi giây có hàng tram đỉnh mới, hàng ngàn cạnh mới
• Đồ thị rất khó đoán, các cạnh lung tung lOMoAR cPSD| 58569740 III. Số EDROS
- Khoảng cách Erdos được định nghĩa cho đồ thị Đồng tác giả: hai nhà
khoa học cùng viết một bài báo chung thì họ được nối với nhau • Erdos có số là 0
• A có bài báo chung với Erdos thì có số Erdos là 1
• Nếu B không có bài chung với Erdos nhưng có bài chung với A thì số Erdos của B là 2
- Cứ như vậy, số Erdos càng nhỏ thì càng gắn bó với các công trình của
Erdos. Và tất nhiên người ta sẽ rất tự hào nếu có khoảng cách là 1 hay 2
- Trong số các nhà khoa học được giải Fields, không ai có số 1, mà chỉ
có số 2. Nhưng Lovas, người
được giải thưởng Abel, có số 1 IV.
Định luật thế giới nhỏ
- Trong rất nhiều các mạng xã hội, các đồ thị siêu lớn, thì khoảng cách
giữa hai đỉnh bình thường nhỏ hơn 6.
Ý nghĩa: Chỉ cần qua 6 bước thôi, là hai con người xa lạ có thể đến được với nhau. V.
Lovász và bước đi ngẫu nhiên
- Định lý: Xét bước đi ngẫu nhiên trên đồ thị vô hướng, có một phân
phối ổn định duy nhất: phân phối của các đỉnh tỷ lệ thuận với bậc của nó.
Ý nghĩa: Các ông già Noel đi phát cho mỗi ngôi nhà một túi quà, cứ đi
đi mãi một cách ngẫu nhiên, thì số quà mỗi bé nhận được sẽ tỉ lệ
thuận với số đoạn đường trực tiếp dẫn đến ngôi nhà của bé. lOMoAR cPSD| 58569740 VI.
Tìm dường đi ngắn nhất
- Bùng nổ các thuật toán tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị:
• Thuật toán kinh điển: Dijkstra
• Tìm đường đi với thời gian O(n logn + m logn)
• Nếu đồ thị có 100 đỉnh, 3000 cạnh thì mất khoảng hàng chục nghìn bước
• Nếu đồ thị có tỷ đỉnh, tram cạnh thì mất khoảng hàng nghìn tỷ bước
• Tìm đường đi ngắn nhất chính xác là mất nhiều thời gian VII.
Sáu bước trung gian