Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Công Nghệ Thông Tin
Cơ sở dữ liệu
Lecture Data structures and algorithms in Java (6th edition): Chapter 14.6 - Goodrich, Tamassia, Goldwasser
Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Data structures and algorithms in Java (6th edition): Chapter 14.6 - Goodrich, Tamassia, Goldwasser
Thúy Loan
97
10
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
This chapter provides knowledge of mst. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Minimum Spanning Tree 3/25/14 15:52 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Minimum Spanning Trees © 2014 Goodrich, Tamassia, Goldwasser Minimum Spanning Trees 1 Minimum Spanning Trees Spanning subgraph n ORD Subgraph of a graph G containing all the vertices of G Spanning tree n Spanning subgraph that is itself a (free) tree DEN Minimum spanning tree (MST) n q Spanning tree of a weighted graph with minimum total edge weight 10 1 PIT 9 6 STL 4 8 7 3 DCA 5 2 Applications n n Communications networks Transportation networks © 2014 Goodrich, Tamassia, Goldwasser DFW Minimum Spanning Trees ATL 2 1 Minimum Spanning Tree 3/25/14 15:52 Cycle Property Cycle Property: Let T be a minimum spanning tree of a weighted graph G n Let e be an edge of G that is not in T and C let be the cycle formed by e with T n For every edge f of C, weight(f) ≤ weight(e) Proof: n By contradiction n If weight(f) > weight(e) we can get a spanning tree of smaller weight by replacing e with f 6 2 9 3 e 8 Replacing f with e yields a better spanning tree 8 f 6 2 4 C 9 3 e 8 7 7 Minimum Spanning Trees 3 U f Partition Property: Consider a partition of the vertices of G into subsets U and V n Let e be an edge of minimum weight across the partition n There is a minimum spanning tree of G containing edge e Proof: n Let T be an MST of G n If T does not contain e, consider the cycle C formed by e with T and let f be an edge of C across the partition n By the cycle property, weight(f) ≤ weight(e) n Thus, weight(f) = weight(e) n We obtain another MST by replacing f with e 7 7 Partition Property n © 2014 Goodrich, Tamassia, Goldwasser 4 C n © 2014 Goodrich, Tamassia, Goldwasser 8 f V 7 4 9 5 2 8 8 3 e 7 Replacing f with e yields another MST U 2 Minimum Spanning .
TÀI LIỆU LIÊN QUAN
Lecture ECE 250 - Algorithms and data structures: Data structures and algorithms
Lecture Data Structures: Lesson 1
Lecture ECE 250 - Algorithms and data structures: Containers, relations, and abstract data types
Lecture ECE 250 - Algorithms and data structures: The tree data structure
Lecture Data structures and algorithms: Chapter 1 - Introduction
Lecture Data Structures and Algorithms - Chapter 0: Course Outline
Lecture Data Structures and Algorithms - Chapter 1: Introduction
Lecture Data Structures and Algorithms - Chapter 0: Course Outline (Dr. Nguyen Ho Man Rang)
Lecture Data Structures and Algorithms - Chapter 1: Introduction (Dr. Nguyen Ho Man Rang)
Lecture Data Structures: Lesson 5
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.