Dominating set, independent set, covering set

1. Definition

1.1 Dominating set

• Let undirected simple graph G = \lt V,E \gt, V^* \subseteq V , if \forall v_i \in V - V^*, \exists v_j \in V^* bring (v_i,V_j) \in E said V^* by G One of the Dominating set , said v_j control v_i.
• set up V* yes G The dominating set of , And V* Any true subset of is not a dominating set , said V* by Minimal dominating set .
• G The least dominating set of vertices of is called G Of The minimum dominating set .
• The number of vertices in the minimal dominating set is called G Of Dominant number , Write it down as \gamma_0(G), Short for \gamma_0​ .

1.2 Independent set

1.2.1 Point independent set

• Let undirected simple graph G = \lt V,E \gt, V^* \subseteq V , if V* Any two vertices in are not adjacent , said V* by G Of Point independent set , abbreviation Independent set .
• if V* Adding any other vertices to the is not an independent set , said V* by Maximal independent set .
• G The independent set of points with the largest number of vertices is called G Of The largest independent set of points .
• The number of vertices of the largest independent set is called G Of Point independent number , Write it down as \beta_0(G), Short for \beta_0.

1.2.2 Edge independent set

• Let undirected simple graph G = \lt V,E \gt, V^* \subseteq V , if E^* Any two edges in the are not adjacent , said E^* by G Of Edge independent set , Also known as G Of matching .
• If in G^* Add any edge to the , None of the resulting sets match , said E^* by Great match .
• G The match with the largest number of sides of is called The biggest match .
• The number of sides in the maximum match is called Edge independence number or Number of matches , Write it down as \beta_1(G), Short for \beta_1​ .
• set up M Figure G = \lt V,E \gt A match of ：

1. call M The edge in is Match side , be not in M The edge in is Unmatched edges .
2. The vertices associated with the matching edge are Saturation point , Vertices that are not associated with matching edges are Unsaturated point .
3. if G Every vertex in is a saturation point , said M by G Of Perfect match .
4. G The path in which matching edges and unmatched edges alternate is called Alternate paths , An alternate path where both the starting point and the focus are unsaturated points is called Augmented interleaved paths .
5. G A circle in which matching edges and unmatched edges alternate is called a circle Crisscross circle .

• set up G = \lt V_1,V_2,E \gt Is a bipartite graph , |V_1| \leq |V_2| ,M by G A match of and |M| = |V_1| , call M by V_1 To V_2 Of Perfect match .

1.3 Covering set

1.3.1 Point covering set

• Let undirected simple graph G = \lt V,E \gt, V^* \subseteq V , if \forall e \in E, \exists v \in V^* bring v And e Related to , said V^* by G Of Point covering set , Referred to as Point coverage , said v Cover e .
• set up V^* yes G Point coverage , if V^* Any true subset of is not a point covering , said V^* by Minima cover .
• G The point covering with the least number of vertices is called G Of Minimum point coverage .
• The number of vertices in the minimum point covering is called G Of The number of points covered , Write it down as \alpha_0(G), Short for \alpha_0 .

1.3.2 Edge covering set

• Let undirected simple graph G = \lt V,E \gt No outliers ,E^* \subseteq E, if \forall v \in V, \exists e \in E^* bring v And e Related to , said E^* by Edge covering set , Referred to as Edge covering , said e Cover v .
• set up E^* Cover edges , if E^* Any true subset of is not an edge covering set , said E^* by Minimal edge covering set .
• G The edge covering with the least number of edges is called G Of Minimum edge coverage .
• The number of edges in the minimum edge cover is called G Of The number of edge covers , Write it down as \alpha_1(G), Short for \alpha_1​ .

2. nature

• The maximal independent sets of undirected simple graphs are all minimal dominating sets .
• Let undirected simple graph G = \lt V,E \gt, V^* \subseteq V , be V^* by G If and only if \overline{V^*} = V - V^* by G Independent set of points .

inference

\begin{array}{c} \alpha_0 + \beta_0 = |V| \end{array}

• set up n Order graph G There are no outliers in ：

1. set up M by G A maximum match of , Yes G Each unsaturated point in the takes an edge associated with it , Form an edge set N, be W = M \cup N by G Minimum edge cover of .
2. set up W_1​ by G A minimum edge covering of , if W_1​ Remove one of the adjacent edges in the , Let the removed edge set be N_1, be M_1 = W_1 - N_1 ​ by G The maximum match of .
3. G Number of edge covers \alpha_1 And matching number \beta_1 Satisfy ：\alpha_1 + \beta_1 = n .

inference Set up a picture G No outliers ,M yes G A match of ,W yes G One edge of the cover , be |M| \leq |W|, And when the equal sign holds ,M yes G A perfect match for ,W yes G Minimum edge cover of .

• Bipartite graph G = \lt V_1,V_2,E \gt The complete match of is the maximum match , But maximum matching is not necessarily complete matching . When |V_1| = |V_2| when , A perfect match is a perfect match .
• ( The condition of dissimilarity )： Set bipartite graph G = \lt V_1,V_2,E \gt among |V_1| \leq |V_2| , be G in V_1 To V_2​ Complete matching of if and only if V_1​ In any k(k = 1,2,\cdots,|V_1|) A vertex is at least related to V_2 Medium k Two vertices are adjacent to each other .
• (t Conditions )： Set bipartite graph G = \lt V_1,V_2,E \gt If there are positive integers t, bring V_1 Each vertex in the is associated with at least t side , and V_2 At most... Are associated with each vertex in the t side , be G in V_1​ To V_2 Complete matching of .