Bài 1776F. Train Splitting trên codeforces

#1

Em nhìn được ý tưởng bài này là: tô màu sao cho:

  1. Nếu giữ một màu thì đồ thị bị rời(unconnected)
  2. Nếu giữ hai màu thì đồ thị liên tục(connected)

Em cũng nhìn được cách đánh màu trong trường hợp đồ thị không đầy đủ, nhưng trường hợp đầy đủ thì em chưa tìm được hướng. Đọc lời giải thì em cũng không hiểu lắm tại sao(chứng minh!?) cách làm của tác giả lại đúng. Em trích lại lời giải ở dưới:

If, on the other hand, the graph is complete, we can paint the edges from one vertex with two different colors(at least one of the edges with first color and at least one of the edges with second color) and all other edges with third color. You can verify that all conditions are satisfied with this coloring.

Giúp em chứng minh phần này với ạ? Theo cách em hiểu: Đúng là nếu dùng chỉ dùng màu 1 hoặc màu 2 thì không thể đi từ A -> B với A, B bất kỳ được vì nếu đi từ A, bằng màu 1 hoặc 2 thì khi đến A’ kề với A thì cũng không đi đến node nào khác mà chỉ có thể quay lại A(vì mỗi đỉnh chỉ có một cạnh màu 1 hoặc màu 2 thôi). Vậy câu hỏi của em là:

  1. Nếu chỉ dùng màu 3, sao đồ thị lại rời?
  2. Nếu giữ hai màu nào đó trong ba thì sao đồ thị lại liên tục?

Em cảm ơn ạ! :blush:

Các đường dẫn có liên quan:

Đề bài

Lời giải(trang 11)

1 Like
#2

Để chứng minh các phần của lời giải, ta cần xem xét các trường hợp:

  1. Nếu chỉ dùng màu 3 (có nghĩa là không có cạnh nào được sơn màu 1 hoặc màu 2):
  • Giả sử có một đỉnh A. Vì không có cạnh nào kề với A sơn màu 1 hoặc màu 2, nên từ A không thể đi đến bất kỳ đỉnh nào khác. Điều này có nghĩa là đồ thị sẽ rời rạc.
  • Vậy nếu chỉ dùng màu 3, đồ thị sẽ rời rạc.
  1. Nếu giữ hai màu nào đó trong ba thì đồ thị lại liên thông (connected):
  • Giả sử chọn hai màu là màu 1 và màu 2.
  • Gán một cạnh bất kỳ bằng màu 1 và đi từ đỉnh A đến đỉnh B (không mất tổng quát tính chất).
  • Gán cạnh nối từ A đến các đỉnh kề của B bằng màu 2.
  • Lặp lại quá trình trên cho tất cả các cạnh chưa được sơn.
  • Ta sẽ có đồ thị liên thông vì từ mỗi đỉnh đều có đường đi đến đỉnh khác (theo cách này, chúng ta đã đảm bảo mỗi đỉnh có ít nhất một cạnh sơn màu 1 và ít nhất một cạnh sơn màu 2).

Với hai trường hợp trên, lời giải đều chứng minh chính xác và đảm bảo đồ thị được sơn bằng ba màu một cách hợp lý và thỏa mãn yêu cầu của bài toán.

#3

Em đã đặt câu hỏi trên maths exchange. Hướng tiếp cận bằng phản chứng này cũng khá ổn

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?