Lý thuyết đồ thị - Lớp phủ
Đồ thị bao trùm là một đồ thị con chứa tất cả các đỉnh hoặc tất cả các cạnh tương ứng với một số đồ thị khác. Một đồ thị con chứa tất cả các đỉnh được gọi làline/edge covering. Một đồ thị con chứa tất cả các cạnh được gọi làvertex covering.
Bao phủ dòng
Cho G = (V, E) là một đồ thị. Một tập con C (E) được gọi là phủ dòng của G nếu mọi đỉnh của G là điểm trùng với ít nhất một cạnh trong C, tức là
deg (V) ≥ 1 ∀ V ∈ G
vì mỗi đỉnh được nối với đỉnh khác bằng một cạnh. Do đó nó có mức độ tối thiểu là 1.
Example
Hãy xem biểu đồ sau:
Các đồ thị con của nó có dòng bao phủ như sau:
C 1 = {{a, b}, {c, d}}
C 2 = {{a, d}, {b, c}}
C 3 = {{a, b}, {b, c}, {b, d}}
C 4 = {{a, b}, {b, c}, {c, d}}
Bao phủ dòng của 'G' không tồn tại nếu và chỉ khi 'G' có một đỉnh biệt lập. Đường bao của đồ thị có 'n' đỉnh có ít nhất [n / 2] cạnh.
Che phủ dòng tối thiểu
Một đường bao phủ C của đồ thị G được cho là cực tiểu if no edge can be deleted from C.
Example
Trong biểu đồ trên, các đồ thị con có dòng bao phủ như sau:
C 1 = {{a, b}, {c, d}}
C 2 = {{a, d}, {b, c}}
C 3 = {{a, b}, {b, c}, {b, d}}
C 4 = {{a, b}, {b, c}, {c, d}}
Ở đây, C 1 , C 2 , C 3 là độ phủ dòng tối thiểu, còn C 4 thì không vì chúng ta có thể xóa {b, c}.
Độ phủ dòng tối thiểu
Nó còn được gọi là Smallest Minimal Line Covering. Một đường bao phủ tối thiểu với số cạnh tối thiểu được gọi là phủ đường tối thiểu của 'G'. Số cạnh trong một dòng tối thiểu bao phủ trong 'G' được gọi làline covering numbercủa 'G' (α 1 ).
Example
Trong ví dụ trên, C 1 và C 2 là đường bao nhỏ nhất của G và α 1 = 2.
Mỗi lớp phủ dòng chứa một dòng tối thiểu.
Mỗi dòng bao phủ không chứa một dòng tối thiểu (C 3 không chứa bất kỳ dòng tối thiểu nào.
Không có dòng tối thiểu bao gồm một chu kỳ.
Nếu một dòng bao phủ 'C' không chứa đường dẫn có độ dài từ 3 trở lên, thì 'C' là một dòng tối thiểu bao phủ bởi vì tất cả các thành phần của 'C' là đồ thị hình sao và từ đồ thị hình sao, không có cạnh nào có thể bị xóa.
Phủ đỉnh
Cho 'G' = (V, E) là một đồ thị. Một tập con K của V được gọi là đỉnh bao của 'G', nếu mọi cạnh của 'G' là trùng với hoặc bao bởi đỉnh trong 'K'.
Example
Hãy xem biểu đồ sau:
Các đồ thị con có thể được suy ra từ đồ thị trên như sau:
K 1 = {b, c}
K 2 = {a, b, c}
K 3 = {b, c, d}
K 4 = {a, d}
Ở đây, K 1 , K 2 và K 3 có đỉnh, trong khi K 4 không có đỉnh nào vì nó không che cạnh {bc}.
Che phủ đỉnh tối thiểu
Một đỉnh 'K' của đồ thị 'G' được cho là đỉnh tối thiểu bao phủ nếu không có đỉnh nào có thể bị xóa khỏi 'K'.
Example
Trong đồ thị trên, các đồ thị con có đỉnh bao phủ như sau:
K 1 = {b, c}
K 2 = {a, b, c}
K 3 = {b, c, d}
Ở đây, K 1 và K 2 là đỉnh tối thiểu, trong khi ở K 3 , đỉnh 'd' có thể bị xóa.
Che phủ đỉnh tối thiểu
Nó còn được gọi là phủ đỉnh tối thiểu nhỏ nhất. Một đỉnh tối thiểu của đồ thị 'G' với số đỉnh tối thiểu được gọi là phủ đỉnh tối thiểu.
Số đỉnh trong một đỉnh tối thiểu của 'G' được gọi là số đỉnh của G (α 2 ).
Example
Trong đồ thị sau, các đồ thị con có đỉnh bao phủ như sau:
K 1 = {b, c}
K 2 = {a, b, c}
K 3 = {b, c, d}
Ở đây, K 1 là đỉnh tối thiểu của G, vì nó chỉ có hai đỉnh. α 2 = 2.