Giáo trình toán rời rạc - chương I - Đại cương về đồ thị

Toán rời rạc là một lĩnh vực của toán học nghiên cứu về các đối tượng rời rạc. Mặc dù các đối tượng là rời rạc, không có ý nghĩa nhưng khi chúng ta liên kết các đối tượng rời rạc lại với nhau ta lại có được những thông tin rất lý thú và mang nhiều ý nghĩa.
Nội dung trích xuất từ tài liệu:
Giáo trình toán rời rạc - chương I - Đại cương về đồ thị BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA SƯ PHẠM BỘ MÔN TOÁN HỌC GIÁO TRÌNHTOÁN RỜI RẠC (Discrete mathematics) Biên soạn Th.s Bùi Anh Kiệt Th.s Trương Quốc Bảo Năm 2003 LỜI NÓI ĐẦU Toán rời rạc là một lĩnh vực của toán học nghiên cứu về các đối tượng rời rạc. Mặc dùcác đối tượng là rời rạc, không có ý nghĩa nhưng khi chúng ta liên kết các đối tượng rời rạc lạivới nhau ta lại có được những thông tin rất lý thú và mang nhiều ý nghĩa. Chúng ta sẽ sử dụngcông cụ của toán học rời rạc khi phải đếm các đối tượng, nghiên cứu mối quan hệ giữa các tậprời rạc, khi nghiên cứu các quá trình hữu hạn. Một trong những nguyên nhân chủ yếu làmtăng tầm quan trọng của toán rời rạc là việc lưu trữ và xử lý thông tin trên máy tính điện tử màbản chất là các quá trình rời rạc. Ba lĩnh vực có nhiều ứng dụng của toán học rời rạc là lýthuyết tổ hợp, hàm đại số logic (đại số Boole) và lý thuyết đồ thị. Các vấn đề về lý thuyết tổhợp, hàm đại số logic (đại số Boole) sẽ được trình bày trong các giáo trình khác. Trong phạmvi giáo trình này chúng tôi chỉ trình bày lĩnh vực có thể xem là quan trọng nhất và có nhiềuứng dụng nhất của toán học rời rạc là Lý thuyết đồ thị. Lý thuyết đồ thị được khai sinh kể từ công trình nghiên cứu về bài toán “7 cây cầuKönigsberg” của nhà toán học Leonhard Euler (1707 - 1783) được công bố vào năm 1736.Từ đó đến nay, đã có nhiều nhà toán học trên thế giới nghiên cứu làm cho lý thuyết đồ thịngày càng phong phú và có nhiều ứng dụng trong các lĩnh vực khác nhau như mạng điện tử,lý thuyết mã, vận trù học, kinh tế học,... Đặc biệt, trong khoảng vài chục năm trở lại đây, cùngvới sự ra đời của máy tính điện tử và sự phát triển nhanh chóng của Tin học, Lý thuyết đồ thịcàng được quan tâm nhiều hơn, đặc biệt là các thuật toán và ứng dụng trên đồ thị. Hiện nay,môn học này đã được xem là kiến thức cơ sở của khoa học máy tính. Giáo trình này được biên soạn từ bài giảng của các tác giả trong các năm qua ởTrường Đại học Cần thơ và các trung tâm đào tạo liên kết trong vùng Đồng bằng sông Cửulong, nhằm đáp ứng nhu cầu tài liệu tham khảo và học tập bằng tiếng Việt của sinh viên. Đâylà giáo trình dành cho sinh viên sư phạm Toán Tin, Toán nên hầu hết các vấn đề được trìnhbày đều được chứng minh chặt chẽ, rõ ràng. Đồng thời, cũng kèm theo một số thuật toán vàcác ứng dụng thực tế cũng như ứng dụng trên máy tính. Các sinh viên chuyên ngành Lý Tin,Tin học và Điện tử cũng có thể sử dụng giáo trình này như một tài liệu tham khảo hữu ích. Nội dung của giáo trình bao gồm các nội dung cơ bản nhất của lý thuyết đồ thị có kèmcác bài tập áp dụng và được chia làm 04 chương: Chương 1: Trình bày các thuật ngữ, định nghĩa và khái niệm cơ bản của đồ thị như đồthị vô hướng, có hướng, các loại đồ thị, đường đi, chu trình, tính liên thông, phương pháptổng quát để giải quyết một bài toán bắng lý thuyết đồ thị,... Chương 2: Trình bày các bài toán về đường đi Euler, Hamilton, các giải thuật tìmđường đi ngắn nhất như Dijkstra, Heterdetmin cùng một số ví dụ ứng dụng. Chương 3: Trình bày các vấn đề liên quan đến đồ thị phẳng và bài toán tô màu đồ thịcùng một số ứng dụng. Chương 4: Khảo sát tổng quát về cấu trúc cây và các vấn đề liên quan, đặc biệt là câynhị phân. Một số ứng dụng của cây trong tin học cũng được trình bày như các phép duyệt cây,cây biểu thức số học, ký pháp nghịch đảo Ba Lan (RPN), các thuật toán tìm cây phủ tối tiểu,... Cuối mỗi chương có phần bài tập giúp sinh viên rèn luyện và kiểm tra lại những kiếnthức đã được học. Một số vấn đề trong phần lý thuyết cũng còn để mở xem như phần bài tậptự giải của sinh viên. Do giới hạn về mặt thời gian (giáo trình được giảng dạy trong 45 tiết) nên chúng tôichỉ đề cập đến các vấn đề cơ bản nhất của lý thuyết đồ thị. Các vấn đề mở rộng và chuyên sâucủa lý thuyết của lý thuyết đồ thị sẽ được trình bày thêm trong quá trình giảng dạy trên lớp vàxem là các vấn đề mở cho sinh viên tự học, nghiên cứu thêm khi làm tiểu luận, luận văn tốtnghiệp. Tuy đã hết sức cố gắng, song với quỹ thời gian và kiến thức hạn chế chắc chắn giáotrình vẫn còn những vấn đề khiếm khuyết, chúng tôi rất mong nhận được sự đóng góp ý kiếnquý báu của quý thầy cô, bạn bè đồng nghiệp và các em sinh viên để giáo trình được hoànthiện hơn. Th.S. Bùi Anh Kiệt Th.S. Trương Quốc Bảo Cần thơ, tháng 12 năm 2003Chương I ĐẠI CƯƠNG VỀ ĐỒ THỊI. Các khái niệm cơ bản 1. Đồ thị Đồ thị (graph) G = (V,E) là một bộ gồm 2 tập hợp V và E, trong đó V ≠ ∅ các phần tửcủa V được gọi là các đỉnh (vertices), ...