Lecture
The set TMX is called externally stable in the graph ( X, Γ ) if for each vertex of xpt there exists at least one image in the set T. The number b (G) = called the number of external stability.
Examples: how many queens can be put (fig.12) or other figures, so that all the board fields are under attack (5 queens, 8 rooks or elephants, 12 horses), how many observers to put at the intersections of streets, so that all crossroads are supervised.
There is a fairly simple algorithm for finding the minimum externally stable set. For the graph G = (X, D) (see Fig. 13a), we construct the graph ( X, , D ), where the mapping D of the set X to so that if y = x or y is a prototype of x (yql -1 x) (fig. 13b).
Next steps:
Let be - some graph. Subset of vertices called a set of external stability if
one)
2)
The power of the minimal set of external stability is called the number of external stability of the graph. . In order to find all the sets of external stability of the graph, it is necessary to find all the covers of the modified graph adjacency matrix. The modification is to add a single main diagonal.
Example
|
External stability sets:
Comments
To leave a comment
Discrete Math. Set theory. Graph theory. Combinatorics.
Terms: Discrete Math. Set theory. Graph theory. Combinatorics.