728x90 AdSpace

Theo dõi và chia sẻ các bài viết mới
Tin nhanh

Tối ưu đồ thị phần I: Định lý Mantel và định lý Turan

Hôm nay, chúng tôi cùng các bạn tìm hiểu một số bài toán về tối ưu đồ thị, đặc biệt ở đây bạn sẽ được gặp Định lý Mantel, đinh lý Turan.
Bài toán 1: (Mantel) Chứng minh rằng với mọi đồ thị chứa nhiều hơn $\frac{{{n}^{2}}}{4}$ cạnh thì chứa một tam giác.
Chứng minh: Giả sử đồ thị $G=\left( V,E \right)$, với $\left| V \right|=n$ đỉnh, không chứa  tam giác nào. Thì với mỗi cạnh $uv$, ta phải có $d\left( u \right)+d\left( v \right)\le n$ (nếu ngược lại, theo nguyên lý chuồng bồ câu, hai đỉnh $u,v$sẽ có lân cận chung ) . Lấy tổng theo tất cả các cạnh ta được
$n\left| E \right|\ge \sum\limits_{\left\{ u,v \right\}\in E}{\left( d\left( u \right)+d\left( v \right) \right)=}\sum\limits_{v\in V}{{{d}^{2}}\left( v \right)}\ge \frac{{{\left( \sum\limits_{v\in V}{d\left( v \right)} \right)}^{2}}}{\left| V \right|}=\frac{{{\left( 2\left| E \right| \right)}^{2}}}{n}=\frac{4{{\left| E \right|}^{2}}}{n}$, từ đây ta suy ra  $\left| E \right|\le \frac{{{n}^{2}}}{4}$.


Tài liệu Tối ưu đồ thị phần I
 toi uu do thi phan dinh ly turan va mantel phan iii
toi uu do thi phan dinh ly turan va mantel phan ii
toi uu do thi phan dinh ly turan va mantel phan i

Các dạng toán về tối ưu đồ thị thường là khó, ít đề cập tới ở phổ thông.  Nhưng nội dung này thường gặp trong các kỳ thi học sinh giỏi toán nên chúng ta cùng cần quan tâm hơn.
Lấy về tài liệu nói về tối ưu đồ thị của tác giả Trương Phước Nhân để tìm hiểu hơn định lý Turan và Mantel:
Download

Nghiên cứu thêm: Bài toán girth cho đồ thị Trương Phước Nhân
Tối ưu đồ thị phần I: Định lý Mantel và định lý Turan Reviewed by Tân Phúc on 11:11:00 Rating: 5 Hôm nay, chúng tôi cùng các bạn tìm hiểu một số bài toán về tối ưu đồ thị, đặc biệt ở đây bạn sẽ được gặp Định lý Mantel, đinh lý Turan. Bà...

Không có nhận xét nào:

Xin vui lòng để lại vài dòng nhận xét hoặc đánh giá có nội dung. Sự quan tâm, chia sẻ của quý độc giả sẽ tạo ra những trải nghiệm tuyệt vời cho cộng đồng bạn đọc cả nước.