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

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<br /> <br /> 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| = ∑<br /> v∈V<br /> <br /> deg(v)<br /> <br /> (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 |<br /> <br /> 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<br /> <br /> 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 hơn k màu được gán cho các đỉnh kề với v. Vậy trong số k màu có thể, sẽ có một màu không được dùng cho các nút kề với v, và màu này có thể được gán cho v để tô Gn+1 bằng k màu. 4. Một đồ thị có độ rộng m nếu các đỉnh có nó có thể được sắp xếp thành dãy v1 , v 2 , · · · , v n sao cho mỗi đỉnh vi có cạnh nối với nhiều nhất là m đỉnh đứng trước nó (Đỉnh vj đứng trước vi nếu j < i.) Dùng quy nạp để chứng minh rằng mọi đồ thị với độ rộng nhỏ hơn hoặc bằng m đều có thể tô bằng (m + 1) màu. 5. Đồ thị phẳng là đồ thị có thể vẽ trên mặt phẳng sao cho các đường cong biểu diễn cạnh hoặc không giao nhau hoặc chỉ giao nhau ở các đỉnh chung. (a) Chỉ ra rằng đồ thị con của một đồ thị phẳng cũng là đồ thị phẳng. (b) Ta biết rằng mọi đồ thị phẳng phải có một đỉnh có bậc không lớn hơn 5. Hãy chứng minh bằng quy nạp rằng mọi đồ thị phẳng có thể tô không dùng quá 6 màu. 6. Hai đồ thị gọi là đẳng cấu nếu chúng giống hệt nhau về cấu trúc nhưng chỉ khác nhau nhãn của đỉnh. Nói một cách chính xác, hai đồ thị G = (V, E) và H = (W, F ) đẳng cấu, và viết G ∼ H, nếu có một song ánh f : V → W sao cho: = {x, y} ∈ E với mọi x, y ∈ V . Những cặp đồ thị nào từ bốn đồ thị dưới đây đẳng cấu với nhau? Tại sao? nếu và chỉ nếu {f (x), f (y)} ∈ F<br /> <br /> 2<br /> <br /> 7. Để hiện đại hóa phương pháp giảng dạy, số giờ lên lớp của môn Toán rời rạc bị giảm đi, thay vào đó mỗi sinh viên phải tham gia vào một số nhóm tự học. Mỗi nhóm tự học này sẽ phải đề cử một sinh viên đại diện cho nhóm để trình bày một nội dung nghiên cứu trước lớp. Yêu cầu bắt buộc là một sinh viên chỉ đại diện cho một nhóm. Làm thế nào để chọn đại diện từ mỗi nhóm để đảm bảo yêu cầu này? (a) Mô hình bài toán lựa chọn đại diện bằng ghép cặp. (b) Danh sách đăng ký nhóm của sinh viên cho thấy rằng không có sinh viên nào là thành viên của hơn 4 nhóm và mỗi nhóm đều có ít nhất 4 sinh viên. Điều này có đảm bảo được rằng luôn có cách chọn đại diện thích hợp không? hãy giải thích. 8. Xét đồ thị sau:<br /> <br /> .<br /> <br /> (a) Đường kính của đồ thị này bằng bao nhiêu? (b) Đồ thị này có phải đồ thị phẳng không? Giải thích câu trả lời của bạn. (c) Số màu ít nhất cần thiết để tô đồ thị trên là bao nhiêu? Giải thích câu trả lời của bạn. 9. Chứng minh hoặc bác bỏ rằng trong mọi đồ thị với n ≥ 2 đỉnh luôn có hai đỉnh cùng bậc.<br /> <br /> 3<br /> <br />