Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope
Ghi Danh Hỏi/Ðáp Thành Viên Social Groups Lịch Ðánh Dấu Ðã Ðọc

Go Back   Diễn Đàn MathScope > Sơ Cấp > Tổ Hợp

News & Announcements

Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé !

* Nội quy MathScope.Org

* Một số quy định chung !

* Quy định về việc viết bài trong diễn đàn MathScope

* Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


Trả lời Gởi Ðề Tài Mới
 
Ðiều Chỉnh Xếp Bài
Old 09-08-2012, 08:14 PM   #1
batigoal
Super Moderator
 
batigoal's Avatar
 
Tham gia ngày: Jul 2010
Đến từ: Hà Nội
Bài gởi: 2,895
Thanks: 382
Thanked 2,967 Times in 1,295 Posts
Topic các định lí về lí thuyết đồ thị

Chào các bạn

Lí thuyết đồ thị là một môn học thuộc lĩnh vực toán học tổ hợp rời rạc . Lí thuyết đồ thị xuất hiện nhiều trong các kì thi học sinh giỏi các cấp, có thể nói đây là một môn học có nhiều ứng dụng trong thực tiễn như các mô hình lập lịch phân công công việc, các giải pháp tối ưu hóa trong hệ thống giao thông, cách đặt các trạm thu phát tín hiệu điện thoại sao cho tốt nhất,...Đây là một môn học khó với khá nhiều bạn. Một phần vì tính tư duy trừu tượng trong đó, phần khác là rất nhiều định lí về lí thuyết đồ thị chúng ta cần phải biết. Để thuận tiện cho các anh em trong việc học tập, rèn luyện và mở mang kiến thức với Lí thuyết đồ thị, cùng với mong muốn thúc đẩy học tập tốt toán tổ hợp và đặc biệt là lí thuyết đồ thị mình xin phép lập topic này mong các bạn thành viên Mathscope mỗi ngày chúng ta ủng hộ ít nhất 1 định lí bao gồm chứng minh cho định lí ấy. Topic được lập ra còn nhằm mục đích để không chỉ chúng ta học tập, rèn luyện mà các thế hệ đàn em tiếp theo của chúng ta sẽ được kế thừa kiến thức và tiếp tục học tập, cập nhật bổ sung để có một bộ lí thuyết đầy đủ hơn các anh của chúng.

Để topic sạch ,đẹp, chuyên nghiệp mình xin đưa ra một số nội quy cho topic như sau:
NỘI QUY TOPIC

1. Đánh số thứ tự định lí (Ghi tên định lí nếu có)
Mẫu thực hiện
Định lí 1
..........
Chứng minh định lí:

Định lí 2 (Mantel)
..........
Chứng minh định lí:


2. Nếu định lí và chứng minh sử dụng kí hiệu mới thì bạn gửi định lí hãy giải thích kí hiệu, thuật ngữ mới đó cho bạn đọc dễ quan sát và tìm hiểu.
3.Đây là topic dành riêng cho định lí, hệ quả, bổ đề nên không post bài toán hỏi về lí thuyết đồ thị ở đây, nếu cần hỏi về bài toán nào các bạn lập topic khác.
4. Các bài gửi rác, spam sẽ bị xóa mà không báo trước

Rất mong sự ủng hộ nhiệt tình của các bạn.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
“ Sức mạnh của tri thức là sự chia sẻ tri thức”

[Only registered and activated users can see links. ]

thay đổi nội dung bởi: batigoal, 09-08-2012 lúc 09:02 PM
batigoal is offline   Trả Lời Với Trích Dẫn
The Following 22 Users Say Thank You to batigoal For This Useful Post:
99 (09-08-2012), bboy114crew (20-09-2012), conami (09-08-2012), conan99 (03-03-2013), Conanvn (10-08-2012), ELOV (10-08-2012), hahahaha4 (09-08-2012), Highschoolmath (09-08-2012), hungqh (09-08-2012), leeleex (11-09-2012), minhcanh2095 (15-08-2012), mrvui123 (03-10-2012), n.v.thanh (09-08-2012), ptk_1411 (09-08-2012), sang89 (10-08-2012), thiendienduong (10-08-2012), TNP (09-08-2012), tranhoang233 (10-08-2012), TrauBo (09-08-2012), Trànvănđức (04-03-2013), Trầm (09-08-2012), vanthanh0601 (10-08-2012)
Old 09-08-2012, 08:22 PM   #2
batigoal
Super Moderator
 
