Đồ thị và đường đi
Hòn đảo và cây cầu, ngôi nhà và con đường, người và quan hệ quen biết: tất cả đều vẽ được thành các điểm và các đường nối giữa chúng. Hình như vậy gọi là đồ thị. Khoảng 6,6% số câu trong đề Tin học trẻ Bảng M1, M2 năm 2025-2026 là bài đồ thị: đi qua mỗi cây cầu một lần, tìm đường ngắn nhất, đếm số đường đi, tô màu bản đồ. Mỗi dạng có một cách làm riêng, nắm được là giải nhanh.
Dạng 1. Điểm, đường nối và bậc
Phần tiêu đề “Dạng 1. Điểm, đường nối và bậc”
Số đường nối đi ra từ một điểm gọi là bậc của điểm đó. Ở hình trên:
| Điểm | A | B | C | D |
|---|---|---|---|---|
| Bậc | 2 | 2 | 3 | 1 |
Cộng các bậc: 2 + 2 + 3 + 1 = 8. Hình có 4 đường nối, đúng bằng 8 : 2 = 4. Mỗi đường nối có hai đầu, nên được đếm hai lần:
Tổng các bậc = 2 × số đường nối.
Lưu ý: vì tổng các bậc luôn là số chẵn, số điểm có bậc lẻ cũng luôn là số chẵn (0, 2, 4, …). Ở hình trên có 2 điểm bậc lẻ là C và D.
Dạng 2. Vẽ một nét, đi qua mỗi cây cầu một lần
Phần tiêu đề “Dạng 2. Vẽ một nét, đi qua mỗi cây cầu một lần”Vẽ một hình mà không nhấc bút, không vẽ lại đoạn nào, cũng giống đi qua mỗi cây cầu đúng một lần. Mỗi lần bút đi ngang qua một điểm thì dùng 2 đường (một vào, một ra). Vì thế:
| Số điểm bậc lẻ | Kết luận |
|---|---|
| 0 | Vẽ được, bắt đầu ở đâu cũng được và kết thúc đúng chỗ bắt đầu |
| 2 | Vẽ được, phải bắt đầu ở một điểm lẻ và kết thúc ở điểm lẻ còn lại |
| 4, 6, … | Không vẽ được |
Hình ở dạng 1 có 2 điểm lẻ (C và D), nên vẽ được một nét: bắt đầu ở D, đi D, C, A, B, C.
Lưu ý: hình phải liền một khối (không có phần tách rời). Khi một hình không vẽ được, mỗi đoạn vẽ thêm (hoặc đi lại) nối hai điểm lẻ sẽ làm giảm 2 điểm lẻ.
Dạng 3. Đường đi ngắn nhất
Phần tiêu đề “Dạng 3. Đường đi ngắn nhất”Số trên mỗi đường là độ dài (hoặc thời gian). Tìm đường ngắn nhất từ S đến T:
Đi từ S ra xa dần, ghi ở mỗi điểm độ dài ngắn nhất để đến điểm đó:
| Điểm | Cách đến ngắn nhất | Độ dài |
|---|---|---|
| S | xuất phát | 0 |
| A | S đến A | 1 |
| B | qua A (đi thẳng từ S thì mất 4) | 1 + 2 = 3 |
| T | qua B (từ A thì mất 1 + 6 = 7) | 3 + 3 = 6 |
Đường ngắn nhất là S, A, B, T, dài 6.
Lưu ý: đường đi thẳng chưa chắc ngắn nhất. Ở mỗi điểm phải so sánh tất cả các đường đến nó.
Dạng 4. Ít bước nhất: đánh số loang dần
Phần tiêu đề “Dạng 4. Ít bước nhất: đánh số loang dần”Trong mê cung hay trên bàn cờ, mỗi bước đi dài như nhau. Ghi 0 vào ô xuất phát, ghi 1 vào các ô đi được sau 1 bước, ghi 2 vào các ô chưa ghi số mà đi được từ ô số 1, cứ thế loang dần như vết mực:
Số ghi ở mỗi ô là số bước ít nhất để đến ô đó. Muốn tìm lại đường đi, đi ngược từ ô đích về các ô có số nhỏ hơn 1.
Lưu ý: quân mã đi hình chữ L luôn đổi màu ô (đen sang trắng, trắng sang đen). Nên muốn đến một ô khác màu thì số nước phải lẻ, đến ô cùng màu thì số nước phải chẵn.
Dạng 5. Đếm số đường đi
Phần tiêu đề “Dạng 5. Đếm số đường đi”Trên lưới đường phố, chỉ đi sang phải hoặc xuống dưới. Mỗi giao lộ đến được từ giao lộ bên trái hoặc giao lộ bên trên, nên số đường đến một giao lộ bằng tổng hai số đó:
Từ A đến B có 6 đường. Cách cộng dồn này dùng được cho mọi hình mà đường đi chỉ theo một chiều (cầu một chiều, mũi tên): số của một điểm bằng tổng số của các điểm có đường đi vào nó.
Lưu ý: giao lộ bị cấm thì ghi 0. Nếu bắt buộc đi qua điểm X thì đếm hai chặng (đến X, rồi từ X) và nhân hai kết quả.
Dạng 6. Tô màu
Phần tiêu đề “Dạng 6. Tô màu”Tô các vùng của bản đồ sao cho hai vùng có chung đường biên thì khác màu. Muốn biết cần ít nhất bao nhiêu màu:
- Tìm nhóm vùng đôi một chung biên. Ba vùng đôi một chung biên thì cần ít nhất 3 màu.
- Chỉ ra một cách tô cụ thể với đúng số màu đó.
Muốn đếm số cách tô, tô lần lượt từng vùng (bắt đầu từ vùng chung biên với nhiều vùng nhất) và nhân số màu còn được chọn. Ví dụ 3 vùng xếp thành hàng, vùng giữa chung biên với hai vùng hai bên, có 3 màu: vùng giữa 3 cách, mỗi vùng bên 2 cách, tất cả 3 × 2 × 2 = 12 cách.
Lưu ý: hai vùng chỉ chạm nhau ở một điểm không tính là chung biên. Nhiều bài không nói đến bản đồ (xếp lịch thi, chia nhóm, xếp chuồng thú) nhưng cách giải giống hệt: mỗi thứ là một vùng, hai thứ không được ở cùng nhóm thì coi như chung biên.
Dạng 7. Nối mạng với chi phí ít nhất
Phần tiêu đề “Dạng 7. Nối mạng với chi phí ít nhất”Cần nối tất cả các điểm (đảo, nhà, máy tính) sao cho đi được giữa hai điểm bất kỳ, với tổng chi phí ít nhất:
Xét các đường từ rẻ đến đắt. Đường nào nối thêm được điểm chưa liên lạc được thì chọn, đường nào chỉ tạo vòng kín thì bỏ:
- B-C (1): chọn. D-A (2): chọn. A-B (3): chọn, giờ cả 4 điểm đã liên lạc được.
- C-D (4) và A-C (5): bỏ, vì chỉ tạo vòng kín.
Tổng chi phí 1 + 2 + 3 = 6.
Lưu ý: nối n điểm luôn cần đúng n − 1 đường. Có 4 điểm thì chọn đủ 3 đường là dừng.
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 20 bài, chia thành 5 nhóm từ dễ đến khó. Nhãn M1 là mức đề tiểu học, M2 là mức đề THCS. Mỗi bài có đáp số để các bạn tự kiểm tra sau khi làm.
Nhóm 1. Đỉnh, cạnh và bậc
Phần tiêu đề “Nhóm 1. Đỉnh, cạnh và bậc”Bài 1. Ai quen nhiều bạn nhất? (M1)
Phần tiêu đề “Bài 1. Ai quen nhiều bạn nhất? (M1)”Sáu bạn An (A), Bình (B), Cường (C), Dũng (D), Hà (H), Lan (L). Hai bạn quen nhau thì được nối bằng một đoạn thẳng.
Có bao nhiêu cặp bạn quen nhau? Bạn nào quen nhiều bạn nhất?
Bài 2. Đếm cặp từ số bạn quen (M1)
Phần tiêu đề “Bài 2. Đếm cặp từ số bạn quen (M1)”Trong nhóm 5 bạn, mỗi bạn kể mình quen bao nhiêu bạn khác trong nhóm. Các bạn kể lần lượt: 4, 3, 3, 2, 2. Trong nhóm có bao nhiêu cặp bạn quen nhau?
Bài 3. Mỗi điểm nối đúng 3 điểm (M2)
Phần tiêu đề “Bài 3. Mỗi điểm nối đúng 3 điểm (M2)”Cho 8 điểm. Người ta nối chúng bằng các đoạn thẳng sao cho mỗi điểm được nối với đúng 3 điểm khác (hai điểm nối với nhau nhiều nhất một đoạn). Có tất cả bao nhiêu đoạn thẳng?
Nhóm 2. Vẽ một nét, đi qua mỗi đường đúng một lần
Phần tiêu đề “Nhóm 2. Vẽ một nét, đi qua mỗi đường đúng một lần”Bài 4. Hình nào vẽ được một nét? (M1)
Phần tiêu đề “Bài 4. Hình nào vẽ được một nét? (M1)”Hình nào dưới đây vẽ được bằng một nét: không nhấc bút và không vẽ lại đoạn nào đã vẽ? (Các đường chéo cắt nhau ở giữa hình vuông không phải là điểm nối, bút được đi thẳng qua.)
Bài 5. Đi qua mỗi cây cầu một lần (M1)
Phần tiêu đề “Bài 5. Đi qua mỗi cây cầu một lần (M1)”Vương quốc có 5 hòn đảo A, B, C, D, E, mỗi đoạn nối là một cây cầu.
Rô-bốt muốn đi qua mỗi cây cầu đúng một lần. Rô-bốt phải xuất phát từ đảo nào?
Bài 6. Con kiến trên tháp que (M2)
Phần tiêu đề “Bài 6. Con kiến trên tháp que (M2)”Tuấn dùng 10 que gỗ làm một cái tháp: đáy là hình ngũ giác (5 que), đỉnh tháp nối với cả 5 góc của đáy (5 que). Con kiến muốn bò dọc theo mỗi que đúng một lần. Hiện nay kiến không làm được. Tuấn cần gắn thêm ít nhất bao nhiêu que (mỗi que nối hai điểm đã có) để kiến làm được?
Bài 7. Rô-bốt kiểm tra đường phố (M2)
Phần tiêu đề “Bài 7. Rô-bốt kiểm tra đường phố (M2)”Khu phố có các con đường như hình: 3 khối nhà theo chiều ngang, 2 khối theo chiều dọc, mỗi cạnh khối nhà dài 100 m. Rô-bốt xuất phát ở A, phải đi qua mọi đoạn đường ít nhất một lần rồi quay về A. Quãng đường ngắn nhất rô-bốt phải đi là bao nhiêu mét?
Nhóm 3. Đường đi ngắn nhất, ít bước nhất
Phần tiêu đề “Nhóm 3. Đường đi ngắn nhất, ít bước nhất”Bài 8. Đường nhanh nhất đến trường (M1)
Phần tiêu đề “Bài 8. Đường nhanh nhất đến trường (M1)”Hình dưới cho các con đường từ nhà (N) đến trường (T), số trên mỗi đường là số phút đi hết đường đó. Đi nhanh nhất thì mất bao nhiêu phút?
Bài 9. Nhặt ba món đồ chơi (M1)
Phần tiêu đề “Bài 9. Nhặt ba món đồ chơi (M1)”Rô-bốt đứng ở R, trên sàn có ba món đồ chơi X, Y, Z. Số trên mỗi đoạn là khoảng cách (mét), hình vẽ không đúng tỉ lệ. Rô-bốt đi nhặt cả ba món theo thứ tự tùy chọn, mỗi lần đi thẳng từ chỗ này đến chỗ kia, nhặt xong món cuối thì dừng. Quãng đường ngắn nhất là bao nhiêu mét?
Bài 10. Ra khỏi mê cung (M1)
Phần tiêu đề “Bài 10. Ra khỏi mê cung (M1)”Mê cung 5 × 5 ô, các nét đậm là tường. Mỗi bước, bạn Sóc đi sang một ô kề cạnh nếu giữa hai ô không có tường. Sóc đi từ ô S đến ô Đ ít nhất bao nhiêu bước?
Bài 11. Quân mã sang ô bên cạnh (M2)
Phần tiêu đề “Bài 11. Quân mã sang ô bên cạnh (M2)”Quân mã trên bàn cờ đi theo hình chữ L: mỗi nước đi 2 ô theo một hướng rồi 1 ô theo hướng vuông góc. Trên bàn cờ 5 × 5, quân mã đứng ở ô góc dưới bên trái. Cần ít nhất bao nhiêu nước để quân mã đến ô ngay bên phải nó?
Nhóm 4. Đếm số đường đi
Phần tiêu đề “Nhóm 4. Đếm số đường đi”Bài 12. Đường đi trên lưới phố (M1)
Phần tiêu đề “Bài 12. Đường đi trên lưới phố (M1)”Bạn Bi đi từ A đến B trên lưới đường phố dưới đây, mỗi bước chỉ đi sang phải hoặc xuống dưới. Có bao nhiêu đường đi khác nhau?
Bài 13. Giao lộ bị chặn (M1)
Phần tiêu đề “Bài 13. Giao lộ bị chặn (M1)”Lưới đường phố 3 × 3 khối nhà. Giao lộ có dấu X đỏ đang sửa, không được đi qua. Đi từ A đến B, mỗi bước chỉ sang phải hoặc xuống dưới. Có bao nhiêu đường đi?
Bài 14. Cầu một chiều (M2)
Phần tiêu đề “Bài 14. Cầu một chiều (M2)”Các đảo A, B, C, D, E, F nối với nhau bằng những cây cầu một chiều (chỉ đi theo hướng mũi tên). Có bao nhiêu cách đi từ A đến F?
Bài 15. Bắt buộc đi qua giao lộ X (M2)
Phần tiêu đề “Bài 15. Bắt buộc đi qua giao lộ X (M2)”Lưới đường phố 4 × 4 khối nhà. Đi từ A đến B, mỗi bước chỉ sang phải hoặc xuống dưới, và phải đi qua giao lộ X ở chính giữa. Có bao nhiêu đường đi?
Nhóm 5. Tô màu và nối mạng
Phần tiêu đề “Nhóm 5. Tô màu và nối mạng”Bài 16. Tô màu bản đồ (M1)
Phần tiêu đề “Bài 16. Tô màu bản đồ (M1)”Bản đồ dưới đây có 4 vùng A, B, C, D. Lan tô mỗi vùng một màu sao cho hai vùng có chung đường biên thì khác màu. Lan cần ít nhất bao nhiêu màu?
Bài 17. Vùng giữa và vòng ngoài (M2)
Phần tiêu đề “Bài 17. Vùng giữa và vòng ngoài (M2)”Bản đồ 5 × 5 ô có vùng O ở giữa và 5 vùng A, B, C, D, E bao quanh. Tô màu sao cho hai vùng có chung đường biên thì khác màu. Cần ít nhất bao nhiêu màu?
Bài 18. Đếm cách tô màu (M2)
Phần tiêu đề “Bài 18. Đếm cách tô màu (M2)”Dùng lại bản đồ 4 vùng A, B, C, D ở bài 16. Lan có 4 màu và tô mỗi vùng một màu sao cho hai vùng có chung đường biên thì khác màu (không bắt buộc dùng hết 4 màu). Có bao nhiêu cách tô?
Bài 19. Xây cầu nối các đảo (M1)
Phần tiêu đề “Bài 19. Xây cầu nối các đảo (M1)”Quốc vương muốn xây cầu nối 5 hòn đảo A, B, C, D, E sao cho từ đảo nào cũng đi được đến mọi đảo khác (có thể đi qua đảo trung gian). Số trên mỗi đoạn là chi phí xây cây cầu đó (tỷ đồng). Tổng chi phí ít nhất là bao nhiêu?
Bài 20. Xếp lịch thi (M2)
Phần tiêu đề “Bài 20. Xếp lịch thi (M2)”Trường xếp lịch thi 6 môn: Toán, Văn, Anh, Lý, Hóa, Sinh. Hai môn có chung học sinh dự thi thì không được thi cùng buổi. Các cặp môn có chung học sinh là: Toán và Văn, Toán và Anh, Văn và Anh, Toán và Lý, Lý và Hóa, Hóa và Sinh, Anh và Sinh, Văn và Hóa. Mỗi buổi thi được nhiều môn. Cần ít nhất bao nhiêu buổi thi?
© 2026 Bumbii Academy. Toàn bộ nội dung thuộc bản quyền của Bumbii Academy, nghiêm cấm sao chép dưới mọi hình thức khi chưa được cho phép.