Một nhóm gổm 30 bạn học sinh tham gia trò chơi truyển tin. Biết rằng mỗi bạn có thể truyển

Câu hỏi số 662771:

Thông hiểu

Một nhóm gổm 30 bạn học sinh tham gia trò chơi truyển tin. Biết rằng mỗi bạn có thể truyển tin cho ít nhất 15 bạn và nếu bạn A có thể truyển tin cho bạn B, thì bạn B cũng có thể truyền tin cho bạn A. Chứng minh rằng bất kì hai bạn nào trong nhóm cũng có thể truyển tin cho nhau.

Quảng cáo

Xem lời giải

Câu hỏi:662771

Phương pháp giải

Nếu một đồ thị có n đỉnh, mỗi đỉnh có bậc ít nhất bằng n thì nó là đổ thị liên thông.

Giải chi tiết

Ta cho tương ứng mỗi bạn với một đỉnh của một đồ thị gổm 30 đỉnh. Hai bạn có thể truyền tin cho nhau được xem như hai đỉnh tương ứng của đồ thị, được nối với nhau bằng một cạnh. Do mỗi bạn có thể truyền tin cho ít nhất 15 bạn nên mỗi đỉnh của đồ thị có bậc ít nhất là 15 . Theo định lí trên, đồ thị đang xét là liên thông. Vậy hai đỉnh bất kì của đổ thị đểu có một đường đi nối hai đỉnh đó. Điều này chứng tỏ hai bạn bất kì đều có thể truyền tin cho nhau.

Group 2K9 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K9 Chú ý! Lộ Trình Sun 2027 - 1 lộ trình ôn đa kỳ thi (TN THPT, ĐGNL (Hà Nội/ Hồ Chí Minh), ĐGNL Sư Phạm, ĐGTD, ĐGNL Bộ Công an, ĐGNL Bộ Quốc phòngTD - Click xem ngay) tại Tuyensinh247.com. Cập nhật bám sát bộ SGK mới, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.