batigoal's Avatar
 
Tham gia ngày: Jul 2010
Đến từ: Hà Nội
Bài gởi: 2,895
Thanks: 382
Thanked 2,967 Times in 1,295 Posts
I. CÁC ĐỊNH NGHĨA .
- Trước khi đi đến các định lí thì sau đây là một số khái niêm cơ bản để bạn đọc nhập môn lí thuyết đồ thị .
1.1. Định nghĩa 1.
Một đơn đồ thị $G = (V, E)$ gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập $E$ mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt.
1.2. Định nghĩa 2.
Một đa đồ thị $G = (V, E)$ gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ $E$ mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt. Hai cạnh được gọi là cạnh bội hay song song nếu chúng cùng tương ứng với một cặp đỉnh.
1.3. Định nghĩa 3.
Một đồ thị có hướng $G = (V, E)$ gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc $V$.
1.4. Định nghĩa 4.
Một đa đồ thị có hướng $G = (V, E)$ gồm một tập khác rỗng $V$ mà các phần tử của nó gọi là các đỉnh và một họ $E$ mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc $V$.
1.5. Định nghĩa 5
Hai đỉnh $u$ và $v$ trong đồ thị (vô hướng) $G=(V,E)$ được gọi là liền kề nếu $(u,v) \in E$. Nếu $e = (u,v)$ thì $e$ gọi là cạnh liên thuộc với các đỉnh $u$ và $v$. Cạnh $e$ cũng được gọi là cạnh nối các đỉnh $u$ và $v$.
1.6. Định nghĩa 6
Bậc của đỉnh $v$ trong đồ thị $G=(V,E)$, ký hiệu $deg(v)$, là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó.
Đỉnh $v$ được gọi là đỉnh treo nếu $deg(v)=1$ và được gọi là đỉnh cô lập nếu $deg(v)=0$.

1.7. Định nghĩa 7
Cho $A, B$ là 2 đỉnh của một đồ thị G. Một đường đi từ A đến B là một dãy các cạnh $(A_i, A_{i+1}) \ (i=\overline{0,k-1})$ với $A_0=A, A_k=B$. Số các cạnh (ở đây là $k$) tạo nên đường đi gọi là độ dài của đường đi.
Một đồ thị gọi là liên thông nếu giữa 2 đỉnh bất kì luôn có đường đi.
1.8. Định nghĩa 8 (Định nghĩa về tính liên thông)

Đường đi độ dài $n$ từ đỉnh $u$ đến đỉnh $v$, với $n$ là một số nguyên dương, trong đồ thị (giả đồ thị vô hướng hoặc đa đồ thị có hướng) $G=(V,E)$ là một dãy các cạnh (hoặc cung) $e_1, e_2, ..., e_n$ của đồ thị sao cho $e_1=(x_0,x_1),e_2=(x_1,x_2), ...,e_n=(x_{n-1},x_n)$, với $x_0=u$ và $x_n=v$. Khi đồ thị không có cạnh (hoặc cung) bội, ta ký hiệu đường đi này bằng dãy các đỉnh $x_0, x_1, ..., x_n$. Đường đi được gọi là chu trình nếu nó bắt đầu và kết thúc tại cùng một đỉnh.
Đường đi hoặc chu trình gọi là đơn nếu nó không chứa cùng một cạnh (hoặc cung) quá một lần.
Một đường đi hoặc chu trình không đi qua đỉnh nào quá một lần (trừ đỉnh đầu và đỉnh cuối của chu trình là trùng nhau) được gọi là đường đi hoặc chu trình sơ cấp. Rõ ràng rằng một đường đi (t.ư. chu trình) sơ cấp là đường đi (t.ư. chu trình) đơn.
1.9. Định nghĩa 9
Một đồ thị (vô hướng) được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị.
Một đồ thị không liên thông là hợp của hai hay nhiều đồ thị con liên thông, mỗi cặp các đồ thị con này không có đỉnh chung. Các đồ thị con liên thông rời nhau như vậy được gọi là các thành phần liên thông của đồ thị đang xét. Như vậy, một đồ thị là liên thông khi và chỉ khi nó chỉ có một thành phần liên thông.
1.10. Định nghĩa 10 (Chu trình Hamilton)
Định nghĩa: Chu trình (t.ư. đường đi) sơ cấp chứa tất cả các đỉnh của đồ thị (vô hướng hoặc có hướng) G được gọi là chu trình (t.ư. đường đi) Hamilton. Một đồ thị có chứa một chu trình (t.ư. đường đi) Hamilton được gọi là đồ thị Hamilton (t.ư. nửa Hamilton).


