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

[tieu_than_tien]

cho $p \in P $là tập các số nguyên tố .Tìm số $ n \in Z^{+}$ lớn nhất thỏa mãn các cạnh của 1 graph $n$ đỉnh có thể tô bằng $p+1$ màu thỏa mãn :
a)Có tối thiểu 2 cạnh khác màu .
b)Nếu $A,B,C$ là 3 đỉnh của graph thì nếu $AB,AC$ cùng màu thì $BC$ cùng màu .

Bài viết đã được chỉnh sửa nội dung bởi DinhCuongTk14: 01-09-2007 - 09:28

[chuong_pbc]

cho $p \in P $là tập các số nguyên tố .Tìm số $ n \in Z^{+}$ lớn nhất thỏa mãn các cạnh của 1 graph $n$ đỉnh có thể tô bằng $p+1$ màu thỏa mãn :
a)Có tối thiểu 2 cạnh khác màu .
b)Nếu $A,B,C$ là 3 đỉnh của graph thì nếu $AB,AC$ cùng màu thì $BC$ cùng màu .

ta chứng minh $N max =p^2$
ta định nghĩa tô màu 1 p-giác là tô màu tất cả các cạnh và các đường chéo của nó.
Đánh số màu từ $0 \to p$ ,đánh số các đỉnh như sau:
1,1 ; 1,2;......; 1,p
2,1 ; 2,2;......; 2,p
...
p,1 ; p,2;......; p,p
với màu thứ i (với $0\leq i\leq p-1$) ta tô như sau :
-p-giác thứ nhất 1,1 ; 2,1+i;.......;p,1+(p-1)i

-p-giác thứ 2: 1,2 ; 2,2+i;........;p,2+(p-1)i
-...
-p-giác thứ p : 1,p ; 2,p+i......... ;p,p+(p-1)i
riêng màu thứ p ta tô p -giác j,1 ; j,2;......; j,p với $0\leq j\leq p$
tiếp theo ta c/m ko còn cách tô khác thỏa mãn
do có p+1 màu nếu tồn tại p+1 giác to cùng 1 màu thì tồn tại 1 đỉnh khác (p+1) đỉnh đó nối với p+1 đỉnh này mà chỉ dc tô bởi p màu ( do trừ màu vừa tô) nên tồn tại 2 đỉnh cùng màu do đó tam giác có 2 cạnh cùng màu nhưng cạnh kia khác màu (><) như vậy trong cách tô thỏa mãn cho $p^2$ đỉnh thì đa giác lớn nhất tô 1 màu là có p đỉnh
Xét 1 màu bất kì ta tô 1 đa giác thì tô được tối đa $C^2_p$ cạnh mà từ p^2 đỉnh tạo ra được p đa giác -mỗi đa giác p đỉnh nên có tối đa là $p.C^2_p$ cạnh được tô 1màu.Lại có p+1 màu nên có $p(p+1)C^2_p$ cạnh được tô và bằng số cạnh có thể nói được của đa giác $p^2$đỉnh.Do đó cách tô với p^2 đỉnh duy nhất là với mầy j nhóm p nhóm ,mỗi nhóm p đỉnh tạo thành tô cùng màu j.

+)c/m p^2 là số lớn nhất có thể :
Nếu có lớn hơn hoặc bằng p^2+1 đỉnh .Xét đỉnh A bất kìvà p^2 đỉnh còn lại , từ A kẻ đến đỉnh B bất kì bởi màu j nào đó mà B luôn là đỉnh của p-giác nào đó tô bởi 1 màu j nên theo c/m ở trên thì từ A nối đến đỉnh bất kì nào của p-giác đều có màu j do đó tạo thành (p+1) giác được tô cùng 1 màu ( ><)
--> đpcm

Bài viết đã được chỉnh sửa nội dung bởi chuong_pbc: 02-09-2007 - 11:13