Bài giảng "Thiết kế và đánh giá thuật toán: Đồ thị" cung cấp cho người học các kiến thức: Định nghĩa, biểu diễn đồ thị, tìm kiếm, sắp xếp topo. Đây là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn này và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu. | Thiết Kế & Đánh Giá Thuật Toán Đồ Thị TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung Định nghĩa Biểu diễn Tìm kiếm Sắp xếp topo 1 Định Nghĩa Đồ thị = ( , ) bao gồm Tập các đỉnh Tập ⊆ × cạnh Đồ thị vô hướng Cặp cạnh không có thứ tự , = ( , ) Đồ thị định hướng Cặp cạnh có thứ tự , ≠ , Cả hai trường hợp, ∈ ( ) Nếu liên thông, ≥ − 1 ⟹ log = log 2 Biểu Diễn Danh sách liền kề Mảng 1 chiều danh sách Mỗi danh sách cho một đỉnh bao gồm Các đỉnh sao cho , ∈ Ma trận liền kề Mảng 2 chiều × Đỉnh được đánh số 1, 2, , Giá trị 1 thể hiện có cạnh , ∈ 3 Biểu Diễn – Danh Sách Danh sách liền kề Mảng 1 chiều danh sách Mỗi danh sách cho một đỉnh bao gồm Các đỉnh sao cho , ∈ 1 2, 3 2! "3# 3! "# 4! .
