Giáo trình Đồ thị và các thuật toán - Chương 4: Cây

4.3.4 Thuật toán tìm tất cả các cây bao trùm Việc phân tích các mạch điện về cơ bản có thể đưa về bài toán tìm tất cả các cây bao trùm của đồ thị (xem [19]). Do tầm quan trọng của nó, có nhiều thuật toán khác nhau giải quyết bài toán này. Một trong những phương pháp là hoán đổi các chu trình như sau: Xuất phát từ một cây bao trùm T nào đó. Với mỗi cạnh không nằm trên cây T, khi thêm vào cây này sẽ tạo ra duy nhất một chu trình. Xóa bỏ một canh bất kỳ trong chu trình này sẽ cho ta một cây bao trùm mới. Do số các cây bao trùm là rất lớn thậm chí cả với những đồ thị nhỏ, tính hiệu quả của những thuật toán giải quyết bài toán rất quan trọng (xem [14]). Một tổng quan của các phương pháp này là một luận án tiến sĩ của Chase [12]. Chase đã chỉ ra rằng thuật toán đưa ra bởi Minty có hiệu quả nhất: liên tiếp thu gọn đồ thị bằng các phép toán xoá một cạnh và hợp nhất các định đầu cuối của nó. Từ các cây bao trùm của các đô thị thu gọn (mà nhỏ hơn rất nhiều) ta có thể dựng được tất cả các cây bao trùm của đồ thị ban đầu. Để bảo đảm thuật toán kết thúc, các đồ thị có kích thước dưới một ngirỡng cho trước sẽ không được thu gọn thêm; thay vào đó là các cây bao trùm của chúng được suy ra.