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

[lamNMP01]

Cho G(V,E) là đồ thị có 9 đỉnh, biết trong đó cứ 5 đỉnh bất kì thì đồ thị sinh của chúng có ít nhất 2 cạnh. Hỏi có ít nhất bao nhiêu cạnh ?

[Drago]

Cho G(V,E) là đồ thị có 9 đỉnh, biết trong đó cứ 5 đỉnh bất kì thì đồ thị sinh của chúng có ít nhất 2 cạnh. Hỏi có ít nhất bao nhiêu cạnh ?

Bạn 2k1 à? Mình 2k1 Học trường Ams hèn gì học ghê quá, đăng mấy bài không ai giải nổi :>

[lamNMP01]

Bạn 2k1 à? Mình 2k1 Học trường Ams hèn gì học ghê quá, đăng mấy bài không ai giải nổi :>

 Đâu có gì đâu cậu , chả qua tớ học đtqg rồi nên cx có biết 1 ít cái gọi là bài tập khó thôi

[Drago]

Hâm mộ quá, chả bù cho mình học cuối lớp. hic hic

[JUV]

Lemma: Một đồ thị $G$ không có $k-clique$ hay $k-clique$ thiếu $1$ cạnh thì tồn tại đồ thị $G'$ $k-2$ phe cùng tập đỉnh với $G$ có số cạnh không ít hơn $G$

Sketch: Quy nạp theo $k$. Chọn $A$ là điểm có bậc lớn nhất là $k$, $M(A)$ là các đỉnh nối với $A$, $N(A)$ là các đỉnh còn lại. Xét đồ thị sinh bởi $M(A)$ không có $(k-1)-clique$ hay $(k-1)-clique$ thiếu $1$ cạnh nên có đồ thị $H$ $k-3$ phe cùng tập đỉnh và có số cạnh không ít hơn $M(A)$. Bỏ đi tất cả các cạnh trong $N(A)$ và nối tất cả các điểm của $N(A)$ với tất cả các điểm của $H$ đôi một, ta được đồ thị $G'$ $k-2$ phe (Các đỉnh của $N(A)$ là $1$ phe). Bậc của các đỉnh của $N(A)$ trong $G$ đều nhỏ hơn hoặc bằng $k$, còn trong $G'$ thì đúng bằng $k$. Mà $H$ có số cạnh ít nhất bằng $M(A)$ nên $G'$ có số cạnh ít nhất bằng $G$, $Q.E.D$

Thay $k=5$, $G$ có $9$ đỉnh, số cạnh lớn nhất thoả mãn không có $5-clique$ hay $5-clique$ thiếu $1$ cạnh thu được khi đồ thị là đồ thị $3$ phe. Ta dễ thấy số cạnh nhiều nhất là $27$, do vậy có inhiều nhất $27$ cặp điểm không được nối, hay ít nhất $9$ cặp cạnh được nối để thoả mãn đề bài, xảy ra trong trường hợp chia thành $3$ tam giác rời nhau

[lamNMP01]

Lemma: Một đồ thị $G$ không có $k-clique$ hay $k-clique$ thiếu $1$ cạnh thì tồn tại đồ thị $G'$ $k-2$ phe cùng tập đỉnh với $G$ có số cạnh không ít hơn $G$

Sketch: Quy nạp theo $k$. Chọn $A$ là điểm có bậc lớn nhất là $k$, $M(A)$ là các đỉnh nối với $A$, $N(A)$ là các đỉnh còn lại. Xét đồ thị sinh bởi $M(A)$ không có $(k-1)-clique$ hay $(k-1)-clique$ thiếu $1$ cạnh nên có đồ thị $H$ $k-3$ phe cùng tập đỉnh và có số cạnh không ít hơn $M(A)$. Bỏ đi tất cả các cạnh trong $N(A)$ và nối tất cả các điểm của $N(A)$ với tất cả các điểm của $H$ đôi một, ta được đồ thị $G'$ $k-2$ phe (Các đỉnh của $N(A)$ là $1$ phe). Bậc của các đỉnh của $N(A)$ trong $G$ đều nhỏ hơn hoặc bằng $k$, còn trong $G'$ thì đúng bằng $k$. Mà $H$ có số cạnh ít nhất bằng $M(A)$ nên $G'$ có số cạnh ít nhất bằng $G$, $Q.E.D$

Thay $k=5$, $G$ có $9$ đỉnh, số cạnh lớn nhất thoả mãn không có $5-clique$ hay $5-clique$ thiếu $1$ cạnh thu được khi đồ thị là đồ thị $3$ phe. Ta dễ thấy số cạnh nhiều nhất là $27$, do vậy có inhiều nhất $27$ cặp điểm không được nối, hay ít nhất $9$ cặp cạnh được nối để thoả mãn đề bài, xảy ra trong trường hợp chia thành $3$ tam giác rời nhau

Cảm ơn anh vì cách làm bài trên, em giải bằng phép truy hồi cũng ra kết quả như thế, ngoài ra thầy em nói là 1 cách có thể dùng định lý Hall @@

[JUV]

Cảm ơn anh vì cách làm bài trên, em giải bằng phép truy hồi cũng ra kết quả như thế, ngoài ra thầy em nói là 1 cách có thể dùng định lý Hall @@

Thật ra bổ đề trên phải trừ TH $(k-1)-clique$ nhưng cũng dễ dàng CM mọi đồ thị khác đều thoả mãn bổ đề