Tại sao thuật toán tham lam lại không tìm được tập hợp đồ thị độc lập tối đa?

Question

Cho một đồ thị G, tại sao sau thuật toán tham lam không được bảo đảm để tìm maximum independent set của G:

Greedy(G): 
S = {} 
While G is not empty: 
    Let v be a node with minimum degree in G 
    S = union(S, {v}) 
    remove v and its neighbors from G 
return S 

tôi tự hỏi ai đó có thể chỉ cho tôi một ví dụ đơn giản của một đồ thị mà thuật toán này không?

Answer 1

Tôi không chắc chắn đây là ví dụ đơn giản, nhưng đây là một trong những thất bại: http://imgur.com/QK3DC

Đối với bước đầu tiên, bạn có thể chọn B, C, D, F hoặc kể từ khi tất cả họ đều có trình độ 2. Giả sử chúng ta loại bỏ B và những người hàng xóm của nó. Điều đó lá F và D với mức độ 1 và E với mức độ 2. Trong hai bước tiếp theo, chúng tôi loại bỏ F và D và kết thúc với một kích thước thiết lập của 3, đó là tối đa.

Thay vào đó, giả sử bước đầu tiên, chúng tôi đã xóa C và các nước lân cận. Điều này khiến chúng ta với F, A và E, mỗi cái có kích thước bằng 2. Chúng ta lấy một trong hai thứ này, và đồ thị trống và giải pháp của chúng ta chỉ chứa 2 nút, như chúng ta đã thấy, không phải là tối đa .