Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 4: Khái niệm cơ bản về cây - Cao Thanh Tình

TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌCKHÁI NIỆM CƠ BẢN VỀ CÂY1Một số khái niệm cơ bảnCâyĐịnh nghĩa: Cây là một đồ thị vô hướng, liên thông và không có chu trình sơ cấpCây không có cạnh bội và khuyênCây là một đơn đồ thịVí dụ2Một số khái niệm cơ bảnRừngĐịnh nghĩa: Rừng là một đồ thị vô hướng và không có chu trìnhRừng có thể có nhiều thành phần liên thôngMỗi thành phần liên thông là một câyVí dụ3Một số khái niệm cơ bảnĐịnh lý (Điều kiện đủ của cây)Nếu mọi cặp đỉnh của một đồ thị vô hướng G luôn tồn tại một đường đi sơ cấp thì G là một câyChứng minhSV tham khảo tài liệu4Một số khái niệm cơ bảnCây có gốcĐịnh nghĩaMột cây với một đỉnh được chọn làm gốcĐịnh hướng các cạnh trên cây từ gốc đi raVí dụCùng một cây, nếu chọn gốc khác nhau thì cây có gốc thu được sẽ khác nhau5Một số khái niệm cơ bảnCây có gốcMột số khái niệmChaAnh emTổ tiênCon cháuLáĐỉnh trongCây conMứcChiều cao6Một số khái niệm cơ bảnĐịnh lý Daisy ChainT là đồ thị có n đỉnh. Các mệnh đề tương đương:T là một câyT không có chu trình và có n-1 cạnhT liên thông, mọi cạnh đều là cầuGiữa hai đỉnh bất kỳ của T luôn tồn tại một đường đi sơ cấp duy nhấtT không có chu trình và T U {e} có chu trìnhT liên thông và có n-1 cạnh 7Một số khái niệm cơ bảnCây m-phânĐịnh nghĩaCây m-phânCây có gốcTất cả các đỉnh trong có không quá m conCây m-phân đầy đủTất cả các đỉnh trong có không quá m conm=2: Cây nhị phân8Một số khái niệm cơ bảnCây m-phânVí dụT1: Cây nhị phân đầy đủT2: Cây tam phân đầy đủT3: Cây tứ phân (không đầy đủ)9Một số tính chất của câyTính chất 1Cây n đỉnh (n  2) có ít nhất 2 đỉnh treoTính chất 2Cây m-phân đầy đủ với i đỉnh trong cón = m.i + 1Tính chất 3i = (n -1)/ml = [(m - 1)n + 1] / ml = (m - 1)i + 1n = l + i10Phép duyệt Cây nhị phânĐịnh nghĩaDuyệt câyLiệt kê các đỉnh theo một thứ tự xác định, mỗi đỉnh một lầnThường được đỉnh nghĩa đệ quy cho các cây con3 phương pháp duyệt câyDuyệt tiền tự (Pre-Oder)Duyệt trung tự (In-Oder)Duyệt hậu tự (Post-Oder)11Phép duyệt Cây nhị phânĐịnh nghĩaDuyệt tiền tựDuyệt nút gốcDuyệt tiền tự con tráiDuyệt tiền tự con phải12312Phép duyệt Cây nhị phânĐịnh nghĩaDuyệt trung tựDuyệt trung tự con tráiDuyệt nút gốcDuyệt trung tự con phải21313Phép duyệt Cây nhị phânĐịnh nghĩaDuyệt hậu tựDuyệt hậu tự con tráiDuyệt hậu tự con phảiDuyệt nút gốc31214Phép duyệt Cây nhị phânĐịnh nghĩaVí dụDuyệt tiền tựA B D E C FDuyệt trung tựD B E A C FDuyệt hậu tựD E B F C AABCDEF15Ký pháp nghịch đảo Ba LanCây biểu thức số họcLà cây nhị phânMỗi nút trong biểu diễn cho toán tử 2 ngôi Biểu diễn cho biểu thức  E1  E2Con trái biểu diễn cho biểu thức E1Con phải biểu diễn cho biểu thức E2Mỗi nút lá biểu diễn cho một toán hạng16Ký pháp nghịch đảo Ba LanCây biểu thức số họcVí dụE = (2 + 3)*2 – (4 – 1)*(15/5)17Ký pháp nghịch đảo Ba LanCây biểu thức số họcDuyệt cây biểu thứcBiểu thức tiền tốBiểu thức trung tốBiểu thức hậu tô18Ký pháp nghịch đảo Ba LanCây biểu thức số họcKý pháp nghịch đảo Ba Lan (Reverse Polish Notation – RPN)Biểu thức ở dạng hậu tốVí dụ: 5 1 2 + 4 * + 3 –Sử dụng để tính giá trị biểu thức trên máy tínhTính từ trái qua phảiKhông sử dụng dấu ngoặcSử dụng Stack (ngăn xếp)19Ký pháp nghịch đảo Ba LanCây biểu thức số họcKý pháp nghịch đảo Ba Lan (Reverse Polish Notation – RPN)Thuật toán tính giá trị biểu thức RPNĐọc một ký hiệu (token)Nếu ký hiệu là một sốĐẩy vào StackNgược lại, ký hiệu là một toán tửLấy ra 2 toán hạng từ StackTính giá trị theo toán tử đối với 2 toán hạngĐẩy kết quả vào Stack20Ký pháp nghịch đảo Ba LanCây biểu thức số họcKý pháp nghịch đảo Ba Lan (Reverse Polish Notation – RPN)Ví dụ: Tính giá trị biểu thức5 1 2 + 4 * + 3 - 21Cây khung (Spanning Tree)Định nghĩaCây khung của đơn đồ thị G Đồ thị con của GChứa tất cả các đỉnh của GMột đồ thị có thể có nhiều cây khungVí dụ22Cây khung (Spanning Tree)Định lýMột đơn đồ thị là liên thông khi và chỉ khi nó có cây khungChứng minhÑôn giaûn23Cây khung (Spanning Tree)Cây khung nhỏ nhấtĐịnh nghĩaCây khung nhỏ nhất trong một đồ thị liên thông, có trọng số là một cây khung có tổng trọng số trên các cạnh là nhỏ nhấtĐịnh lýCho G = (V, E), X  Ve là cạnh có trọng số nhỏ nhất nối giữa X và V\X.  e là một cạnh trong cây khung nhỏ nhất.24Cây khung (Spanning Tree)Cây khung nhỏ nhấtThuật toán PrimPhân hoạch tập đỉnhTập các đỉnh thuộc cây đang xây dựngTập các đỉnh còn lạiXây dựng câyChọn một đỉnh chưa thuộc cây mà có khoảng cách gần cây đang xây dựng nhấtGhép vào cây cạnh ngắn nhất tìm đượcThuật toán dừng khi được n-1 cạnh25Cây khung (Spanning Tree)Cây khung nhỏ nhấtThuật toán PrimCho T là tập đỉnh gồm một đỉnh xTrong khi T có ít hơn n đỉnh, thực hiện việc sauTìm đỉnh u trong V \ T mà gần với T nhấtthêm đỉnh u vào T thêm cạnh uv vào cây với v  T là đỉnh gần u nhất 2627Cây khung (Spanning Tree)Cây khung nhỏ nhấtThuật toán PrimPhương pháp lân cận gần nhất (Gán nhãn)Khoảng cáchd(v, X) = min { d(v, x) | x  X } với v  XNhãn của đỉnhMỗi đỉnh v ta gắn một nhãn dvdv = d(v, T) với T là tập đỉnh của cây đang xây dựngMỗi bước ta tìm đỉnh u mà du = min {dv | v  T}Ghép uv vào cây TCập nhật lại dv với v  T28Cây khung (Spanning Tree)Cây khung nhỏ nhấtThuật toán PrimPhương pháp lân cận gần nhất (Gán nhãn)Bước 1: Khởi tạoVT = {s}; T = ; ds = 0; dv = w(s, v)Bước 2: Tìm cạnhTìm u mà du = min {dv | v  VT}VT = VT  {u}; T = T  {uv}Nếu VT  V thì dừngBước 3: Cập nhật nhãndv = min{ dv, w(u, v) } với V  VT2930Cây khung (Spanning Tree)Cây khung nhỏ nhấtThuật toán KruskalPhân hoạch tập đỉnhTập các đỉnh liên thông với một đỉnh được chọn trong cây đang xétTập các đỉnh còn lạiXây dựng câyChọn 1 cạnh e = uvNếu uv không liên thông với nhau trong cây đang xây dựng thì ghép cạnh này vào câyThuật toán dừng khi được n-1 cạnh31Cây khung (Spanning Tree)Cây khung nhỏ nhấtThuật toán KruskalSắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số.Khởi tạo tập cạnh T = Với mỗi cạnh e lấy theo thứ tự:Nếu các đầu mút của e không liên thông với nhau trong T thìThêm e vào T.Cây khung nhỏ nhất là T 3233Cây khung (Spanning Tree)Cây khung nhỏ nhấtVí dụ: Tìm cây khung nhỏ nhất của đồ thị sau5123462520142034Cây khung (Spanning Tree)Cây khung nhỏ nhấtVí dụ: Tìm cây khung nhỏ nhất35Cây khung (Spanning Tree)Cây khung nhỏ nhấtSo sánh Prim và KruskalPrim chọn cạnh có trọng số nhỏ nhất liên thuộc với một đỉnh đã thuộc câyKruskal chọn cạnh có trọng số nhỏ nhất miễn là không tạo ra chu trìnhThuật toán Prim hiệu quả hơn đối với các đồ thị dày (số cạnh nhiều)36Cây khung (Spanning Tree)Một số bài toán ứng dụngNối dây điệnTrong một mặt phẳng toạ độ cho N + 1 điểm, điểm đầu tiên chính là gốc tọa độ được coi là nguồn điện duy nhất mà từ đó ta nối dây cấp điện cho các nơi khác. Điểm thứ i trong N điểm còn lại có toạ độ là (Xi, Yi), là điểm đặt máy thứ i. Mỗi điểm đặt máy có thể lấy trực tiếp từ nơi cấp điện ban đầu hay gián tiếp qua một điểm đặt máy khác.Yêu cầu đưa ra phương án nối điện giữa các điểm để mọi nơi đặt máy đều có điện và tổng chiều dài dây cần thiết là ngắn nhất. 37Cây khung (Spanning Tree)Một số bài toán ứng dụngTheo thiết kế, một mạng giao thông gồm N nút. Biết trước chi phí để xây dựng đường hai chiều trực tiếp từ nút i đến nút j. Hai tuyến đường khác nhau không cắt nhau tại điểm không là đầu mút. Hiện đã xây dựng được K tuyến đường.Bài toán : Hệ thống đường đã xây dựng đã bảo đảm sự đi lại giữa hai nút bất kỳ chưa? Nếu chưa, hãy chọn một số tuyến đường cần xây dựng thêm sao cho:Các tuyến đường sẽ xây dựng thêm cùng với các đường đã xây dựng bảo đảm sự đi lại giữa hai nút bất kỳ.Tổng kinh phí xây dựng các tuyến đường thêm vào là ít nhất. 38