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

[supermember]

Với mỗi đĩnh của một đồ thị cho trước; ta gán cho nó một số nguyên dương.

Hiển nhiên $2$ đỉnh khác nhau sẽ được gán $2$ số nguyên dương khác nhau.

Một đồ thị được gọi là đồ thị ước số nếu $2$ đĩnh $x$ và $y$ kề nhau khi và chỉ khi $ x|y $ hoặc $y|x$

Chứng minh rằng với mọi số nguyên dương $ n \ge 3$ và mọi số nguyên dương $m$ thoả :

$ 0 < m \le \binom{n}{2}$, thì ta luôn tìm được một đồ thị ước số với $n$ đỉnh và $ m$ cạnh

Bài viết đã được chỉnh sửa nội dung bởi supermember: 12-12-2012 - 09:55

[gogo123]

Bài này không khó như lúc đầu mình nghĩ.
Dễ thấy ta chỉ cần làm việc với TH khó nhất , đó là khi $m=\binom{n}{2}=\frac{n(n-1)}{2}$.
Với đồ thị $n$ đỉnh đó ta thực hiện điền số vào các đỉnh lần lượt là $1;2;2^{2};...;2^{n-1}$ , lúc đó ta nối một đỉnh bất kì với đỉnh bội của nó.
Mà $2^{i}$ có $n-1-i$ bội trong tập trên nên với đỉnh $2^{i}$ có $n-1-i$ cạnh xuất phát từ nó tới đỉnh bội.
Như vậy,tổng số cạnh sẽ là $n-1+n-3+n-4+...+1=\frac{n(n-1)}{2}=\binom{n}{2}$.
Vậy là xong.

Bài viết đã được chỉnh sửa nội dung bởi gogo123: 12-12-2012 - 23:27