Bài 4
Đất nước Dreamland gồm thành phố. Hãng hàng không Starways muốn thiết lập một số chuyến bay một chiều giữa các cặp thành phố sao cho mỗi thành phố có đúng một chuyến bay xuất phát từ nó. Tìm số nguyên dương nhỏ nhất sao cho dù Starways thiết lập các chuyến bay như thế nào, các thành phố luôn có thể được chia thành nhóm sao cho từ một thành phố bất kỳ không thể đến một thành phố khác trong cùng nhóm bằng cách dùng nhiều nhất chuyến bay.
Bước 1 trên 4: Chặn dưới từ chu trình đỉnh
Phân tích chi tiết
Các chuyến bay tạo thành một đồ thị có hướng trên đỉnh, mỗi đỉnh có bậc ra bằng . Nếu chứa một chu trình có hướng độ dài , thì hai thành phố bất kỳ trên chu trình này có thể đến nhau bằng nhiều nhất chuyến bay (đi theo chiều ngắn hơn quanh chu trình đỉnh), nên không hai thành phố nào trong số đó được cùng nhóm. Vì Starways có thể tạo ra cấu hình như vậy, luôn cần ít nhất nhóm, tức .