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 ?
Basic Matrix
#2
Đã gửi 23-05-2017 - 10:34
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 :>
$\mathbb{VTL}$
#3
Đã gửi 23-05-2017 - 14:15
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
#4
Đã gửi 23-05-2017 - 15:54
Hâm mộ quá, chả bù cho mình học cuối lớp. hic hic
$\mathbb{VTL}$
#5
Đã gửi 01-06-2017 - 20:06
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
- redfox, lamNMP01 và nguyenhaan2209 thích
#6
Đã gửi 02-06-2017 - 11:09
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 @@
#7
Đã gửi 02-06-2017 - 13:15
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ổ đề
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh