bài tập lý thuyết đồ thị

[canhocthem]

chà mình có máy bài toán bên phần lý thuyết đồ thị đang bị bí mong các bạn chỉ giáo cho
1) Một lớp có 60 sv,trong đó mỗi sv có ít nhất 30 email của các sv còn lại.
Chứng minh rằng bất cứ 2 sv trong lờp đều liên lạc với nhau
2) Trong cộc liên hoan mọi người bắt tay nhau.Hãy chứng minh tổng số lượt người bắt tay là một số chẵn.Giả sử không ai tự bắt tay mình
Mong các bạn giúp đỡ minh nha.Chỉ cần gợi ý cho mình thui.
Cảm ơn nhiều

[Tarzan]

Câu 2 vô cùng đơn giản.
Giả sử A bắt tay B thì B cũng bắt tay A, như vậy nếu tồn tại 1 cái bắt tay t1 giữa A và B thì luôn tồn tại 1 bắt tay t1* giữa B và A.

Như thế chưa chặt chẽ để chứng minh số bắt tay là số chẵn . Bác nào tiếp đi.

[Tarzan]

Câu 1 :

Giả sử tồn tại 1 người A không liên lạc được với 1 người B nào đó.

Ta gọi tập {B1, B2, ..., B30} là những người mà liên lạc được với người B.

Như vậy, người A không liên lạc được với {B1, B2, ... B30} (vì nếu liên lạc được thì đã liên lạc được với B)

Ta có tiếp, người A không liên lạc được với {B, B1, B2, ... B30}. Như vậy người A không liên lạc được với 31 người.

Giả sử người A có khả năng liên lạc được với tất cả những người còn lại, cũng chỉ được 60 - 31 - 1 = 28. Trái với giả thiết.

Điều còn lại dàng cho chủ topic.

[rox_rook]

Cả 2 bài chẳng có liên quan 1 chút gì đến 2 từ "Đồ thị", thầy cô nào bảo bạn 2 bài này thuộc lý thuyết đồ thị vậy ?
- Dùng xác xuất, tổ hợp, tập hợp CM kiểu nào cũng xong.
- Dùng phản chứng cũng được.
ps : tự suy nghĩ, cả 2 bài đều quá cơ bản.

[Tarzan]

có liên quan đến đồ thị đó chứ. Tớ viết lại đề bài nhé.

Bài 1:

Cho một đồ thị có hướng, gồm 60 đỉnh. Mỗi đỉnh có thể đi đến chính xác 30 đỉnh khác.
Chứng minh rằng đồ thị là liên thông toàn phần.

Bài 2:
Chứng minh rằng khi một đồ thị vô hướng sang đồ thị có hướng thì số cạnh của đồ thị có hướng là chẵn.

[diepcothanh]

Quá hay!!! không nghề từ Toán học dịch sang lý thuyết đồ thị lại hay vậy.
Chắc mình đổi ý chuyển nghành thuj.Theo lập trình thui.
Bạn còn bà nào hay kjeu này nữa hok?
pót lên anh em tranh luận chơi