Chủ đề này có 3 trả lời

[huynhht]

Cuộc họp có ít nhất ba người. Mỗi đại biểu đến dự họp đều bắt tay ít nhất một nửa số đại biểu có mặt. Chứng minh rằng luôn luôn có thể xếp tất cả các đại biểu ngồi xung quanh một bàn tròn, để mỗi người ngồi giữa hai người, mà đại biểu này đã bắt tay.

[ducvipdh12]

Cuộc họp có ít nhất ba người. Mỗi đại biểu đến dự họp đều bắt tay ít nhất một nửa số đại biểu có mặt. Chứng minh rằng luôn luôn có thể xếp tất cả các đại biểu ngồi xung quanh một bàn tròn, để mỗi người ngồi giữa hai người, mà đại biểu này đã bắt tay.

Ta có thể biểu diễn mối quan hệ của các đại biểu đến tham dự bằng đơn đồ thị $G=(V,E)$

$G$ có $n$ đỉnh ( $n\geq 3$, $n$ là số đại biểu ) và $e$ cạnh

Mỗi đỉnh của đồ thị ứng với 1 đại biểu,giữa 2 đỉnh ứng với 2 đại biểu quen biết nhau tồn tại 1 cạnh

Gọi $V_i(i=1,2,...,n)$: đỉnh của đồ thị ( ứng với 1 đại biểu )

Do mỗi người quen ít nhất 2 đại biểu khác nên:

$deg(V_i)\geq 2$

$\Rightarrow \sum_{i=1}^{n}deg(V_i)\geq 2n$

Nên số cạnh của đồ thị: $e\geq n$ (1)

Mặt khác theo đề ra ta có các đại biểu ngồi xung quanh 1 bàn tròn.

Vì vậy , đồ thị biểu diễn cách sắp xếp chỗ ngồi của các đại biểu thỏa mãn là đồ thị vòng $C_n$

Trong đồ thị $C_n$ có $n$ cạnh, $n$ cạnh này được lấy từ $e$ cạnh của $G$ ( do nó biểu thị mối quan hệ giữa các đại biểu ) (2)

Tập đỉnh của $G$ và $C_n$ bằng nhau và bằng $n$ (3)

Từ (1),(2),(3) cho thấy, $C_n$ là đồ thị con bao hàm của $G$ ( $C_n$ được tạo ra bằng cách bỏ đi 1 số cạnh của $G$ )

Vậy từ đó ta có dpcm

P/s: bài tóan này nghiên cứu sâu vào lý thuyết đồ thị, phù hợp hơn với box Đại Học hơn

[Bui Ba Anh]

Thực ra đây là áp dụng trực tiếp của định lý Dirac
Xét đơn đồ thị vô hướng $G=(V,E)$
Trong đó $V$ biểu diễn các thành viên, $E$ biểu diễn tập bắt tay
Do bậc mỗi đỉnh không bé hơn $\frac{a}{2}$ nên $G$ là đồ thị Hamiton . Do đó có vết Hamiton (đpcm)

------------------

@ducvipdh12: 2 cách tựa như nhau mà em

Bài viết đã được chỉnh sửa nội dung bởi ducvipdh12: 05-06-2015 - 22:44

[Belphegor Varia]

Anh có thể nói rõ hơn về Dirac được không ?

Bài viết đã được chỉnh sửa nội dung bởi Belphegor Varia: 05-06-2015 - 22:50