Dạng toán: Lý thuyết Đồ thị cơ bản, Tìm đường đi ngắn nhất & Cây khung
Biểu diễn các địa điểm là Đỉnh (Nodes) và các con đường là Cạnh (Edges); cộng trọng số theo từng chặng từ điểm đầu để tìm đường ngắn nhất.
- 🤖 Tư duy Thuật toán & Ngôn ngữ Toán-Anh
- Lý thuyết Đồ thị, Cây khung & Tìm đường (Bebras)
- Lớp 1 – Lớp 12
- 76 câu luyện tập
Cách giải dạng Lý thuyết Đồ thị cơ bản, Tìm đường đi ngắn nhất & Cây khung
Tên tiếng Anh: Graph Theory, Shortest Path & Spanning Trees (Bebras)
- Ghi chi phí nhỏ nhất để đi tới từng đỉnh trung gian theo thứ tự từ điểm xuất phát.
- Để nối N đỉnh với tổng chi phí nhỏ nhất (Cây khung nhỏ nhất), chọn lần lượt (N - 1) cạnh ngắn nhất mà không tạo chu trình khép kín.
📐 Công thức / quy tắc: Cây khung nối N đỉnh luôn có đúng (N - 1) cạnh ; Định lý Euler: ∑ bậc các đỉnh = 2 × Số cạnh
⚠️ Bẫy thường gặp: Chọn cạnh ngắn nhưng tạo thành vòng khép kín thừa thãi hoặc đi qua đỉnh bị cấm.
Con có đang yếu dạng này không?
Trên LuyệnToán.net, mỗi câu dạng “Lý thuyết Đồ thị cơ bản, Tìm đường đi ngắn nhất & Cây khung” con làm đều được ghi nhận vào độ thành thạo của dạng. Nếu con sai lặp lại, dạng này được đánh dấu cần luyện bù và hệ thống gợi ý 10 câu từ dễ đến khó — thứ kho PDF không làm được.
Xuất hiện trong các kỳ thi
Dạng toán liên quan
Cho con làm thử ngay — miễn phí
Làm thử 5 câu không cần đăng ký. Tạo tài khoản để con làm 2 đề vòng loại miễn phí, có chấm điểm, lời giải và Sổ tay từ khoá.
từ 99.000đ149.000đ · dùng 1 năm cho mỗi bé · xem bảng giá