tailieunhanh - Bài giảng LÝ THUYẾT ĐỒ THỊ - CÂY

CÂY là đồ thị liên thông và không có chu trình RỪNG là một đồ thị gồm p thành phần liên thông, trong đó mỗi thành phần liên thông là một cây Lưu ý: cây không chứa khuyên và cạnh song song. Định lý: Một cây T gồm N đỉnh với N 2 chứa ít nhất hai đỉnh treo Xét đồ thị G gồm N đỉnh, các điều sau đây tương đương. Đồ thị G là cây. Giữa hai đỉnh bất kỳ của G, tồn tại duy nhất một dây chuyền nối chúng với nhau. G liên thông tối tiểu. Thêm một cạnh nối 2 đỉnh. | CÂY ntsonptnk@ ĐỊNH NGHĨA CÂY là đồ thị liên thông và không có chu trình RỪNG là một đồ thị gồm p thành phần liên thông, trong đó mỗi thành phần liên thông là một cây Lưu ý: cây không chứa khuyên và cạnh song song. Lý thuyết đồ thị - chương 2 – Nguyễn Thanh Sơn C A B D SỰ TỒN TẠI ĐỈNH TREO Định lý: Một cây T gồm N đỉnh với N 2 chứa ít nhất hai đỉnh treo Lý thuyết đồ thị - Nguyễn Thanh Sơn C A B D E F CÁC ĐỊNH NGHĨA TƯƠNG ĐƯƠNG Xét đồ thị G gồm N đỉnh, các điều sau đây tương đương. Đồ thị G là cây. Giữa hai đỉnh bất kỳ của G, tồn tại duy nhất một dây chuyền nối chúng với nhau. G liên thông tối tiểu. Thêm một cạnh nối 2 đỉnh bất kỳ của G thì G sẽ chứa một chu trình duy nhất. G liên thông và có n-1 cạnh G không có chu trình và có n-1 cạnh Lý thuyết đồ thị - Nguyễn Thanh Sơn CÂY TỐI ĐẠI Định nghĩa: Cho G=(X, E) là một đồ thị liên thông và T=(X, F) là một đồ thị bộ phận của G. Nếu T là cây thì T được gọi là một cây tối đại của G. Các tên gọi khác: cây khung, cây bao trùm, cây . | CÂY ntsonptnk@ ĐỊNH NGHĨA CÂY là đồ thị liên thông và không có chu trình RỪNG là một đồ thị gồm p thành phần liên thông, trong đó mỗi thành phần liên thông là một cây Lưu ý: cây không chứa khuyên và cạnh song song. Lý thuyết đồ thị - chương 2 – Nguyễn Thanh Sơn C A B D SỰ TỒN TẠI ĐỈNH TREO Định lý: Một cây T gồm N đỉnh với N 2 chứa ít nhất hai đỉnh treo Lý thuyết đồ thị - Nguyễn Thanh Sơn C A B D E F CÁC ĐỊNH NGHĨA TƯƠNG ĐƯƠNG Xét đồ thị G gồm N đỉnh, các điều sau đây tương đương. Đồ thị G là cây. Giữa hai đỉnh bất kỳ của G, tồn tại duy nhất một dây chuyền nối chúng với nhau. G liên thông tối tiểu. Thêm một cạnh nối 2 đỉnh bất kỳ của G thì G sẽ chứa một chu trình duy nhất. G liên thông và có n-1 cạnh G không có chu trình và có n-1 cạnh Lý thuyết đồ thị - Nguyễn Thanh Sơn CÂY TỐI ĐẠI Định nghĩa: Cho G=(X, E) là một đồ thị liên thông và T=(X, F) là một đồ thị bộ phận của G. Nếu T là cây thì T được gọi là một cây tối đại của G. Các tên gọi khác: cây khung, cây bao trùm, cây phủ Lý thuyết đồ thị - Nguyễn Thanh Sơn C A B D E F SỰ TỒN TẠI CỦA CÂY TỐI ĐẠI Định lý: Mọi đồ thị liên thông đều có chứa ít nhất một cây tối đại Lý thuyết đồ thị - Nguyễn Thanh Sơn C A B D E F XÁC ĐỊNH CÂY TỐI ĐẠI Lý thuyết đồ thị - Nguyễn Thanh Sơn Thuật toán tựa PRIM Input: đồ thị liên thông G=(X, E), X gồm N đỉnh Output: cây tối đại T=(V, U) của G Chọn tùy ý v X và khởi tạo V := { v }; U := ; Chọn w X \ V sao cho e E, e nối w với một đỉnh trong V V := V {w}; U := U {e} Nếu U đủ N-1 cạnh thì dừng, ngược lại lặp từ bước 2. XÁC ĐỊNH CÂY TỐI ĐẠI Lý thuyết đồ thị - Nguyễn Thanh Sơn C A B D E F V = {F, A, B, E, C, D} U = {FA, AB, BE, FC, ED} CÂY TỐI ĐẠI NGẮN NHẤT Định nghĩa: Cho G=(X, E) G được gọi là ĐỒ THỊ CÓ TRỌNG nếu mỗi cạnh của G được tương ứng với một số thực, nghĩa là có một ánh xạ như sau: L: E |R e | L(e) TRỌNG LƯỢNG của một cây T của G bằng với tổng trọng lượng các cạnh trong cây: L(T) = (e T)L(e) CÂY TỐI ĐẠI NGẮN NHẤT là cây tối đại có trọng lượng nhỏ nhất .