Cây

Định nghĩa

Cây là một đồ thị vô hướng liên thông, không có chu trình đơn. Rừng là đồ thị không có chu trình. Các thành phần liên thông của rừng là cây.

• Các tính chất của cây:
  • Cây có đỉnh thì có cạnh
  • Mỗi cạnh của cây đều là cầu
  • Hai đỉnh bất kì của cây được nối với nhau bằng một và chỉ một đường đi đơn
  • Khi thêm bất kì một cạnh nào, ta thu được một chu trình
• Cho đồ thị vô hướng, liên thông. Cây với được gọi là cây khung của đồ thị

Công thức Cayley

Số cây khung của đồ thị đỉnh là

Bài toán cây khung nhỏ nhất

• Xét đồ thị vô hướng có trọng số , trong đó trọng số cạnh được kí hiệu là . Ta cần tìm cây khung có tổng trọng số các cạnh là nhỏ nhất

Thuật toán Kruskal

• Xét
• Sắp xếp tập cạnh theo thứ tự tăng dần của trọng số
• Với mỗi cạnh trong , từ trọng số nhỏ đến lớn, bổ sung vào sao cho việc bổ sung không tạo thành chu trình
• Thuật toán kết thúc khi đã duyệt hết cạnh trong hoặc có cạnh
• Độ phức tạp: với là số cạnh của đồ thị
• Thuật toán Kruskal thường được dùng cho các đồ thị thưa

Thuật toán Prim

• Xét , với là một đỉnh bất kì của đồ thị
• Chọn cạnh sao cho là cạnh nhỏ nhất giữa một đỉnh trong tập và một đỉnh ngoài tập mà khi bổ sung vào không tạo ra chu trình
• Bổ sung cạnh vào T
• Thuật toán được lặp lại cho đến khi có đủ đỉnh và cạnh
• Độ phức tạp: với là số cạnh, là số đỉnh, thực hiện trên danh sách kề và đống nhị phân (binary heap)