tailieunhanh - Bài tập Toán rời rạc: Đồ thị 1

Bài tập Toán rời rạc: Đồ thị 1 sau đây gồm các bài tập môn Toán rời rạc dạng đồ thị 1 nhằm giúp người học có thêm tài liệu tham khảo tham khảo môn học đồng thời tự rèn luyện kiến thức qua việc tự giải các bài tập sau đây. | Bài tập Toán rời rạc Đồ thị 1 1. Xét P (m, n) là câu ”Đồ thị đầy đủ n đỉnh Kn có đúng m cạnh”, ở đây miền giá trị của cả hai biến là tập số nguyên dương. Xác định giá trị chân lý của các khẳng định sau: (a) P (2, 2) = T hay F (b) P (3, 3) = T hay F (c) P (4, 4) = T hay F (d) ∃m ∀n P (n, m) = T hay F (e) ∀n ∃m P (n, m) = T hay F (f) ∃n P (n, 2n) = T hay F 2. Xét đồ thị G = (V, E). Ta nhắc lại rằng bậc của một đỉnh v ∈ V , ký hiệu deg(v), là số cạnh liên thuộc với nó. (a) Chứng minh rằng 2|E| = ∑ v∈V deg(v) (b) Chứng minh rằng số đỉnh bậc lẻ của G luôn là số chẵn. (c) Giả sử D và d là bậc lớn nhất và bậc nhỏ nhất của G. Chứng minh rằng d≤ 2|E| ≤ D. |V | 3. Nhắc lại rằng tô màu đồ thị là một cách gán màu cho mỗi đỉnh của đồ thị sao cho hai đỉnh kề nhau có màu khác nhau. Bổ đề (Sai). Xét G là một đồ thị có bậc lớn nhất không lớn hơn k. Nếu G có một đỉnh nhỏ hơn k, vậy G có thể tô bằng k màu. (a) Hãy đưa ra một phản ví dụ cho Bổ đề Sai khi k = 1. (b) Hãy chỉ ra chính xác câu nào sai trong chứng minh sau đây của Bổ đề Sai: Chứng minh. Chứng minh bằng quy nạp theo số đỉnh n. Giả thiết quy nạp: P (n) là mệnh đề: Xét một đồ thị G có n đỉnh sao cho bậc lớn nhất của nó không vượt quá k. Nếu G có một đỉnh có bậc nhỏ hơn k, thì G tô được bằng k màu. Bước cơ sở: (n = 1) G có chỉ một đỉnh, vậy nó tô được bằng 1 màu. Vậy P (1) đúng. Bước quy nạp: Ta giả sử P (n) đúng, xét Gn+1 là đồ thị với n + 1 đỉnh và bậc lớn nhất không vượt quá k. Ta giả sử Gn+1 có một đỉnh v có bậc nhỏ hơn k. Ta cần chứng minh Gn+1 có thể tô bằng k màu. Để làm điều này, trước hết ta xét đồ thị Gn là đồ thị tạo từ Gn+1 bằng cách xóa đỉnh v và các cạnh liên quan. Việc xóa đỉnh v giảm bậc của mọi đỉnh kề với v đi 1. Vậy trong Gn các đỉnh này có bậc nhỏ hơn k. Và bậc lớn nhất của Gn vẫn không vượt quá k. Vậy 1 Gn thỏa mãn các điều kiện của giả thiết quy nạp P (n). Ta kết luận rằng Gn có thể tô bằng k màu. Bây giờ, k màu của đồ thị Gn dùng để tô mọi đỉnh của đồ thị Gn+1 trừ đỉnh v. Vì v có bậc nhỏ hơn k, có ít .