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

Đâ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
ah mà ai có ý kiến j bình luận nha.

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!!!

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!

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!