Nội Dung Chính
(Trang 83)
Thuật ngữ | Giải thích |
Bài toán người đưa thư (trong Lí thuyết đồ thị) | Bài toán tìm chu trình ngắn nhất đi qua tất cả các cạnh của một đồ thị cho trước |
Bài toán tìm đường đi tối ưu (trong Lí thuyết đồ thị) | Bài toán tìm đường đi từ đỉnh A đến đỉnh L trong một đồ thị có trọng số sao cho tổng các trọng số trên các cạnh của đường đi là nhỏ nhất |
Chu trình | Một đường đi khép kín, tức là đường đi có đầu đường trùng với cuối đường |
Chu trình Euler | Một chu trình đơn giản chứa mọi cạnh của đồ thị |
Chu trình Hamilton | Một chu trình sơ cấp chứa mọi đỉnh của đồ thị |
Đồ thị | Tập hợp hữu hạn các điểm (gọi là các đỉnh của đồ thị) cùng với tập hợp các đoạn đường cong hay thẳng (gọi là cạnh của đồ thị) có đầu mút tại các đỉnh của đồ thị |
Đồ thị có trọng số | Đồ thị liên thông và mỗi cạnh được gắn với một số không âm, gọi là trọng số của cạnh đó |
Đơn đồ thị | Một đồ thị không có khuyên, trong đó hai đỉnh được nối bằng nhiều nhất một cạnh |
Đường đi | Một dãy cạnh nối tiếp, nối hai đỉnh nào đó của đồ thị |
Hai đỉnh kề nhau | Hai đỉnh của đồ thị được nối với nhau bằng một cạnh |
Hai đỉnh liên thông | Hai đỉnh của một đồ thị gọi là liên thông nếu có một đường đi nối chúng. |
Hai hình bằng nhau | Nếu có một phép dời hình, biến hình này thành hình kia. |
Hai hình đồng dạng | Nếu có một phép đồng dạng, biến hình này thành hình kia. |
Bình Luận
Để Lại Bình Luận Của Bạn