II. CÁC ĐỊNH LÍ (VIỆC BỔ SUNG CÁC ĐỊNH LÍ BẮT ĐẦU . XIN MỜI CÁC BẠN)
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
“ Sức mạnh của tri thức là sự chia sẻ tri thức”

[Only registered and activated users can see links. ]

thay đổi nội dung bởi: batigoal, 14-08-2012 lúc 08:34 PM
batigoal is offline   Trả Lời Với Trích Dẫn
The Following 11 Users Say Thank You to batigoal For This Useful Post:
99 (09-08-2012), AnhIsGod (09-08-2012), Conanvn (10-08-2012), hahahaha4 (09-08-2012), Highschoolmath (09-08-2012), huynhcongbang (10-08-2012), MathForLife (09-08-2012), n.v.thanh (09-08-2012), thiendienduong (10-08-2012), tienanh_tx (26-04-2015), Trầm (09-08-2012)
Old 09-08-2012, 08:30 PM   #3
TrauBo
Moderator
 
TrauBo's Avatar
 
Tham gia ngày: Oct 2011
Đến từ: Hội Fan của thầy Thái (VVT Fan Club)
Bài gởi: 1,058
Thanks: 937
Thanked 1,249 Times in 433 Posts
Định lý 1: (Định lý Mantel)

Cho G là một đồ thị (đơn, vô hướng) trên $n$ đỉnh. Nếu G không có tam giác thì G không có nhiều hơn $\left[ \dfrac{n^2}{4}\right]$ cạnh. Đẳng thức xảy ra khi và chỉ khi $G=K_{ \frac{n}{2} , \frac{n}{2}}$ nếu $n$ chẵn và $K_{\frac{n-1}{2} , \frac{n+1}{2}}$ nếu $n$ lẻ.
Chứng minh:

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: Trầm, 09-08-2012 lúc 08:56 PM
TrauBo is offline   Trả Lời Với Trích Dẫn
The Following 11 Users Say Thank You to TrauBo For This Useful Post:
99 (09-08-2012), AnhIsGod (09-08-2012), Conanvn (21-10-2012), hahahaha4 (09-08-2012), Highschoolmath (09-08-2012), hungqh (17-09-2012), mrvui123 (03-10-2012), n.v.thanh (09-08-2012), supermouse (05-10-2012), thiendienduong (10-08-2012), Trầm (09-08-2012)
Old 09-08-2012, 08:33 PM   #4
batigoal
Super Moderator
 
batigoal's Avatar
 
Tham gia ngày: Jul 2010
Đến từ: Hà Nội
Bài gởi: 2,895
Thanks: 382
Thanked 2,967 Times in 1,295 Posts
Định lí 2 (Còn được gọi là bổ đề bắt tay.)
Cho đồ thị $G = (V, E)$. Khi đó
$$2|E| =\sum\limits_{v \in {\kern 1pt} V} {\deg (v)} $$

Chứng minh

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
“ Sức mạnh của tri thức là sự chia sẻ tri thức”

[Only registered and activated users can see links. ]

thay đổi nội dung bởi: batigoal, 09-08-2012 lúc 08:43 PM
batigoal is offline   Trả Lời Với Trích Dẫn
The Following 7 Users Say Thank You to batigoal For This Useful Post:
99 (09-08-2012), AnhIsGod (09-08-2012), hahahaha4 (09-08-2012), Highschoolmath (09-08-2012), n.v.thanh (09-08-2012), thiendienduong (10-08-2012), Trầm (09-08-2012)
Old 09-08-2012, 08:45 PM   #5
TrauBo
Moderator
 
