Chương 5 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 và một số ứng dụng của đồ thị. để nắm bắt các nội dung chi tiết. | 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
