Tài liệu Về bài toán steiner

Mục lục Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Danh mục ký hiệu . . . . . . . . . . . . . . . . . . . . . . . . 1 3 Danh sách hình vẽ . . . . . . . . . . . . . . . . . . . . . . . . 5 Chương 1. LỊCH SỬ BÀI TOÁN STEINER 1.1. Lịch sử bài toán Steiner . . . . . . . . . . . . . 1.1.1. Bài toán Fermat - Torricelli - Napoleon 1.1.2. Bài toán Gauss . . . . . . . . . . . . . 1.1.3. Phát biểu bài toán Steiner cho n điểm . 1.2. Một số khái niệm bổ trợ . . . . . . . . . . . . 1.2.1. Đồ thị . . . . . . . . . . . . . . . . . . 1.2.2. Đồ thị có hướng và đồ thị vô hướng . . 1.2.3. Đỉnh kề . . . . . . . . . . . . . . . . . 1.2.4. Cạnh liên thuộc . . . . . . . . . . . . . 1.2.5. Đỉnh cô lập . . . . . . . . . . . . . . . 1.2.6. Bậc của đỉnh . . . . . . . . . . . . . . . 1.2.7. Hành trình, đường và chu trình . . . . . 1.2.8. Đồ thị có trọng số và không có trọng số 1.2.9. Đồ thị con . . . . . . . . . . . . . . . . 1.2.10. Đồ thị liên thông . . . . . . . . . . . . 1.2.11. Mạng . . . . . . . . . . . . . . . . . . . 1.2.12. Cây . . . . . . . . . . . . . . . . . . . . 1.2.13. Cây bao trùm . . . . . . . . . . . . . . 1.2.14. Cây bao trùm nhỏ nhất . . . . . . . . . 1.2.15. Tập lồi, bao lồi . . . . . . . . . . . . . . i 6 . . . . . . . . . . . . . . 6 6 . . . . . . . . . . . . . . 8 9 . . . . . . . 10 . . . . . . . 10 . . . . . . . 10 . . . . . . . 11 . . . . . . . 11 . . . . . . . 11 . . . . . . . 11 . . . . . . . 12 . . . . . . . 13 . . . . . . . 13 . . . . . . . 14 . . . . . . . 14 . . . . . . . 14 . . . . . . . 14 . . . . . . . 15 . . . . . . . 15 Chương 2. BÀI TOÁN STEINER VỚI KHOẢNG CÁCH EUCLIDE 2.1. Đồ thị Euclide . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Bài toán Steiner . . . . . . . . . . . . . . . . . . . . . . . . 2.3. Ý tưởng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Định nghĩa và kí hiệu . . . . . . . . . . . . . . . . . 2.3.2. Các loại cây . . . . . . . . . . . . . . . . . . . . . . 2.3.3. Các tính chất của cây Steiner . . . . . . . . . . . . 2.4. Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1. Bài toán Steiner trong trường hợp n = 3 . . . . . . . 2.4.2. Thuật toán tìm cây ngắn nhất cho ba điểm . . . . . 2.4.3. Thuật toán Melzak cho bốn điểm . . . . . . . . . . . 2.4.4. Thuật toán Melzak . . . . . . . . . . . . . . . . . . 2.5. Tỉ số Steiner (the Steiner ratio) . . . . . . . . . . . . . . . Chương 3. BÀI TOÁN STEINER VỚI KHOẢNG CÁCH CHỮ NHẬT 3.1. Một số khái niệm . . . . . . . . . . . . . . . . . . . . . . . 3.2. Bài toán Steiner với ba điểm và khoảng cách chữ nhật . . . 3.3. Điều kiện cần của bài toán Sn . . . . . . . . . . . . . . . . 3.4. Bài toán Steiner trong trường hợp n = 4 . . . . . . . . . . . 3.5. Bài toán Steiner trong trường hợp n = 5 . . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . ii 16 16 16 17 17 17 21 26 26 27 29 33 36 38 38 41 43 50 54 57 59 Lời nói đầu Giả sử chúng ta cần xây dựng một hệ thống giao thông nối tất các điểm quan trọng (bệnh viện, trường học,...) trong một khu đô thị mới. Vấn đề đặt ra là ta phải thiết kế sao cho hệ thống giao thông đó có độ dài ngắn nhất để tiết kiệm chi phí xây dựng, cũng như thuận tiện cho việc sử dụng sau này. Đây là một ví dụ của bài toán Steiner. Bài toán này còn được sử dụng để giải quyết nhiều vấn đề thực tế như xây dựng đường ống dẫn nước, mạng dây điện, mạng cáp quang internet,... Bài toán đặt ra là phải kết nối một số điểm cho trước trong mặt phẳng Euclide, cho phép thêm một số điểm để giảm thiểu tổng chiều dài (các điểm thêm vào được gọi là điểm Steiner ). Bài toán Steiner còn được mở rộng với khoảng cách chữ nhật (rectilinear distance) khi mà cạnh của mạng chỉ được phép đi theo chiều dọc hoặc chiều ngang hay nói cách khác chỉ gồm các đường thẳng song song với trục 0x, 0y . Bài toán Steiner với khoảng cách chữ nhật được ứng dụng trong trong công nghệ mạch. Luận văn Về bài toán Steiner có mục đích trình bày một số vấn đề cơ bản nhất của bài toán Steiner và gồm ba chương. Chương 1: Lịch sử bài toán Steiner. Chương này trình bày sự ra đời và phát triển của bài toán Steiner, một số kiến thức của lý thuyết đồ thị cần thiết phục vụ cho việc nghiên cứu và giải quyết bài toán Steiner. Chương 2: Bài toán Steiner với khoảng cách Euclide. Chương này trình bày hai thuật toán cơ bản để giải quyết bài toán Steiner là thuật toán ba điểm và thuật toán Melzak. Chương 3: Bài toán Steiner với khoảng cách chữ nhật (rectilinear distance). 1 Lời nói đầu Trình bày thuật toán giải bài toán Steiner với khoảng cách chữ nhật trong trường hợp số điểm cần kết nối nhỏ hơn hoặc bằng năm. Luận văn được hoàn thành tại Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, dưới sự hướng dẫn của PGS. TS. Tạ Duy Phượng. Đầu tiên tác giả xin trân trọng gửi lời cảm ơn đến các thầy cô giáo, các cán bộ công nhân viên của Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, những người đã giảng dạy và cung cấp những kiến thức khoa học quý báu trong những năm học vừa qua, để tôi có nền tảng kiến thức thực hiện luận văn này, cũng như đã quan tâm giúp đỡ tôi trong suốt quá trình học tập và nghiên cứu tại Viện. Đặc biệt, tác giả xin được bày tỏ lời cảm ơn sâu sắc tới thầy giáo hướng dẫn, PGS. TS. Tạ Duy Phượng, người đã tận tình chỉ bảo, giúp đỡ và tạo điều kiện về nhiều mặt để tác giả có thể hoàn thành luận văn này. Tác giả cũng xin bày tỏ lòng biết ơn tới lãnh đạo Khoa Khoa học tự nhiên, Ban Giám hiệu trường Đại học Thủ Dầu Một, Sở Nội vụ tỉnh Bình Dương đã tạo mọi điều kiện thuận lợi nhất giúp tôi hoàn thành khóa học. Tác giả cũng xin chân thành cảm ơn toàn thể gia đình, bạn bè, đồng nghiệp đã luôn động viên giúp đỡ trong suốt quá trình học tập. Hà Nội, ngày 15 tháng 08 năm 2014 Trần Lê Thủy 2 Danh mục ký hiệu pq hoặc pq Đoạn thẳng nối hai điểm p và q |x| Giá trị tuyệt đối của x \ AP D Góc AP D R2 Không gian Euclide hai chiều ∆abc Tam giác tạo bởi ba đỉnh a, b, c W P Tập hợp các điểm ai Tổng của các số ai i  Kết thúc chứng minh 3 Danh sách hình vẽ 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 Phương pháp Torricelli . . . . . . . . . . . . Phương pháp Simpson . . . . . . . . . . . . Bài toán Napoleon . . . . . . . . . . . . . . Mạng giao thông tối ưu nối bốn thành phố . Đồ thị có hướng . . . . . . . . . . . . . . . . Đồ thị vô hướng . . . . . . . . . . . . . . . . Đồ thị có chu trình . . . . . . . . . . . . . . Đồ thị con của một đồ thị . . . . . . . . . . Đồ thị liên thông và đồ thị không liên thông Mạng có chu trình . . . . . . . . . . Cấu hình giống nhau . . . . . . . . . Cấu hình khác nhau . . . . . . . . . Cây suy biến . . . . . . . . . . . . . Thu hẹp và phân chia. . . . . . . . . Điều kiện góc . . . . . . . . . . . . . Ví dụ trường hợp điểm Steiner bậc 2 Thuật toán ba điểm . . . . . . . . . . Chứng minh Định lý 2.4 . . . . . . . Vị trí và cấu hình ban đầu . . . . . . Thuật toán Melzak: Bước 1 . . . . . Thuật toán Melzak: Bước 2 . . . . . Thuật toán Melzak: Bước 3 . . . . . Thuật toán Melzak: Bước 4 . . . . . Thuật toán Melzak: Bước 4 . . . . . SMT và MST cho một tam giác đều 4 . . . . . . . . 6 . . . . . . . . . . . . . . . . 7 8 . . . . . . . . 9 . . . . . . . . 10 . . . . . . . . 11 . . . . . . . . 13 . . . . . . . . 13 . . . . . . . . 14 . . . . . . . . . . . . 17 . . . . . . . . . . . . 19 . . . . . . . . . . . . 19 . . . . . . . . . . . . 20 . . . . . . . . . . . . 20 . . . . . . . . . . . . 21 . . . . . . . . . . . . 22 . . . . . . . . . . . . 27 . . . . . . . . . . . . 29 . . . . . . . . . . . . 30 . . . . . . . . . . . . 30 . . . . . . . . . . . . 31 . . . . . . . . . . . . 31 . . . . . . . . . . . . 32 . . . . . . . . . . . . 33 . . . . . . . . . . . . 36 DANH SÁCH HÌNH VẼ 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 Khoảng cách chữ nhật khi quay trục tọa độ . . Hình chữ nhật bao . . . . . . . . . . . . . . . . Nghiệm bài toán S3 và P3 trùng nhau . . . . . . Điều kiện cần của nghiệm của Sn . . . . . . . . Chứng minh Bổ đề 3.2 . . . . . . . . . . . . . . Chứng minh Bổ đề 3.2 . . . . . . . . . . . . . . Chứng minh Bổ đề 3.2 . . . . . . . . . . . . . . Bài toán Steiner cho trường hợp n = 4 . . . . . . Ví dụ hình chữ nhật trong . . . . . . . . . . . . Bài toán Steiner cho trường hợp n = 4 . . . . . . Bài toán Steiner cho trường hợp n = 5 . . . . . . Bài toán Steiner cho trường hợp n = 5 . . . . . . Mạng giao thông kết nối 532 thành phố của nước 5 . . . . . . 39 . . . . . . 41 . . . . . . 43 . . . . . . 45 . . . . . . 47 . . . . . . 48 . . . . . . 49 . . . . . . 51 . . . . . . 52 . . . . . . 53 . . . . . . 55 . . . . . . 55 Mỹ . . . . 57 Chương 1 LỊCH SỬ BÀI TOÁN STEINER 1.1. Lịch sử bài toán Steiner 1.1.1. Bài toán Fermat - Torricelli - Napoleon Vào thế kỷ 17, nhà toán học Pháp Pierre de Fermat (1601 - 1665) đã đặt ra bài toán sau đây: “Cho trước ba điểm trong mặt phẳng. Hãy tìm điểm thứ tư sao cho tổng khoảng cách từ điểm này tới ba điểm cho trước là nhỏ nhất”. F D A P C B E Hình 1.1 Phương pháp Torricelli Bài toán của Fermat đã được Evangelista Torricelli (1608 - 1647) giải bằng phương pháp hình học vào khoảng năm 1640. Phương pháp của Torricelli như sau: 1. Cho 4ABC . Dựng các tam giác đều: 4ABD, 4BCE , 4ACF bên ngoài 4ABC . 2. Dựng các đường tròn ngoại tiếp các tam giác đều 4ABD, 4BCE , 4ACF . Ba đường tròn này cắt nhau tại một điểm, ký hiệu là P . Điểm P chính là điểm có tổng khoảng cách đến ba điểm A, B, C ngắn nhất. Điểm này được gọi là điểm Torricelli của 4ABC đã cho. 6 Chương 1. LỊCH SỬ BÀI TOÁN STEINER Bonaventura Francesco Cavalieri (1598 - 1667) trong cuốn sách “Exezcitationes geometricae” xuất bản năm 1647 đã chỉ ra rằng, điểm Torricelli P nhìn ba cạnh của 4ABC dưới các góc bằng 1200 . Thomas Simpson (1710 - 1761) đưa ra một phương pháp tìm điểm Torricelli vào năm 1750. Phương pháp của Simpson thực hiện bằng cách vẽ ba đường Simpson nối mỗi đỉnh của tam giác đều nằm ngoài 4ABC với đỉnh đối diện của 4ABC . Ba đường Simpson cắt nhau tại một điểm, điểm này cũng là điểm Torricelli. F D A P C B E Hình 1.2 Phương pháp Simpson Bài toán Fermat có liên hệ trực tiếp với định lý Napoleon sau đây. Định lý Napoleon Cho 4ABC . Về phía ngoài 4ABC dựng ba tam 0 0 0 giác đều M BCA , M ACB và M ABC . Khi đó tâm của ba tam giác đều 0 0 0 M BCA , M ACB và M ABC cũng tạo thành một tam giác đều và ba 0 0 0 đường thẳng AA , BB và CC đồng quy. Phải đến năm 1834 nhà toán học Franz Heinen mới đưa ra lời giải trọn vẹn cho bài toán Fermat như sau: 7 Chương 1. LỊCH SỬ BÀI TOÁN STEINER i) Nếu một trong các góc của 4ABC được tạo thành từ ba điểm A, B, C lớn hơn hoặc bằng 1200 thì lời giải bài toán Fermat là điểm trùng với đỉnh của góc lớn hơn hoặc bằng 1200 . ii) Nếu các góc của 4ABC nhỏ hơn 1200 thì lời giải bài toán Fermat là giao điểm của các đường Simpson hoặc điểm Torricelli và là điểm nhìn các cạnh của 4ABC với ba góc bằng 1200 . Ông cũng chỉ ra rằng tổng khoảng cách từ điểm Torricelli đến ba đỉnh của tam giác bằng độ dài của các đường Simpson. B0 C0 A P M F C B N A0 Hình 1.3 Bài toán Napoleon Bài toán Fermat đã được mở rộng bởi nhiều nhà toán học khác. Bài toán Fermat mở rộng Cho trước một tập hợp hữu hạn điểm trong mặt phẳng. Hãy tìm một điểm sao cho tổng khoảng cách từ điểm này tới các điểm cho trước là nhỏ nhất có thể. Điểm cần tìm được gọi là điểm Torricelli của hệ n điểm cho trước. Vào thế kỷ 19, Jacob Steiner (1796 - 1863) đã mở rộng bài toán của Fermat bằng cách cho phép thêm vào một số điểm phụ không thuộc tập các điểm đã cho. 1.1.2. Bài toán Gauss Các nhà nghiên cứu lịch sử toán học đã phát hiện ra rằng, Carl Friedrich Gauss (1777 - 1855) cũng đã biết đến bài toán Steiner. Năm 1836 trong 8 Chương 1. LỊCH SỬ BÀI TOÁN STEINER bức thư trả lời người bạn của mình là nhà thiên văn học Schumacher, Gauss có viết: “Nếu đề cập tới vấn đề kiến thiết một mạng giao thông tối ưu cho các đỉnh một tứ giác, thì ta gặp phải bài toán thật sự thú vị, mà tôi đã biết tới nó khi phải thiết kế các tuyến đường sắt nối các thành phố Harburg, Bremen, Hannover và Braunschweig. . . ”. Bài toán trên đã được Karl Bopp (1856 – 1905) giải quyết một cách triệt để vào năm 1879. Hệ thống đường sắt tối ưu được bổ sung thêm một điểm, là điểm Torricelli của tam giác với ba đỉnh là ba thành phố Harburg, Bremen, Hannover, và Braunschweig được nối với Hannover bởi một tuyến đường sắt chạy thẳng. Trong Hình 1.4, chúng ta thấy mô tả lời giải của bài toán này. Hurburg Bremen Hannover Braunschweig Hình 1.4 Mạng giao thông tối ưu nối bốn thành phố 1.1.3. Phát biểu bài toán Steiner cho n điểm Cuốn sách “What is Mathematics” của Robbins và Courant xuất bản năm 1941, đã phát biểu bài toán dưới đây. Bài toán Steiner cho n điểm Cho trước một tập hợp hữu hạn n điểm trên mặt phẳng (hoặc trong không gian metric nào đó), hãy tìm mạng giao thông nối các điểm này lại với nhau, cho phép thêm một số điểm mới, sao cho tổng độ dài của các đoạn thẳng nối các điểm là nhỏ nhất. Bài toán Steiner với ba điểm cho trước chính là một trường hợp riêng của bài toán Fermat. Nhưng bài toán Steiner cho bốn điểm không còn là bài toán Fermat cho bốn điểm nữa. 9 Chương 1. LỊCH SỬ BÀI TOÁN STEINER Chương 2 sẽ trình bày lời giải của bài toán Steiner cho trường hợp n = 3 và thuật toán Melzak giải bài toán Steiner cho n điểm bất kì. 1.2. Một số khái niệm bổ trợ 1.2.1. Đồ thị Định nghĩa 1.1. (xem [1], trang 9) Một đồ thị G bao gồm một tập hợp V , mà mỗi phần tử được gọi là đỉnh (hoặc nút) và một tập hợp E gồm các cặp hai đỉnh u và v dạng e = (u, v), được gọi là cạnh. Ký hiệu đồ thị G là G = (V, E). Tập V hữu hạn thì đồ thị G được gọi là đồ thị hữu hạn. Trong luận văn này ta quy ước khi nói đến đồ thị G thì G là đồ thị hữu hạn với số đỉnh của đồ thị là n, số cạnh là m, tức là |V | = n, |E| = m. 1.2.2. Đồ thị có hướng và đồ thị vô hướng Định nghĩa 1.2. (xem [1], trang 9) Giả sử u và v là hai đỉnh của đồ thị G = (V, E), nếu cặp (u, v) ∈ E có kể đến thứ tự u là đỉnh đầu, v là đỉnh cuối, thì ta gọi đó là đồ thị có hướng, khi đó mỗi cạnh e = (u, v) được gọi là một cung (Hình 1.5). Hình 1.5 Đồ thị có hướng Ngược lại, ta gọi đó là đồ thị vô hướng (hay đồ thị không có hướng) và (u, v) gọi là cạnh nối đỉnh u với v và cũng kí hiệu là e = (u, v) (Hình 1.6). Bằng hình vẽ ta có thể biểu diễn mỗi đỉnh của đồ thị bởi một điểm trên mặt phẳng, mỗi cạnh bởi một đường nối hai điểm tương ứng với hai đỉnh. 10 Chương 1. LỊCH SỬ BÀI TOÁN STEINER Hình 1.6 Đồ thị vô hướng Với đồ thị có hướng ta thêm vào cạnh một mũi tên hướng từ đỉnh đầu đến đỉnh cuối. 1.2.3. Đỉnh kề Định nghĩa 1.3. (xem [1], trang 9) Cho đồ thị G = (V, E) là đồ thị vô hướng và đỉnh x ∈ V , hai đỉnh nằm trên cùng một cạnh gọi là hai đỉnh kề nhau. Kí hiệu: V (x) là tập con của V , gồm những đỉnh kề với x. Trường hợp G là đồ thị có hướng, kí hiệu V + (x) = {y ∈ V : (x, y) ∈ E} là tập các đỉnh kề sau của x; V − (x) = {y ∈ V : (y, x) ∈ E} là tập các đỉnh kề trước của x. Chẳng hạn: Trong Hình 1.6 thì V (a) = {b, d, e} . 1.2.4. Cạnh liên thuộc Định nghĩa 1.4. (xem [1], trang 10) Cho u, v ∈ V và e = (u, v) ∈ E . Ta nói u, v là hai đỉnh kề nhau và cạnh e liên thuộc với hai đỉnh u và v . Ví dụ, cạnh (a, b) trong Hình 1.6 là cạnh liên thuộc với đỉnh a và đỉnh b. 1.2.5. Đỉnh cô lập Định nghĩa 1.5. (xem [3], trang 186) Đỉnh không liên thuộc với một cung (cạnh) nào được gọi là đỉnh cô lập. 1.2.6. Bậc của đỉnh Định nghĩa 1.6. (xem [1], trang 11) Với mỗi đỉnh v của đồ thị, ta định nghĩa bậc (degree) của đỉnh v là số cạnh liên thuộc với v hoặc số đỉnh kề với v và kí hiệu là d(v). 11 Chương 1. LỊCH SỬ BÀI TOÁN STEINER Trên đồ thị Hình 1.6 thì bậc của đỉnh a là 3 vì đỉnh a có các đỉnh kề là b, d, e. Định lý 1.1. (xem [1], trang 11) Giả sử G = (V, E) là đồ thị vô hướng m cạnh, khi đó tổng tất cả các bậc của đỉnh trong V của đồ thị được tính bằng công thức P d(v) = 2m. v∈V Chứng minh. Khi tính bậc của đỉnh, mỗi cạnh vô hướng hoặc có hướng được tính mỗi đầu đúng một lần, nên dễ dàng suy ra khẳng định trên.  1.2.7. Hành trình, đường và chu trình Định nghĩa 1.7. (xem [3], trang 193) Giả sử G = (V, E) là một đồ thị có hướng. Một hành trình có hướng trong G là một dãy v0 e1 v1 e2 v2 ...en vn sao cho với mọi i = 0, 1, ..., n, vi ∈ V , còn với mọi i = 1, ..., n, ei ∈ E và ei = (vi−1, vi ). Đỉnh v0 được gọi là đỉnh đầu, còn đỉnh vn được gọi là đỉnh cuối của hành trình có hướng trên. Định nghĩa 1.8. (xem [3], trang 193) Một hành trình vô hướng trong G là một dãy v0 e1 v1 e2 v2 ...en vn sao cho với mọi i = 0, 1, ..., n, vi ∈ V , còn với mọi i = 1, ..., n, ei ∈ E và hoặc ei = (vi−1, vi ) hoặc ei = (vi , vi−1 ). Đỉnh v0 được gọi là đỉnh đầu, còn đỉnh vn được gọi là đỉnh cuối của hành trình vô hướng trên. Định nghĩa 1.9. (xem [3], trang 193) Một hành trình (có hướng, vô hướng) được gọi là khép kín nếu đỉnh đầu và đỉnh cuối của nó trùng nhau. Định nghĩa 1.10. (xem [3], trang 194) Một hành trình được gọi là đường nếu các đỉnh của hành trình đó đều khác nhau. Định nghĩa 1.11. (xem [3], trang 194) Hành trình khép kín được gọi là chu trình, nếu hành trình đó có ít nhất ba cạnh và khi xóa đi đỉnh cuối thì trở thành đường. Ví dụ: {a, b, c, f, a} trong Hình 1.7 là một chu trình. Định nghĩa 1.12. (xem [3], trang 186) Cung dạng (a, a) với a ∈ V được gọi là khuyên. Ví dụ: Trong Hình 1.5 cung (d, d) là một khuyên. 12 Chương 1. LỊCH SỬ BÀI TOÁN STEINER a b c f e d Hình 1.7 Đồ thị có chu trình 1.2.8. Đồ thị có trọng số và không có trọng số Định nghĩa 1.13. (xem [1], trang 12) Đồ thị G mà mỗi cạnh của nó được gắn với một số không âm, thể hiện thông tin liên quan đến cạnh đó, được gọi là đồ thị có trọng số. Nói cách khác, đồ thị có trọng số nếu có ánh xạ l : E → R+ , trong đó E là tập các cạnh; R+ là tập số thực không âm; w = l(e) được gọi là trọng số của cạnh e ∈ E. Đồ thị mà mỗi cạnh không được gắn trọng số thì ta gọi là đồ thị không có trọng số. 1.2.9. Đồ thị con Định nghĩa 1.14. (xem [1], trang 14) Đồ thị con của đồ thị G là đồ thị mà tập đỉnh và các cạnh của nó là các tập con của các thành phần tương ứng của G. 1 2 3 6 5 4 Hình 1.8 Đồ thị con của một đồ thị Trong Hình 1.8 đồ thị H = (W, F ), trong đó W = {1, 2, 5, 6} và F = {(1, 2), (1, 6), (2, 5), (2, 6)} là đồ thị con của đồ thị G, bởi vì W ⊆ V , F ⊆ E. 13 Chương 1. LỊCH SỬ BÀI TOÁN STEINER Nhận xét 1.1. Cho G = (V, E) và tập V1 ⊂ V. Đồ thị con có tập đỉnh V1 và tập cạnh chứa tất cả các cạnh của G mà chúng nối hai đỉnh thuộc V1 được gọi là đồ thị con sinh bởi V1 . Trong Hình 1.8 đồ thị K = (A, B) trong đó A = {1, 2, 5, 6} và B = {(1, 2), (1, 6), (2, 5), (2, 6), (5, 6)} được gọi là đồ thị con sinh bởi A. 1.2.10. Đồ thị liên thông Định nghĩa 1.15. (xem [1], trang 15) Đồ thị G là liên thông nếu tìm được đường nối hai đỉnh bất kì trong đồ thị. Ngược lại, ta nói đồ thị G là không liên thông. 1 2 1 2 3 3 4 4 (a) 5 (b) Hình 1.9 Đồ thị liên thông và đồ thị không liên thông Hình 1.9(a) là đồ thị liên thông, còn Hình 1.9(b) là đồ thị không liên thông. 1.2.11. Mạng Định nghĩa 1.16. (xem [8], trang 46) Đồ thị hữu hạn, liên thông được gọi là mạng. 1.2.12. Cây Định nghĩa 1.17. (xem [1], trang 93) Một đồ thị vô hướng liên thông không có chu trình được gọi là cây. 1.2.13. Cây bao trùm Định nghĩa 1.18. (xem [3], trang 223) Giả sử G = (V, E) là đồ thị vô hướng liên thông. Khi đó đồ thị con T = {V 0 , E 0 } của G được gọi là cây bao trùm của G nếu T là một cây và V 0 = V . 14 Chương 1. LỊCH SỬ BÀI TOÁN STEINER 1.2.14. Cây bao trùm nhỏ nhất Định nghĩa 1.19. (xem [11], trang 7) Giả sử G(V, E) là một đồ thị hữu hạn, liên thông và mỗi cạnh có trọng số l(e) > 0 cho trước. Cây bao trùm nhỏ nhất (minimum spanning tree) của G(V, E) là cây bao trùm G0 (V, E 0 ) P sao cho tổng trọng số của các cạnh l(e) là bé nhất. e∈E 0 1.2.15. Tập lồi, bao lồi Kí hiệu En là không gian Euclide n−chiều với chuẩn Euclide kí hiệu là k·k. Cho hai điểm phân biệt p, q ∈ En . Đoạn thẳng nối hai điểm p và q , kí hiệu là pq , là tập tất cả các điểm x ∈ En có dạng x = (1 − λ)p + λq, 0 ≤ λ ≤ 1. Định nghĩa 1.20. (xem [12]) Tập W ⊂ En được gọi là một tập lồi nếu W chứa trọn đoạn thẳng nối hai điểm bất kì thuộc nó, tức là x1 , x2 ∈ W, suy ra x1 x2 ⊂ W. Định nghĩa 1.21. (xem [12]) Cho W ⊂ En . Bao lồi của W , kí hiệu là convW , là giao của tất cả các tập lồi trong En chứa W . 15 Chương 2 BÀI TOÁN STEINER VỚI KHOẢNG CÁCH EUCLIDE 2.1. Đồ thị Euclide Định nghĩa 2.1. (xem [11], trang 10) Khoảng cách Euclide giữa hai điểm x, y trong không gian Euclide là chiều dài đoạn thẳng nối giữa chúng. Nếu x = (x1 , x2 , ..., xn ) và y = (y1 , y2 , ..., yn ) là các điểm trong không gian Euclide n−chiều Rn thì khoảng cách giữa x và y được xác định bởi n q q X 2 2 (xi − yi )2 . d(x, y) =k (x − y) k= (x1 − y1 ) + ... + (xn − yn ) = i=1 Trong luận văn này ta chỉ xét trong không gian Euclide hai chiều R2 và khoảng cách giữa hai điểm trong mặt phẳng R2 được xác định bởi q d(x, y) =k (x − y) k= (x1 − y1 )2 + (x2 − y2 )2 . Định nghĩa 2.2. (xem [1], trang 93) Đồ thị Euclide là đồ thị có trọng số mà các đỉnh là các điểm trong không gian Euclide và trọng số của các cạnh nối giữa các đỉnh bằng khoảng cách Euclide giữa các đỉnh đó. Định nghĩa 2.3. (xem [1], trang 93) Cây bao trùm Euclide là một cây bao trùm trong đồ thị Euclide. Định nghĩa 2.4. (xem [1], trang 93) Cây bao trùm Euclide nhỏ nhất là cây bao trùm Euclide có tổng độ dài Euclide của các cạnh là nhỏ nhất. 2.2. Bài toán Steiner Cho trước một tập hợp hữu hạn n điểm trên mặt phẳng (hoặc trong không gian Euclide). Bài toán Steiner là bài toán xây dựng một mạng có các đỉnh là n điểm đã cho và một số điểm mới thêm vào sao cho tổng độ dài (Euclide) các cạnh của mạng là nhỏ nhất. 16 Chương 2. BÀI TOÁN STEINER VỚI KHOẢNG CÁCH EUCLIDE Định nghĩa 2.5. Một điểm không thuộc các điểm cho trước trong bài toán Steiner, tham gia vào quá trình xây dựng cây Steiner được gọi là điểm Steiner. 2.3. Ý tưởng 2.3.1. Định nghĩa và kí hiệu Sự khác biệt giữa cây bao trùm nhỏ nhất và nghiệm bài toán Steiner là cây bao trùm nhỏ nhất chỉ bao gồm các đỉnh là các điểm đã cho. Trong khi đó nghiệm của bài toán Steiner bao gồm các đỉnh ban đầu nhưng cũng có thể có các đỉnh thêm vào như là các đỉnh đặc biệt để làm cho tổng chiều dài nhỏ hơn. Lời giải của bài toán Steiner Euclide là một mạng T nối n điểm đã cho trong mặt phẳng Euclide gọi là điểm cuối (điểm terminals) mà ta kí hiệu là vi , i = 1, ..., n. Các đỉnh còn lại của T không phải là điểm đã cho thì được gọi là điểm Steiner, kí hiệu là Sj . 2.3.2. Các loại cây v1 v2 S v3 v4 Hình 2.1 Mạng có chu trình Định nghĩa 2.6. (xem [11], trang 25) Trong mặt phẳng cho n điểm. Mạng T kết nối các điểm đã cho ban đầu và các điểm Steiner thêm vào sao cho tổng độ dài các cạnh là nhỏ nhất được gọi là một cây Steiner ngắn nhất (Steiner minimal tree). Như vậy theo định nghĩa, cây Steiner ngắn nhất là một mạng (nối tất cả các điểm đã cho và điểm các điểm Steiner). Mạng 17 Chương 2. BÀI TOÁN STEINER VỚI KHOẢNG CÁCH EUCLIDE này phải là một cây, tức là nó phải là một đồ thị vô hướng, liên thông và không có chu trình.Ví dụ dưới đây giải thích rõ điều đó. Ví dụ 2.1. Cho mạng như trong Hình 2.1, trong đó v1 , v2 , v3 , v4 là các điểm cần kết nối, S là điểm Steiner thêm vào, mạng này có chu trình: v1 , S, v3 . Ta thấy nếu bỏ đi cạnh v1 v3 thì mạng thu được vẫn đảm bảo tính liên thông và có tổng độ dài ngắn hơn. Do đó từ nay về sau, khi nói đến mạng T ta sẽ coi nó là một cây. Việc đi tìm cây Steiner ngắn nhất cho n điểm nói chung là rất khó. Chúng ta chưa có quy tắc để xác định chính xác vị trí hình học của các điểm Steiner thêm vào để tạo ra một cây Steiner ngắn nhất. Các điểm Steiner đó được nối như thế nào với các đỉnh đã cho ban đầu và vị trí cụ thể của nó trong cây Steiner ra sao? Để giải quyết vấn đề này, ta chia bài toán thành những trường hợp nhỏ, tìm phương án tối ưu của từng trường hợp rồi sau đó tìm phương án tối ưu nhất trong các phương án vừa tìm được. Khi đó ta được cây Steiner ngắn nhất cần tìm. Ta đưa vào các khái niệm sau. Định nghĩa 2.7. (xem [7], trang 4) Cấu hình (topology) là đồ thị thể hiện sự kết nối giữa các điểm cuối và các điểm Steiner. Định nghĩa 2.8. Một cây ngắn hơn so với bất kỳ một cây khác trong cùng một cấu hình được gọi là cây tối thiểu tương đối (relatively minimal tree) cho cấu hình đó. Để tìm cây Steiner ngắn nhất, ta chia các phương án mà cách nối các điểm Steiner với các điểm ban đầu giống nhau (không quan tâm tới vị trí của các điểm Steiner hay không quan tâm độ dài các cạnh) là thuộc cùng một cấu hình (topology). Sau đó tìm một cây tối thiểu tương đối (a relatively minimal tree) cho cấu hình đó. Trong Hình 2.2(a) và 2.2(b) hai điểm v1 và v2 được nối với một điểm Steiner S1 , hai điểm v3 và v4 được nối với một điểm Steiner S2 và chúng được coi là có cấu hình giống nhau. Trong Hình 2.3(a) hai điểm v1 và v2 được nối với một điểm Steiner S1 , hai 18