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.