Tóm tắt luận văn Thạc sĩ Toán học: Đồ thị phẳng và bài toán tô màu bản đồ

Luận văn với mục tiêu tìm hiểu và trình bày một số kiến thức cơ bản về đồ thị, đồ thị phẳng và các kết quả lý thuyết, các định lý liên quan đến bài toán tô màu (tô đỉnh, tô cạnh và tô diện - tô màu bản đồ) trên các loại đồ thị khác nhau, cách tô màu đỉnh, cạnh và diện dựa trên các kết quả lý thuyết đã có và đề cập một số ứng dụng thiết thực của bài toán tô màu trong thực tế.
Nội dung trích xuất từ tài liệu:
Tóm tắt luận văn Thạc sĩ Toán học: Đồ thị phẳng và bài toán tô màu bản đồ BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THĂNG LONG ĐINH THỊ DỊU - C01055 ĐỒ THỊ PHẲNG VÀBÀI TOÁN TÔ MÀU BẢN ĐỒ Chuyên ngành: Phương pháp toán sơ cấp Mã số: 8.46.01.13TÓM TẮT LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI - 2019 MỞ ĐẦU Các sơ đồ giao thông, sơ đồ mạng lưới thông tin hay sơ đồ tổchức của một cơ quan, trường học đã khá quen thuộc với nhiềungười. Đó là những hình ảnh sinh động và cụ thể của một kháiniệm toán học trừu tượng - khái niệm đồ thị. Có thể hiểu đơn giản đồ thị là một cấu trúc toán học rời rạc,bao gồm hai yếu tố đỉnh và cạnh, cùng mối quan hệ giữa chúng.Đồ thị là một mô hình toán học cho nhiều vấn đề lý thuyết vàthực tiễn đa dạng. Lý thuyết đồ thị đề cập tới nhiều bài toán có ý nghĩa thựctiến thiết thực, cùng nhiều phương pháp xử lý và thuật toán giảiđộc đáo hiệu quả, giúp ích cho sự phát triển tư duy toán học nóichung và khả năng vận dụng trong cuộc sống thường ngày nóiriêng. Chủ đề về đồ thị còn có trong các đề thi Olympic về toánhọc ở một số nước. Đồ thị phẳng và bài toán tô màu bản đồ là một trong nhữngchủ đề quan trọng và hấp dẫn của lý thuyết đồ thị. Bài toán tômàu cho đồ thị có nhiều tác dụng trong khoa học và đời sống,được nhiều người quan tâm nghiên cứu và vận dụng. Chẳng hạntô màu bản đồ, xếp lịch học tập, lập kho chứa hóa chất, thiếtkế các bản mạch điện tử, bố trí các trạm truyền tin, xác lập cáctuyến xe buýt thành phố, v.v... Đề tài luận văn cao học: Đồ thị phẳng và bài toán tô màu bản đồnhằm mục đích tìm hiểu và trình bày một số kiến thức cơ bảnvề đồ thị, đồ thị phẳng và các kết quả lý thuyết, các định lý liênquan đến bài toán tô màu (tô đỉnh, tô cạnh và tô diện - tô màubản đồ) trên các loại đồ thị khác nhau, cách tô màu đỉnh, cạnhvà diện dựa trên các kết quả lý thuyết đã có và đề cập một sốứng dụng thiết thực của bài toán tô màu trong thực tế. Nội dung luận văn được viết trong ba chương. 1Chương 1Đồ thị phẳng và tínhchất Chương này trình bày một số kiến thức cơ bản về đồ thị và đồthị phẳng. Mục 1.1 nhắc lại các khái niệm dùng trong lý thuyếtđồ thị và các phép toán trên đồ thị. Mục 1.2 nêu khái niệm vềđồ thị phẳng, tính chất đặc trưng của các đồ thị phẳng. Trongchương dẫn ra nhiều ví dụ minh họa các khái niệm và kết quả đãtrình bày1.1 Khái niệm cơ bản về đồ thị1.1.1 Đồ thị vô hướng Trong thực tế ta thường gặp các sơ đồ giao thông (Hình 1.1)hay sơ đồ mạch điện (Hình 1.2). Các sơ đồ này được khái quátthành một sơ đồ vẽ ở Hình 1.34. Hình 1.1: Sơ đồ Hình 1.2: Sơ đồ Hình 1.3: Đồ thị đại khu phố mạch điện diện 2 Từ đó ta đi tới định nghĩa sau.Định nghĩa 1.1. Đồ thị là một tập hợp hữu hạn và khác rỗngcác điểm, gọi là đỉnh, và một tập hợp các đoạn (thẳng hay cong)nối liền một số cặp điểm này, gọi là cạnh của đồ thị (số cạnhcó thể bằng 0). Mỗi đỉnh của đồ thị thường được ký hiệu bằng một chữ cái(a, b, c . . .) hoặc một chữ số (1, 2, 3, . . .). Cạnh nối đỉnh i và đỉnhj (i 6= j) được ký hiệu là (i, j) hoặc (j, i). Một đồ thị như thếcòn có tên gọi là đồ thị vô hướng và thường được ký hiệu bằngmột chữ cái in hoa (có thể kèm theo chỉ số), như G, G1 , G2 , H,K, N ,. . . Nếu đồ thị G có tập đỉnh là V và tập cạnh là E ⊆ V × Vthì ta viết G = (V, E). Ta dùng ký hiệu n = |V | là số đỉnh vàm = |E| là số cạnh của đồ thị (n > 0, m ≥ 0). Để dễ hình dung, mỗi đồ thị thường được biểu diễn bởi mộthình vẽ trên mặt phẳng. Chẳng hạn, Hình 1.3 biểu diễn một đồthị có 5 đỉnh: a, b, c, d, e và 8 cạnh: (a, b), (a, d), (a, e), (b, c),(b, d), (b, e), (c, d) và (d, e). Chú ý rằng điểm cắt nhau của haicạnh (a, d) và (b, e) trong hình vẽ không phải là một đỉnh củađồ thị. Đỉnh i gọi là kề đỉnh j nếu có một cạnh của đồ thị nối i vớij. Nếu ký hiệu cạnh này là e thì ta viết e = (i, j) và nói cạnh eliên thuộc đỉnh i và đỉnh j. Ta cũng nói i và j là hai đầu mútcủa e. Cạnh e và e0 gọi là kề nhau nếu e, e0 có chung đỉnh.Định nghĩa 1.2. Bậc của một đỉnh v trong đồ thị là số cạnhliên thuộc nó, ký hiệu là ρ(v). Đỉnh có bậc 0 gọi là đỉnh cô lập,đỉnh có bậc 1 gọi là đỉnh treo. Ví dụ trong đồ thị vẽ ở Hình 3ta có ρ(a) = ρ(e) = 3, ρ(b) = ρ(d) = 4, ρ(c) = 2. Dễ dàng chứng minh: Trong một đồ thị vô hướng, tổng số bậccủa mọi đỉnh bằng hai lần số cạnh của đồ thị và số đỉnh có bậclẻ bao giờ cũng là một số chẵn. Cùng với bậc của đỉnh, ta còn dùng các khái niệm sau:+ Bậc nhỏ nhất của G là số δ(G) := min{ρ(v)|v ∈ V }. 3+ Bậc lớn nhất của G là số ∆(G) := max{ρ(v)|v ∈ V }.+ Bậc trung bình của G là số X 2m d(G) := |V1 | ρ(v) = (trong đó n = |V |, m = |E|) n v∈V Rõ ràn ...