Trên mặt phẳng, cho một số điểm màu đỏ và một số điểm màu xanh. Người ta nối các điểm khác màu với nhau sao cho hai điều kiện sau được đồng thời thỏa mãn:
1) Mỗi điểm màu đỏ được nối với ít nhất một điểm màu xanh.
2) Mỗi điểm màu xanh được nối với 1 hoặc 2 điểm màu đỏ.
Chứng minh rằng có thể xóa đi không quá một nửa số điểm (trong số các điểm đã cho) sao cho với các điểm còn lại, mỗi điểm màu xanh được nối với đúng một điểm màu đỏ.
I5
Bắt đầu bởi Khong Hoang Thao, 20-01-2007 - 22:20
#1
Đã gửi 20-01-2007 - 22:20
#2
Đã gửi 21-01-2007 - 15:39
Đây alf một tính chất hay của graph lưỡng phân
Gốc của bài này là bài Nga 99 như sau
Trong một lớp học có các học sinh nam và nữ . biết mỗi nam quen tối thiểu một nữ
Cm có thể chọn hơn mọt nửa sô hs của lớp sao cho trong nhóm đó mỗi nam quen một só lẻ nử
Gốc của bài này là bài Nga 99 như sau
Trong một lớp học có các học sinh nam và nữ . biết mỗi nam quen tối thiểu một nữ
Cm có thể chọn hơn mọt nửa sô hs của lớp sao cho trong nhóm đó mỗi nam quen một só lẻ nử
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh