tối thiểu vs đỉnh tối thiểu bao gồm

Question

Tôi đang học tập cho kỳ thi và một trong những câu hỏi mẫu như sau:

Vertex bìa: bìa đỉnh trong một đồ thị là một tập hợp các đỉnh sao cho mỗi cạnh có ít nhất một của hai điểm kết thúc trong tập hợp này.

Bìa đỉnh tối thiểu: bìa đỉnh MINIMUM trong biểu đồ là bìa đỉnh có số đỉnh nhỏ nhất trong số tất cả các đỉnh đỉnh có thể.

đỉnh tối thiểu bao gồm một đỉnh bìa tối thiểu trong một đồ thị là một trang bìa đỉnh đó không chứa khác cover đỉnh (xóa bất kỳ đỉnh từ tập sẽ tạo ra một tập các đỉnh đó không phải là một trang bìa đỉnh)

Câu hỏi : Nắp đỉnh tối thiểu không phải lúc nào cũng là bìa đỉnh tối thiểu. Chứng minh điều này với một ví dụ đơn giản.

Có ai có thể xoay quanh vấn đề này không? Tôi không thấy sự khác biệt giữa hai người. Quan trọng hơn, tôi đang gặp khó khăn khi hình dung nó.

Tôi thực sự hy vọng anh ấy sẽ không hỏi những câu hỏi kỳ lạ như câu hỏi này trong bài kiểm tra!

Answer 1

xem xét đồ thị

A --- B --- C 

B là cover đỉnh tối thiểu.

A, C là nắp đỉnh tối thiểu. Loại bỏ A hoặc C, bạn không phải là trái với một nắp đỉnh.

Answer 2

xem xét đồ thị vô hướng sau:

Tập hợp các đỉnh {2,4,5} là một tối thiểu bìa đỉnh của đồ thị. Tại sao? bởi vì nó là một bìa đỉnh (tất cả các cạnh được bao phủ) và không có các đỉnh đỉnh khác với ít đỉnh hơn.

Tập hợp các đỉnh {2,3,5,6,7} là tối thiểu bìa đỉnh. Tại sao? bởi vì nó là một bìa đỉnh và bất kỳ tập con không tầm thường nào của {2,3,5,6,7} không phải là một bìa đỉnh. Hãy thử xóa bất kỳ đỉnh nào từ {2,3,5,6,7} và thấy rằng bạn rời khỏi một cạnh chưa được khám phá. Điều làm cho nắp đỉnh tối thiểu là không có khả năng giảm nó. Bạn không thể làm cho các thiết lập nhỏ hơn nó đã và vẫn nhận được một bìa đỉnh (mà không cần chèn đỉnh cho nó).

Rõ ràng, nắp đỉnh tối thiểu đã cho không phải là đỉnh đỉnh tối thiểu vì bìa đỉnh tối thiểu có ba đỉnh và đỉnh đỉnh tối thiểu của chúng tôi có 5 đỉnh. Do đó, không phải mọi nắp đỉnh tối thiểu cũng là một đỉnh đỉnh tối thiểu.

Mỗi đỉnh đỉnh tối thiểu cũng là bìa đỉnh tối thiểu vì việc xóa các đỉnh khỏi đỉnh đỉnh tối thiểu sẽ dẫn đến một tập hợp các đỉnh có kích thước nhỏ hơn nắp tối thiểu. Do đó, bất kỳ tập con không tầm thường nào của một đỉnh đỉnh tối thiểu không phải là một đỉnh của đỉnh, và do đó một đỉnh đỉnh tối thiểu cũng rất nhỏ.