Skip to content

23_KhaiNiemDoThi

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

23_KhaiNiemDoThi

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 

README.md

Chương 1: Khái niệm về đồ thị (Graph)

1.1. Định nghĩa đồ thị

  • Đồ thị là một cấu trúc rời rạc gồm các đỉnh và cạnh
  • Đỉnh (Vertex/Node): Các điểm trong đồ thị
  • Cạnh (Edge): Các đường nối giữa các đỉnh
  • Biểu diễn toán học: G = (V, E)
    • V: tập hợp các đỉnh
    • E: tập hợp các cạnh

1.2. Phân loại đồ thị

1.2.1. Theo hướng của cạnh

  • Đồ thị vô hướng (Undirected Graph)

    • Các cạnh không có hướng
    • (u,v) = (v,u)
    • Ví dụ: Mạng xã hội bạn bè

  • Đồ thị có hướng (Directed Graph)

    • Các cạnh có hướng
    • (u,v) ≠ (v,u)
    • Ví dụ: Mạng lưới giao thông một chiều

1.2.2. Theo trọng số của cạnh

  • Đồ thị không trọng số

    • Các cạnh không có giá trị
    • Chỉ quan tâm đến sự tồn tại của cạnh

  • Đồ thị có trọng số

    • Các cạnh có giá trị
    • Ví dụ: Khoảng cách, chi phí, thời gian

1.3. Các thuật ngữ trên đồ thị

  • Đỉnh kề (Adjacent Vertex)

    • Hai đỉnh được nối bởi một cạnh
    • Trong đồ thị có hướng: phân biệt đỉnh kề vào và ra

  • Đường đi (Path)

    • Dãy các đỉnh nối tiếp nhau bởi các cạnh
    • Độ dài đường đi: số cạnh trên đường đi

  • Chu trình (Cycle)

    • Đường đi đóng: đỉnh đầu trùng đỉnh cuối
    • Chu trình đơn: không đỉnh nào lặp lại (trừ đỉnh đầu/cuối)

  • Đồ thị liên thông (Connected Graph)

    • Tồn tại đường đi giữa mọi cặp đỉnh
    • Thành phần liên thông: tập con lớn nhất các đỉnh liên thông

1.4. Bậc của đỉnh

1.4.1. Trong đồ thị vô hướng

  • Bậc của đỉnh: số cạnh nối với đỉnh đó
  • Định lý bắt tay: tổng bậc các đỉnh = 2 × số cạnh
  • Đỉnh cô lập: bậc = 0
  • Đỉnh treo: bậc = 1

1.4.2. Trong đồ thị có hướng

  • Bậc vào (Indegree): số cạnh đi vào đỉnh
  • Bậc ra (Outdegree): số cạnh đi ra từ đỉnh
  • Bậc của đỉnh = bậc vào + bậc ra
  • Tổng bậc vào = Tổng bậc ra = số cạnh

1.5. Một số dạng đồ thị

1.5.1. Đồ thị đầy đủ

  • Mọi cặp đỉnh đều có cạnh nối
  • Số cạnh tối đa: n(n-1)/2 với n đỉnh
  • Mọi đỉnh có bậc n-1

1.5.2. Đồ thị phẳng

  • Có thể vẽ trên mặt phẳng
  • Không có cạnh nào cắt nhau
  • Công thức Euler: V - E + F = 2
    • V: số đỉnh
    • E: số cạnh
    • F: số mặt

1.5.3. Đồ thị hai phía

  • Tập đỉnh chia làm 2 phần
  • Các cạnh chỉ nối giữa 2 phần
  • Ứng dụng: Bài toán ghép cặp

1.5.4. Đồ thị cây

  • Đồ thị liên thông không có chu trình
  • Số cạnh = số đỉnh - 1
  • Tồn tại đường đi duy nhất giữa 2 đỉnh bất kỳ

Bài tập thực hành

  1. Cài đặt cấu trúc đồ thị cơ bản
  2. Kiểm tra tính liên thông của đồ thị
  3. Đếm số thành phần liên thông
  4. Kiểm tra đồ thị hai phía
  5. Kiểm tra đồ thị cây
  6. Tìm chu trình trong đồ thị
  7. Tính bậc của các đỉnh
  8. Kiểm tra đồ thị phẳng

Bài tập nâng cao

  1. Tìm cầu và khớp của đồ thị
  2. Kiểm tra đồ thị Euler
  3. Kiểm tra đồ thị Hamilton
  4. Tìm đường đi ngắn nhất
  5. Tìm cây khung nhỏ nhất
  6. Tô màu đồ thị