Bài tập cấu trúc rời rạc đại học bách khoa năm 2024
|
Toán rời rạc là môn cơ sở ngành của hầu hết các môn có dính dáng tới máy tính, và nó là một môn cũng rất quan trọng cho các bạn nào theo ngành IT. Toán rời rạc cung cấp cho mọi người những kiến thức cơ bản về tổ hợp và lý thuyết đồ thị. Phần tổ hợp thì khá là quen thuộc vì hầu hết mọi người đều được làm quen từ hồi học THPT. Các bài toán đề cập đến như là : bài toán đếm, bài toán liệt kê, bài toán tồn tại, nguyên lý Dirichlet, nguyên lý cực hạn. Sau đó còn có tổ hợp, chỉnh hợp, hoán vị, số Sterling, số Catalan,... Các lý thuyết tổ hợp là nền tảng cho lý thuyết tính toán, độ phức tạp, những bài toán kinh điển như P = NP, ... Lý thuyết đồ thị là phần mới. Toán rời rạc sẽ đề cập tới khái niệm đồ thị, những loại đồ thị khác nhau, các thuật toán trên đồ thị ( DFS, BFS, Djikstra, ...) và những bài toán có thể giải trên đồ thị ( hay mô hình hóa chúng bằng đồ thị để giải quyết)... Tại trường ĐH Bách Khoa Hà Nội, ngoài các sinh viên viện CNTT thì sinh viên viện Toán cũng phải học toán rời rạc, và theo mình biết thì toán rời rạc của sinh viên viện toán khó hơn một tí so với viện CNTT. Toán rời rạc của viện toán được dạy bởi các thầy/cô viện toán và toán rời rạc của viện CNTT được giảng dạy bởi các thầy/cô viện CNTT. Về phần tài liệu thì mỗi thầy/cô đều có slide khác nhau, nhưng đa số dựa trên giáo trình toán rời rạc của thầy Nguyễn Đức Nghĩa. Nhưng mình khuyên các bạn là không nên học theo giáo trình mà học theo các slide của thầy/cô, các slide của các thầy/cô đều đã được chắt lọc những kiến thức trọng tâm nhất. Mình chia sẻ một số tài liệu toán rời rạc để mọi người tham khảo : BÀI GIẢNG - GIÁO TRÌNH (TRƯỜNG KHÁC)
SLIDE BÀI GIẢNG (HUST)
Mình thì mình thích đọc bài giảng của thầy Trần Vĩnh Đức Hơn, thầy viết rất đơn giản nhưng đủ ý và dễ hiểu, tuy nhiên tài liệu của thầy về phần đồ thị nhiều hơn ( kể cả khi học thầy trên lớp thì đa số thầy cũng giảng về phần đồ thị nhiều hơn). Trong phần bài tập này, chúng ta sẽ làm quen với các khái niệm và định nghĩa trong lý thuyết đồ thị . Sinh viên cần ôn lại lý thuyết của chương 8 trước khi làm các bài tập bên dưới. 2 Bài tập mẫu Câu 1. Có bao nhiêu cạnh trong một đồ thị vô hướng có 6 đỉnh, mỗi đỉnh có bậc bằng 4? Lời giải. Vì tổng các bậc của đồ thị là 6 × 4 = 24, nên 2e=24. Do đó, số cạnh trong đồ thị là e=12. Đồ thị có thể được vẽ như hình bên dưới đây: 2 A B D F C E Câu 2. Có bao nhiêu bậc vào và bậc ra của mỗi đỉnh trong đồ thị có hướng G1 như dưới đây? A B G F C 1 E D Lời giải. • deg−(A) = 0, deg−(B) = 2, deg−(C) = 2, deg−(D) = 2, deg−(E) = 2, deg−(F) = 3, • deg+(A) = 4, deg+(B) = 2, deg+(C) = 1, deg+(D) = 2, deg+(E) = 1, deg+(F) = 1. 2 Câu 3. Liệu có tồn tại một đơn đồ thị gồm các đỉnh mà có bậc lần lượt là : Giáo trình Cấu Trúc Rời Rạc Trang 1/6 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính
Nếu có hãy vẽ đồ thị đó. Lời giải.
Đồ thị này được vẽ như sau: B C A D
cả các đỉnh là một số lẻ. 2 3 Bài tập cần giải Câu 4. Có bao nhiêu cạnh trong một đồ thị vô hướng có 8 đỉnh, mỗi đỉnh có bậc là 5 ? Vẽ đồ thị này. Câu 5. Có bao nhiêu bậc vào và bậc ra của mỗi đỉnh trong đồ thị có hướng G2 như dưới đây? A B H G C D F E Câu 6. Liệu có tồn tại một đơn đồ thị gồm các đỉnh mà có bậc lần lượt là :
Giáo trình Cấu Trúc Rời Rạc Trang 2/6 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính Nếu có hãy vẽ đồ thị đó. Câu 7. Số cạnh nhiều nhất có thể của một đơn đồ thị gồm 12 đỉnh là bao nhiêu? Còn trong trường hợp đa đồ thị và giả đồ thị thì như thế nào? Câu 8. Hãy xác định danh sách kề, ma trận kề và ma trận liên thuộc của đồ thị G3 sau: F B E C D A G3 Câu 9. Xét đồ thị vô hướng G4 có ma trận kề (adjacency matrix) như sau: A B C D E F G H A B C D E F 0 0 1 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 G H • Hãy vẽ đồ thị G4. • Xác định danh sách kề và ma trận liên thuộc của đồ thị. • Hãy cho biết đồ thị này có phải là đồ thị phân đôi không. Nếu có, hãy vẽ lại dưới dạng một đồ thị phân đôi. • Hãy cho biết đồ thị này có phải là đồ thị phẳng không (đồ thị phẳng là đồ thị có thể được vẽ trên một mặt phẳng mà các cạnh không cắt chéo lẫn nhau). Nếu có, hãy vẽ lại dưới dạng một đồ thị phẳng. Câu 10. Đồ thị phân đôi.
đôi". Chứng minh. Giáo trình Cấu Trúc Rời Rạc Trang 3/6 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính
đúng hay sai. Chứng minh. 4 Bài tập nâng cao Câu 11. Đếm số cạnh của các đồ thị đặc biệt sau:
Câu 12. Hãy vẽ các đồ thị sau:
Câu 13. • Hãy xác định danh sách kề, ma trận kề và ma trận liên thuộc của đồ thị sau: B A C D F E • Hãy cho biết đồ thị này có phải là đồ thị phân đôi không. Nếu có, hãy vẽ lại dưới dạng một đồ thị phân đôi. • Hãy cho biết đồ thị này có phải là đồ thị phẳng không. Nếu có, hãy vẽ lại dưới dạng một đồ thị phẳng. Giáo trình Cấu Trúc Rời Rạc Trang 4/6 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính A A D B C E F D E F C B G1 G2 Câu 14. Hãy xác định danh sách kề, ma trận kề và ma trận liên thuộc của hai đồ thị sau và cho biết hai đồ thị này có đẳng cấu không. Câu 15. Hãy xác định danh sách kề, ma trận kề và ma trận liên thuộc của hai đồ thị sau và cho biết hai đồ thị này có đẳng cấu không. A B C A B D F C D F E E G1 G2 Câu 16. Hãy vẽ các đồ thị sau:
với nhau nếu và chỉ nếu 1 trong 2 số tương ứng sẽ chia hết cho số còn lại
với nhau nếu và chỉ nếu 2 số tương ứng có ước số chung lớn nhất là 1.
Câu 17. Một cuộc họp có ít nhất hai đại biểu đến dự. Mỗi người quen ít nhất một đại biểu khác. Chứng minh rằng lượng người có số lẻ người quen là một số chẵn. Câu 18. Hãy chứng minh rằng trong một đơn đồ thị, luôn tồn tại hai đỉnh có cùng bậc. Câu 19. Các đồ thị đặc biệt sau có phải là đồ thị phân đôi không, hãy giải thích: Giáo trình Cấu Trúc Rời Rạc Trang 5/6 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính
Câu 20. Hãy chứng minh rằng trong một đồ thị vô hướng G,
Câu 21. Một buổi thảo luận có 101 khách mời; hãy chứng minh rằng tồn tại một người khách mời đã tranh luận với một số chẵn người khách mời khác. Câu 22. Do khói, bụi và hơi nước bốc lên từ một miệng núi lửa bên dưới mặt sông băng Eyjafjallajokull ở Iceland vào ngày thứ tư (14/04/2010), hơn 90.000 chuyến bay ở châu Âu đã bị hủy. Đây cũng là một minh chứng về sự bất ổn của thiên nhiên có thể gây tổn hại tới công việc kinh doanh toàn cầu. Để giảm thiểu thiệt hại về kinh tế, cơ quan quản lý tối ưu hóa và lập lịch đường bay EuroControl cố gắng tiếp tục duy trì một số đường bay đi và đến Việt Nam, liên quan đến các thành phố lớn như: Hồ Chí Minh (A), Paris (B), Berlin (C), và London (D). Tuy nhiên, do ảnh hưởng của môi trường thiên nhiên nói trên, chỉ có một vài chuyến bay có thể hoạt động: từ A hướng đến B và D, từ B hướng đến C, từ C hướng đến A và D, từ D hướng đến B.
5 Tổng kết Thông qua các bài tập trong phần này, chúng ta đã làm quen với các định nghĩa, các tính chất, cũng như là các định lý trong lý thuyết đồ thị (tham khảo chi tiết trong chương 8). Ngoài ra, các bài tập |
