Các nhận xét về bậc của đỉnh trong đồ thị cũng cho ta nhiều quan sát thú vị trong thực tế.
Trước tiên, ta có nhận xét sau.
Nhận xét 1. Trong đơn đồ thị G
có n đỉnh (n lớn hơn bằng 2), luôn tồn tại hai đỉnh có cùng bậc.
Để giải bài toán
này, ta sẽ dùng đến nguyên tắc Dirichlet. Cụ thể như sau.
Chứng minh.
Ta có nhận xét rằng bậc của một đỉnh bất kỳ trong đồ thị là số nguyên từ 0 đến n
– 1. Rõ ràng trong đồ thị, nếu tồn tại một đỉnh có bậc n – 1 (đỉnh
này được nối với tất cả các đỉnh còn lại) thì sẽ không tồn tại đỉnh có bậc 0 (đỉnh
cô lập). Do đó, các đỉnh của đồ thị chỉ có thể nhận n – 1 bậc từ 0 đến n
– 2 hoặc từ 1 đến n – 1. Theo nguyên tắc Dirichlet, trong n đỉnh
này phải có hai đỉnh cùng bậc.
Từ nhận xét này, ta có thể rút ra một số
kết quả trong thực tế như sau
Kết quả 1. Trong một buổi tiệc, luôn
tồn tại hai người có cùng số người quen.
Kết quả 2.
Trong một giải đấu bóng đá, mỗi đội phải thi đấu với các đội khác một lần. Khi
đó, tại mọi thời điểm luôn tồn tại hai đội có cùng số trận đã đấu.
Sử dụng nhận xét 1, ta có thể suy ra nhận xét sau
Nhận xét 2.
Trong đơn đồ thị G có n đỉnh (n lớn hơn hay bằng
3), nếu có đúng hai đỉnh có cùng bậc thì phải có đúng một đỉnh có bậc n – 1
hoặc đúng một đỉnh cô lập.
Chứng minh.
Nếu G có hai đỉnh cô lập thì bằng cách bỏ hai đỉnh này đi, đồ thị mới còn lại n – 2 đỉnh, và các đỉnh này không có đỉnh nào cùng bậc, mâu thuẫn với bài toán 1.
Nếu G có hai đỉnh bậc n – 1 thì ta xét đồ thị G' xác định như sau: đồ thị gồm n đỉnh và nếu hai đỉnh A và B là hai đỉnh kề thì trong G', ta xóa cạnh nối hai đỉnh này đi. Đồ thị G' thu được sẽ có hai đỉnh cô lập là hai đỉnh bậc n – 1 trong đồ thị G, vô lý.
Vậy G không thể có hai đỉnh cô lập hoặc hai đỉnh bậc n – 1. Theo bài toán 1, đồ thị phải có đúng một đỉnh cô lập hoặc một đỉnh bậc n – 1.
Theo em, từ nhận xét 2 này, ta có thể rút ra những kết quả thực tế như nhận xét 1 không? Em hãy để lại bình luận bên dưới nhé.
Không có nhận xét nào:
Đăng nhận xét