Ðề: Đề thi HSG QUốc Gia 2009 - môn Tin học
bài số hai là bài lý thuyết đồ thị quá dễ dàng đúng không?
*a là nút xung yếu khi a thuộc đường đi ngắn nhất từ s=>t.
*loại a ra khỏi graph thì không tìm được đường đi từ s=>t.
Giải thuật dễ nhìn thấy nhất là chạy Dijisktra 1 lần
và giải thuật tìm đường đi (BFS,DFS).
Một giải thuật khác là tìm tất cả các đường đi từ s=>t sau đó tìm các nút xung yếu theo định nghĩa là nút xuất hiện trong tất cả các đường này.
(Phải chỉ ra không cần tìm những đường đi có chứa chu trình)
Không biết DH có cao kiến gì khác không.
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
|