TrauBo's Avatar
 
Tham gia ngày: Oct 2011
Đến từ: Hội Fan của thầy Thái (VVT Fan Club)
Bài gởi: 1,058
Thanks: 937
Thanked 1,249 Times in 433 Posts
Định lý 3: Định lý Ramsey

Với mọi số nguyên dương $k, l$ tồn tại một số nguyên dương nhỏ nhất $R(k,l)$ thỏa mãn: Mọi cách tô màu các cạnh của một đồ thị đầy đủ trên $R(k,l)$ đỉnh bằng hai màu xanh và đỏ đều chứa một dồ thị con đầy đủ trên $k$ đỉnh màu xanh hoặc một đồ thị con đầy đủ trên $l$ đỉnh màu đỏ.
Chứng minh:

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: Trầm, 09-08-2012 lúc 08:55 PM
TrauBo is offline   Trả Lời Với Trích Dẫn
The Following 8 Users Say Thank You to TrauBo For This Useful Post:
99 (09-08-2012), AnhIsGod (09-08-2012), batigoal (09-08-2012), hahahaha4 (09-08-2012), Highschoolmath (09-08-2012), n.v.thanh (09-08-2012), philomath (09-08-2012), Trầm (09-08-2012)
Old 09-08-2012, 09:40 PM   #6
hahahaha4
+Thành Viên+
 
hahahaha4's Avatar
 
Tham gia ngày: Jun 2011
Bài gởi: 34
Thanks: 58
Thanked 14 Times in 10 Posts
Định lý 4: Định lý về đồ thị 2 phần.
Một đồ thị là 2 phần nếu và chỉ nếu không có chu trình sơ cấp độ dài lẻ

Chứng minh:

Chứng minh của mình.Mọi người cho ý kiến nhé.Rất thích cái topic này
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Hoàng Sa,Trường Sa là của Việt Nam

thay đổi nội dung bởi: Trầm, 09-08-2012 lúc 10:15 PM
hahahaha4 is offline   Trả Lời Với Trích Dẫn
The Following 2 Users Say Thank You to hahahaha4 For This Useful Post:
n.v.thanh (09-08-2012), TrauBo (09-08-2012)
Old 09-08-2012, 09:58 PM   #7
TrauBo
Moderator
 
TrauBo's Avatar
 
Tham gia ngày: Oct 2011
Đến từ: Hội Fan của thầy Thái (VVT Fan Club)
Bài gởi: 1,058
Thanks: 937
Thanked 1,249 Times in 433 Posts
Định lý 5: (công thức Euler)
Cho G là một đồ thị phẳng liên thông với $n$ đỉnh, $e$ cạnh. Giả sử $f$ là số mặt của một biểu diễn phẳng của G thì $$n-e+f=2$$

Chứng minh:





