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
Tài liệu HOT
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
0
Trang chủ
Công Nghệ Thông Tin
Hệ điều hành
Đồ án cơ sở -4
TAILIEUCHUNG - Đồ án cơ sở -4
Chứng minh. Trước tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ sử rằng ở một bước lặp nào đó các nhãn cố định cho ta độ dài các đường đi ngắn nhất từ s đến các đinh có nhãn cố định,ta sẽ chứng minh rằng ở lần lặp tiếp theo nếu đỉnh u* thu được nhãn cố định thì d(u*) chính là dọ dài đường đi ngắn nhất từ s đén u*. Kí hiệu S1 là tập các đỉnh có nhãn cố định, S2 là tập các đỉnh có nhãn tạm thời. | Chứng minh. Trước tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ sử rằng ở một bước lặp nào đó các nhãn cố định cho ta độ dài các đường đi ngắn nhất từ s đến các đinh có nhãn cố định ta sẽ chứng minh rằng ở lần lặp tiếp theo nếu đỉnh u thu được nhãn cố định thì d u chính là dọ dài đường đi ngắn nhất từ s đén u . Kí hiệu S1 là tập các đỉnh có nhãn cố định S2 là tập các đỉnh có nhãn tạm thời ở bước lặp đang thúc mỗi bước lặp nhãn tạm thời d v cho ta đoọdài của đường đi ngắn nhất từ s đến v chỉ qua những đỉnh nằm hoàn toàn trong tập sử rằn đường di ngắn nhất từ ú đến u không nằm tron trong tập S1 tức là nó đi qua ít nhất một đỉnh của tập z e S2 là đỉnh đầu tiên như vậy trên đường đi trọng số trên các cung là không âm nên đoạn đường từ s đến u cóđọ dài L 0 và d z d u - L d u . Bất đẳng thức này là mâu thuẫn với cách xác định đỉnh u là đỉnh có nhãn tạm thời nhỏ nhất. Vậy đường đin ngắn nhất từ s đến u phải nằm trọn trong tập S1 và vì thế d u là độ dài của ở lần lặp đầu tiên S1 s và sau mỗi lần lặp ta chỉ them vào S1 một đỉnh u nên giả thiết là d v cho độ dài đường đi ngắn nhất từ s đên v với mọi ve S1 là đúng với bước lặp đầu tiên .Theo qui nạp là suy ra thuật toán cho ta đường đi ngắn nhất từ s đến mọi đỉnh của đồ thị . Bây giờ sẽ đánh giá số phép toán cần thực hiện theo thuật toán. Ở mỗi bước lặp để tìm ra điểm u cần thực hiện O n phép toán để gán nhãn lại cũng cần thực hiện SVTH Nguyễn Công Hiếu_SBD 0041 - Trang 25 một số lượng phép toán cũng là O n .Thuật toán cần phải thực hiện n-1 bước lặp vậy thời gian tính toán của thuật toán là cỡ O n2 . Định lý được chứng minh. Khi đã tìm được độ dài đường đi ngắn nhất d v thì đưòng đi này có thể tìm dựa vào nhãn Trước v veV. Thí dụ 1 Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị ở hình sau 7 4 1 2 4 3 5 SVTH Nguyễn Công Hiếu_SBD 0041 - Trang 26 Kết quả tính toán theo thuật toán được trình bày trong bản dưới ước viết thành 2 phần của nhãn theo
Ðức Minh
83
8
pdf
Báo lỗi
Trùng lắp nội dung
Văn hóa đồi trụy
Phản động
Bản quyền
File lỗi
Khác
Upload
Tải xuống
đang nạp các trang xem trước
Bấm vào đây để xem trước nội dung
Tải xuống
TÀI LIỆU LIÊN QUAN
Bài giảng Lý thuyết đồ thị: Chương 0 - Giới thiệu môn học
12
178
2
ĐỀ THI MÔN TÓAN RỜI RẠC & LÝ THUYẾT ĐỒ THỊ LỚP: LT2011-Lần 1-Đề 1
2
161
1
ĐỀ THI MÔN TÓAN RỜI RẠC & LÝ THUYẾT DỒ THỊ LỚP: HC3CT-Lần 1-Đề 1
1
177
0
ĐỀ THI MÔN TÓAN RỜI RẠC & LÝ THUYẾT DỒ THỊ LỚP: HC3CT-Lần 1-Đề 2
1
141
0
ĐỀ THI MÔN TÓAN RỜI RẠC & LÝ THUYẾT DỒ THỊ LỚP: Học lại K4
1
130
0
Bài giảng Lý thuyết đồ thị: Chương 1 - Đại cương về đồ thị
39
162
1
giáo trình lý thuyết đồ thị
23
259
8
Bài giảng Lý thuyết đồ thị: Chương 2 - Biểu diễn đồ thị trên máy tính
32
208
2
Bài giảng Lý thuyết đồ thị: Chương 3 - Đồ thị Euler và đồ thị Hamilton
19
173
3
Bài giảng Lý thuyết đồ thị - Bài 1: Đại cương về đồ thị
39
191
1
TÀI LIỆU XEM NHIỀU
Một Case Về Hematology (1)
8
462065
59
Giới thiệu :Lập trình mã nguồn mở
14
23827
74
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
11126
536
Câu hỏi và đáp án bài tập tình huống Quản trị học
14
10371
458
Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”
3
9651
106
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8646
1148
Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức
16
8357
423
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7945
2249
Đề tài: Dự án kinh doanh thời trang quần áo nữ
17
6980
260
Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152
6754
1610
TỪ KHÓA LIÊN QUAN
Hệ điều hành
Lý thuyết đồ thị
tư tưởng cơ bản của lý thuyết đồ thị
nhà toán học lỗi lạc người Thụy Sĩ
bài toán nổi tiếng về các cái cầu ở thàng phố Konigsberg
đồ thị vô hướng
Bài giảng Lý thuyết đồ thị
Giới thiệu Lý thuyết đồ thị
Môn học Lý thuyết đồ thị
Đại cương Lý thuyết đồ thị
Hình thức thi Lý thuyết đồ thị
tài liệu về lý thuyết đồ thị
học lý thuyết đồ thị tốt
phương pháp học lý thuyết đồ thị
hàm trên đồ thị
Đại cương về đồ thị
Các mô hình đồ thị
Thuật ngữ cơ bản của đồ thị
Đường đi của đồ thị
Sự liên thông đồ thị
Biểu diễn đồ thị trên máy tính
Sự đẳng cấu của đồ thị
Phương pháp biểu diễn đồ thị
Biểu diễn đồ thị bằng ma trận kề
Đồ thị Euler
Đồ thị Hamilton
Chu trình Hamilton
Kiểm tra đồ thị Hamilton
Đơn đồ thị đặc biệt
Đồ thị bánh xe
Đồ thị con
Mô hình đồ thị
TÀI LIỆU MỚI ĐĂNG
HƯỚNG DẪN SỬ DỤNG PHẦN MỀM CAITA part 9
18
160
0
29-06-2024
Truyện kiếm hiệp - Duy ngã độc tôn phần 5/7
1
118
0
29-06-2024
Báo cáo khoa học: " Principaux critères économiques de gestion des forêts : analyse critique et comparative"
29
108
0
29-06-2024
Báo cáo nghiên cứu khoa học " HÃY LÀM CHO HUẾ XANH HƠN VÀ ĐẸP HƠN "
6
143
1
29-06-2024
ETHICAL CODE HANDBOOK: Demonstrate your commitment to high standards
7
119
0
29-06-2024
Báo cáo nghiên cứu khoa học " Vai trò chính quyền địa phương trong phát triển kinh tế : khu chuyên doanh gốm sứ ( Trung Quốc ) và Bát Tràng ( Việt Nam )("
11
187
1
29-06-2024
Báo cáo nghiên cứu khoa học " Đại hội XVI thông qua điều lệ Đảng cộng sản Trung Quốc những sửa đổi bổ sung mới "
4
135
0
29-06-2024
CUỘC KHÁNG CHIẾN CHỐNG THỰC DÂN PHÁP KẾT THÚC (1953 - 1954)_5
11
109
0
29-06-2024
Đề thi tuyển sinh Đại học năm 2011 môn tiếng Anh khối D - Mã đề 473
9
123
0
29-06-2024
Những loại nước uống làm răng xỉn màu
4
114
1
29-06-2024
TÀI LIỆU HOT
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7945
2249
Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152
6754
1610
Ebook Chào con ba mẹ đã sẵn sàng
112
4024
1301
Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1
62
5702
1194
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8646
1148
Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu
561
3641
666
Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân
122
3846
601
Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm
274
4406
545
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
11126
536
Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe
35
4293
483
Đã 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.