09HCB

Trang chủ 09HCB- Lớp Hoàn Chỉnh Đại Học Khoá 2009-2011
 
Trang ChínhTrang Chính  GalleryGallery  Tìm kiếmTìm kiếm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  

Share
 

 Tài liệu và cách giải 2 bài tập ngày đầu tiên

Go down 
Tác giảThông điệp
Admin
Admin
Admin

Tổng số bài gửi : 149
Join date : 15/03/2010

Tài liệu và cách giải 2 bài tập ngày đầu tiên Empty
Bài gửiTiêu đề: Tài liệu và cách giải 2 bài tập ngày đầu tiên   Tài liệu và cách giải 2 bài tập ngày đầu tiên Empty16/3/2010, 11:05 am

Đây là phần link của thầy Sơn về tài liệu, nhân tiện mình cũng post luôn cách giải 2 bài đầu tiên trong silde, có gì các bạn góp ý nha.
http://ptnk.edu.vn/ntson/public_html/ltdt/index.html
Bài 1.
Đề: G là một đồ thị đơn, vô hướng có số cạnh >3. Chứng minh G có 2 đỉnh cùng bậc.
Giải: TH 01 : Không có đỉnh cô lập -> bậc của đỉnh chạy từ 1, 2, ..., n-1 (tổng cộng có n-1 số bậc). Mà mình có n đỉnh -> theo nguyên lý Dirichlet thì phải có ít nhất 2 đỉnh có cùng số bậc,
(Nội dung nguyên lý : có n con thỏ nhốt vào n-1 chuồng-> ít nhất 1 chuồng có 2 con thỏ)
TH 02 : Có 1 đỉnh cô lập -> số bậc của thành phần ko có đỉnh cô lập chạy từ 1 , 2,..., n-2 (vì ko có cạnh nối với đỉnh cô lập nên tối đa chỉ là n-2). Tương tự trường hợp 1, theo nguyên lý Dirichlet -> có 2 đỉnh cùng số bậc.
TH 03: Có 2 đỉnh cô lập trở lên, 2 đỉnh này có cùng số bậc là 0 -> Giải quyết xong.

Bài 2
Đề: Đồ thị G có đúng 2 đỉnh bậc lẻ, Chứng minh tồn tại 1 dây chuyền nôí 2 đỉnh đó với nhau.
Giải: Đầu tiên theo như đề bài bạn sẽ có được một đồ thị(G) mà trong đó có 2 đỉnh(Tạm thời ta gọi là Đỉnh A và Đỉnh B) có số bậc là lẽ,và ta cần chứng minh có dây chuyền nối giữa 2 đỉnh này.

Giả sử nó không có dây chuyền, thì bạn có thể tưởng tượng được là sẽ có những đỉnh nối tới A mà không nối qua B cũng như ngược lại là nối đến B mà không nối tiếp từ B đến A

Từ đó, bạn sẽ tạo được đồ thị G1 là con của đồ thị G chứa đỉnh A và tất cả các đỉnh + cạnh của nó(Điều này có thể làm được vì theo giả thiết là có những đỉnh tạo cạnh nối đến A nhưng không nối đến B). Khi tạo được đồ thì này bạn sẽ thấy đỉnh và cạnh của G1 giống như G.
(Vết gạch đứng để biểu diễn mình cắt!)

Từ đây bạn thấy rằng đồ thì mới tạo ra mâu thuẫn với Hệ quả là số đỉnh có bậc lẽ là một con số lẽ-> Không thể tồn tại được!
Vậy kết luận bài toán là có dây chuyền đi qua 2 đỉnh có số bậc là lẻ.
===>From MinhVN
Đọc xong thì nhớ thanks phát nha Very Happy
ah mà ai có ý kiến j bình luận nha.
Về Đầu Trang Go down
https://09hcb.forumvi.com
haiquangitvn

haiquangitvn

Tổng số bài gửi : 1
Join date : 19/03/2010

Tài liệu và cách giải 2 bài tập ngày đầu tiên Empty
Bài gửiTiêu đề: Làm thế nào để nộp bài tập cho thầy?   Tài liệu và cách giải 2 bài tập ngày đầu tiên Empty19/3/2010, 9:46 am

Hi All, hôm trước thầy có cho 1 bài tập về nhà làm. Mình đã làm xong nhưng lại không biết cách nào để nộp cho thầy hết. Các bạn có biết làm thế nào đê nộp bài cho thầy thì chỉ mình với nhé. Thanks nhiều nhiều!!!
Về Đầu Trang Go down
Admin
Admin
Admin

Tổng số bài gửi : 149
Join date : 15/03/2010

Tài liệu và cách giải 2 bài tập ngày đầu tiên Empty
Bài gửiTiêu đề: Re: Nộp bài LTDT   Tài liệu và cách giải 2 bài tập ngày đầu tiên Empty19/3/2010, 9:50 am

Trên thông báo bạn sẽ nộp bài cộng điểm tại Moodle môn LTDT.
Mà mình vẫn chưa thấy link nộp bài. Khi nào có mình sẽ thông báo.
Chào bạn.
Admin!
Về Đầu Trang Go down
https://09hcb.forumvi.com
billcuong

billcuong

Tổng số bài gửi : 18
Join date : 23/03/2010
Age : 32
Đến từ : Quảng Ngãi

Tài liệu và cách giải 2 bài tập ngày đầu tiên Empty
Bài gửiTiêu đề: thanks   Tài liệu và cách giải 2 bài tập ngày đầu tiên Empty26/3/2010, 2:10 am

Cảm ơn bạn đã cung cấp những bài giải trên.
Mình đọc bài 1 hiểu nhưng bài 2 thì quá cao siêu. Khi nào bạn rảnh cho mình hỏi thăm cặn kẽ về bài 2 này với nhé. Thanks!
Về Đầu Trang Go down
http://www.vssvietnam.com
Sponsored content




Tài liệu và cách giải 2 bài tập ngày đầu tiên Empty
Bài gửiTiêu đề: Re: Tài liệu và cách giải 2 bài tập ngày đầu tiên   Tài liệu và cách giải 2 bài tập ngày đầu tiên Empty

Về Đầu Trang Go down
 
Tài liệu và cách giải 2 bài tập ngày đầu tiên
Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
09HCB :: Lưu trữ :: HK1 :: LTDT-
Chuyển đến