Đến nội dung

Hình ảnh

định lí mantel và Turan

- - - - -

  • Please log in to reply
Chủ đề này có 2 trả lời

#1
buivantuanpro123

buivantuanpro123

    Hạ sĩ

  • Thành viên
  • 96 Bài viết

Chứng minh các định lí sau: 1, Định lí mantel: Nếu đồ thị với 2n đỉnh có $n^{2}+1$ cạnh thì G chứa tam giác

2, Định lí Turan: Nếu đồ thị G=(V, E) trên n đỉnh không chứa (k+1)-clique, k$\geqslant$2, thì $\left | E \right |\leq (1-\frac{1}{k})\frac{n^{2}}{2}$



#2
huytran08

huytran08

    Trung sĩ

  • Thành viên
  • 170 Bài viết

1,Cho $G$ là đồ thị trên tập hợp $V$ gồm $2n$ đỉnh và có $m\geq n^{2}+1$ cạnh.

 Giả sử $G$ không chứa tam giác.Khi đó các cạnh kề nhau không có đỉnh kề chung,do đó $d(x)+d(y) \leq 2n$ với mọi cạnh {$x,y$}$\in E$.

 

Cộng theo tất cả các cạnh của $G$ ta có:$\sum _{x\in V}d(x)^{2}=\sum _{{x,y}\in E}(d(x)+d(y))\leq 2mn $

 

Mặt khác theo BĐT $Cauchy-Schwarz$ và đẳng thức $Euler \sum _{x\in V}d(x)=2m$ ta có:

$\sum _{x\in V}d(x)^{2} \geq \frac{\left ( \sum_{x\in V}d(x) \right )^{2}}{\left | V \right |}=\frac{2m^{2}}{n} $

Từ đó suy ra $m\leq n^{2}$,mâu thuẫn

$Q.E.D$


How far are you from me,Fruit?

I am hidden in your heart,Flower.

                                                                                                                                                                                                      (Rabindranath Tagore)


#3
chuyenndu

chuyenndu

    Trung sĩ

  • Thành viên
  • 177 Bài viết

https://en.wikipedia...Turán's_theorem






1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh