TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ths. Phạm Thanh An (2018)
Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 5: Đồ thị" cung cấp cho người học các kiến thức: Trình bày những kiến thức căn bản về lý thuyết đồ thị, cách biểu diễn, một số thuật toán trên đồ thị, đánh giá thuật toán, một số ứng dụng của đồ thị. | Ths. Phạm Thanh An Bộ môn Khoa học máy tính - Khoa CNTT Trường Đại học Ngân hàng Chương 5: ĐỒ THỊ Mục tiêu của chương Trình bày những kiến thức căn bản về lý thuyết đồ thị, cách biểu diễn, một số thuật toán trên đồ thị Đánh giá thuật toán Một số ứng dụng của đồ thị Định nghĩa Boston Hartford Atlanta Minneapolis Austin SF Seattle Anchorage Định nghĩa Đồ thị G = (V,E) V = tập hợp hữu hạn các phần tử (đỉnh hay nút) E V × V, tập hữu hạn các cạnh (cung) a b c d e Cung Đỉnh Các khái niệm Nếu (x,y) E x gọi là đỉnh gốc, y là ngọn Nếu x ≡ y, (x,y) gọi là khuyên Một dãy u1,u2, ,un, ui V (i=1,n) gọi là một đường, nếu (ui-1,ui) E Độ dài đường: length(u1,u2, ,un)=n (u1,u2, ,un) đường đi đơn, nếu ui≠uj, 1< i≠j
đang nạp các trang xem trước