[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
TrauBo is offline   Trả Lời Với Trích Dẫn
The Following 2 Users Say Thank You to TrauBo For This Useful Post:
hahahaha4 (09-08-2012), n.v.thanh (09-08-2012)
Old 09-08-2012, 10:06 PM   #8
ptk_1411
Moderator
 
ptk_1411's Avatar
 
Tham gia ngày: Apr 2011
Bài gởi: 697
Thanks: 162
Thanked 810 Times in 364 Posts
Bổ đề 3.1(tiếp theo về số Ramsey)

Với $R(m,n)$ là số Ramsey thì $$R(m,n)\le C_{m+n-2}^{n-1}$$

Chứng minh

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
P.T.K
Có xa xôi mấy mà tình xa xôi...
ptk_1411 is offline   Trả Lời Với Trích Dẫn
The Following 2 Users Say Thank You to ptk_1411 For This Useful Post:
hahahaha4 (09-08-2012), n.v.thanh (09-08-2012)
Old 09-08-2012, 10:52 PM   #9
hahahaha4
+Thành Viên+
 
hahahaha4's Avatar
 
Tham gia ngày: Jun 2011
Bài gởi: 34
Thanks: 58
Thanked 14 Times in 10 Posts
Định lý 6 (Bất đẳng thức liên hệ giữa số cạnh đỉnh và số thành phần liên thông)
Một đồ thị có $n$ đỉnh,$k$ thành phần liên thông và $m$ cạnh thì ta có:
$$n-k \le m \le \dfrac{(n-k)(n-k+1)}{2}$$
Chứng minh:

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Hoàng Sa,Trường Sa là của Việt Nam

thay đổi nội dung bởi: hahahaha4, 09-08-2012 lúc 10:54 PM
hahahaha4 is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to hahahaha4 For This Useful Post:
n.v.thanh (09-08-2012)
Old 10-08-2012, 01:04 PM   #10
batigoal
Super Moderator
 
batigoal's Avatar
 
Tham gia ngày: Jul 2010
Đến từ: Hà Nội
Bài gởi: 2,895
Thanks: 382
Thanked 2,967 Times in 1,295 Posts
Định lí 7.
Giữa mọi cặp đỉnh phân biệt của một đồ thị liên thông luôn có đường đi sơ cấp.

Chứng minh

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
“ Sức mạnh của tri thức là sự chia sẻ tri thức”

[Only registered and activated users can see links. ]

thay đổi nội dung bởi: batigoal, 10-08-2012 lúc 01:14 PM
batigoal is offline   Trả Lời Với Trích Dẫn
Old 14-08-2012, 08:20 PM   #11
batigoal
Super Moderator
 
batigoal's Avatar
 
Tham gia ngày: Jul 2010
Đến từ: Hà Nội
Bài gởi: 2,895
Thanks: 382
Thanked 2,967 Times in 1,295 Posts
Định lí 8 (Định lý (Dirac, 1952) )
Nếu G là một đơn đồ thị có $n$ đỉnh và mọi đỉnh của $G$ đều có bậc không nhỏ hơn $\frac{n}{2}$ thì $G$ là một đồ thị Hamilton.
Chứng minh

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Hình Kèm Theo
Kiểu File : jpg anh 1.1.jpg (12.8 KB, 741 lần tải)
__________________
“ Sức mạnh của tri thức là sự chia sẻ tri thức”

[Only registered and activated users can see links. ]

thay đổi nội dung bởi: batigoal, 14-08-2012 lúc 08:31 PM
batigoal is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to batigoal For This Useful Post:
Ng_Anh_Hoang (14-08-2012)
Old 15-08-2012, 08:57 AM   #12
nguyentram
+Thành Viên+
 
Tham gia ngày: Jul 2012
Bài gởi: 59
Thanks: 26
Thanked 43 Times in 28 Posts
Định lí 9( Mở rộng của định lí dirac)
Nếu G là một đơn đồ thị có n đỉnh và tổng bậc của 2 đỉnh bất kì trong G không nhỏ hơn n thì G là một đồ thị Hamilton.
Chứng minh tương tự như định lí dirac
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: nguyentram, 15-08-2012 lúc 09:00 AM
nguyentram is offline   Trả Lời Với Trích Dẫn
Old 15-08-2012, 09:38 AM   #13
nghiepdu-socap
+Thành Viên+
 
nghiepdu-socap's Avatar
 
Tham gia ngày: Apr 2010
Bài gởi: 193
Thanks: 195
Thanked 129 Times in 72 Posts
Trích:
Nguyên văn bởi nguyentram View Post
Định lí 9( Mở rộng của định lí dirac)
Nếu G là một đơn đồ thị có n đỉnh và tổng bậc của 2 đỉnh bất kì trong G không nhỏ hơn n thì G là một đồ thị Hamilton.
Chứng minh tương tự như định lí dirac
Đây là định lý Ore, bạn bổ sung vào nhé
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
nghiepdu-socap is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to nghiepdu-socap For This Useful Post:
nguyentram (15-08-2012)
Trả lời Gởi Ðề Tài Mới

Bookmarks

Ðiều Chỉnh
Xếp Bài

Quuyền Hạn Của Bạn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


Múi giờ GMT. Hiện tại là 04:55 AM.


Powered by: vBulletin Copyright ©2000-2018, Jelsoft Enterprises Ltd.
Inactive Reminders By mathscope.org
[page compression: 129.41 k/144.94 k (10.71%)]