Đồ thị và mạng lưới
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| graph/ɡræf/ | đồ thị |
| vertices/ˈvɜːtɪsiːz/ | đỉnh |
| edges/ˈedʒɪz/ | cạnh |
| degree/dɪˈɡriː/ | bậc |
| path/pæθ/ | đường đi |
| cycle/ˈsaɪkl/ | chu trình |
| connected/kəˈnektɪd/ | liên thông |
| tree/triː/ | cây |
| weighted graph/ˈweɪtɪd ɡræf/ | đ đồ thị có trọng số |
| shortest path/ˈʃɔːtɪst pæθ/ | đường đi ngắn nhất |
Mô hình kết nối cần các giả định
- Một đồ thị có đỉnh và cạnh. Xác định chúng đại diện cho cái gì và liệu các kết nối có có hướng, có trọng số hay không.
- Một đồ thị có đỉnh và cạnh. Hãy quyết định chúng đại diện cho cái gì và liệu các kết nối có có hướng, có trọng số hay vô hướng.
Đếm kết nối một cách nhất quán
- Bậc đếm số cạnh kề trong đồ thị đơn không hướng. Tổng bậc bằng hai lần số cạnh, do đó nó phải là số chẵn.
- Bậc đếm số cạnh incident trong đồ thị vô hướng đơn giản. Tổng bậc bằng hai lần số cạnh, vì vậy nó phải là số chẵn.
Trong một đồ thị vô hướng đơn giản không có loop, bốn cạnh gặp một đỉnh. Bậc của nó là gì?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Bậc của nó là 4, số lượng cạnh incident dưới quy ước đồ thị được nêu.
Một cây cần hai tính chất
- Một cây là liên thông và không có chu trình. Một cây hữu hạn với n đỉnh có n trừ 1 cạnh.
- Một cây là liên thông và không có chu kỳ. Một cây hữu hạn với n đỉnh có n trừ 1 cạnh.
Một cây có 4 đỉnh. Nó có bao nhiêu cạnh?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Một cây hữu hạn có bốn đỉnh có n − 1 = 3 cạnh. Số lượng này phụ thuộc vào việc đồ thị thực sự là liên thông và không có chu trình.
Trong một mạng không định hướng có trọng số cạnh dương, tại sao một đồ con liên thông có chi phí nhỏ nhất bao phủ tất cả các đỉnh lại không chứa chu trình?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Việc loại bỏ bất kỳ cạnh nào thuộc chu trình vẫn giữ nguyên tính liên thông và làm giảm tổng chi phí vì trọng số của nó là dương. Do đó, một đồ con có chu trình không thể là tối ưu dưới những giả thiết này.
Các con đường nối có chi phí dương. Đối với mạng lưới liên thông với chi phí đường đi strictly positive, việc loại bỏ một cạnh chu trình sẽ giữ nguyên tính liên thông và giảm chi phí. Do đó, một cận dưới của chi phí tối thiểu là một cây. Để tìm cây bao trùm nhỏ nhất, hãy chọn các cạnh nối tất cả các đỉnh mà không tạo thành chu trình; việc chọn bừa bãi n trừ 1 cạnh rẻ nhất nhất có thể để lại các thành phần tách biệt.
Một tuyến đường ngắn nhất không phải là cây bao phủ
- Một đồ thị có trọng số gán một giá trị xác định cho mỗi cạnh. Đường đi ngắn nhất tối thiểu hóa trọng số tuyến đường giữa các điểm đầu cuối đã cho.
- Một đồ thị có trọng số gắn một giá trị chỉ định cho mỗi cạnh. Đường đi ngắn nhất tối thiểu hóa trọng số tuyến đường giữa các điểm đầu cuối đã cho.
Nối mỗi tình huống với các đỉnh và cạnh của nó nên là gì.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Quyết định các đỉnh đại diện cho cái gì là bước mô hình hóa, và đó là nơi điểm số nằm.
Cạnh đóng làm thay đổi tính khả thi. Trang 4.5 tìm thấy một tuyến đường có trọng số 7, sau đó đóng một cạnh và kiểm tra phương án thay thế có trọng số 9. Đừng sử dụng lại tổng cũ cho một đường đi không còn tồn tại nữa.
Hai bản vẽ trông khác nhau phải là hai đồ thị khác nhau.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Các bố trí khác nhau có thể có cùng ma trận kề được gán nhãn. Hãy so sánh cả hướng và trọng số khi chúng là một phần của đồ đã cho.
So sánh tất cả các cấu trúc liên quan đến câu hỏi: tương ứng đỉnh, kề nhau, hướng đi và trọng số (nếu có). Những hình vẽ trông giống nhau chưa chắc đại diện cho cùng một đồ thị; các bố cục khác nhau vẫn có thể biểu diễn các kết nối được gắn nhãn như nhau.