Thuật toán mục đích chung cho triangulating một đồ thị vô hướng?

Question

Tôi đang chơi xung quanh với việc thực hiện thuật toán cây giao nhau để truyền bá niềm tin trên Mạng Bayesian. Tôi đang đấu tranh một chút với hình tam giác đồ thị để các cây giao nhau có thể được hình thành.

Tôi hiểu rằng việc tìm kiếm hình tam giác tối ưu là NP-hoàn chỉnh, nhưng bạn có thể chỉ cho tôi một thuật toán mục đích chung dẫn đến một tam giác đủ tốt cho các mạng Bayesian tương đối đơn giản không?

Đây là một bài tập học tập (sở thích, không phải bài tập về nhà), vì vậy tôi không quan tâm nhiều về không gian/thời gian phức tạp miễn là thuật toán dẫn đến đồ thị tam giác. Cuối cùng, tôi đang cố gắng hiểu các thuật toán suy luận chính xác hoạt động như thế nào trước khi tôi thử làm bất kỳ loại xấp xỉ nào.

Tôi đang tìm kiếm trong Python bằng cách sử dụng NetworkX, nhưng bất kỳ mô tả mã giả nào của thuật toán như vậy đều sử dụng thuật ngữ truyền tải đồ thị điển hình sẽ có giá trị.

Cảm ơn!

Answer 1

Nếu Xi là một biến thể (node) được xóa sau đó,

• S (i) sẽ được kích thước của bè lũ tạo ra bằng cách xóa biến
• C (i) đây sẽ là tổng kích thước của bè phái của đồ thị con do Xi và các nút lân cận của nó

Heuristic:

trong mỗi trường hợp chọn một Xi biến trong những tập hợp các biến thể được de leted với tối thiểu S (i)/C (i)

tham khảo: Heuristic Algorithms for the Triangulation of Graphs