DAA - Bìa Vertex

Một đỉnh của đồ thị vô hướng G = (V, E) là một tập hợp con của các đỉnh V^' ⊆ V như vậy nếu cạnh (u, v) là một cạnh của G, sau đó một trong hai u trong V hoặc là v trong V^' hoặc cả hai.

Tìm một đỉnh có kích thước lớn nhất trong một đồ thị vô hướng đã cho. Lớp phủ đỉnh tối ưu này là phiên bản tối ưu hóa của một bài toán hoàn chỉnh NP. Tuy nhiên, không quá khó để tìm được một đỉnh gần như tối ưu.

APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G] 
while E' is not empty do 
   Let (u, v) be an arbitrary edge of E' c ← c U {u, v} 
   Remove from E' every edge incident on either u or v 
return c

Thí dụ

Tập hợp các cạnh của đồ thị đã cho là -

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}

Bây giờ, chúng ta bắt đầu bằng cách chọn một cạnh tùy ý (1,6). Chúng tôi loại bỏ tất cả các cạnh, hoặc là sự cố đối với đỉnh 1 hoặc 6 và chúng tôi thêm cạnh (1,6) để che đi.

Trong bước tiếp theo, chúng tôi đã chọn một cạnh khác (2,3) một cách ngẫu nhiên

Bây giờ chúng ta chọn một cạnh khác (4,7).

Chúng tôi chọn một cạnh khác (8,5).

Do đó, đỉnh của đồ thị này là {1,2,4,5}.

Phân tích

Dễ dàng nhận thấy rằng thời gian chạy của thuật toán này là O(V + E), sử dụng danh sách kề để đại diện E^'.