Bài giảng Thiết kế và đánh giá thuật toán: Đồ thị - TS. Lê Nguyên Khôi

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Thiết kế và đánh giá thuật toán: Đồ thị - TS. Lê Nguyên Khôi 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!  3# 4