Jump to content

Vertex separator

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Monkbot (talk | contribs) at 17:00, 11 December 2020 (Task 18 (cosmetic): eval 5 templates: del empty params (2×); hyphenate params (3×); cvt lang vals (1×);). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In graph theory, a vertex subset is a vertex separator (or vertex cut, separating set) for nonadjacent vertices and if the removal of from the graph separates and into distinct connected components.

Examples

A separator for a grid graph.

Consider a grid graph with r rows and c columns; the total number n of vertices is r*c. For instance, in the illustration, r = 5, c = 8, and n = 40. If r is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if c is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing S to be any of these central rows or columns, and removing S from the graph, partitions the graph into two smaller connected subgraphs A and B, each of which has at most n/2 vertices. If r ≤ c (as in the illustration), then choosing a central column will give a separator S with r ≤ √n vertices, and similarly if c ≤ r then choosing a central row will give a separator with at most √n vertices. Thus, every grid graph has a separator S of size at most √n, the removal of which partitions it into two connected components, each of size at most n/2.[1]

On the left a centered tree, on the right a bicentered one. The numbers show each node's eccentricity.

To give another class of examples, every free tree T has a separator S consisting of a single vertex, the removal of which partitions T into two or more connected components, each of size at most n/2. More precisely, there is always exactly one or exactly two vertices, which amount to such a separator, depending on whether the tree is centered or bicentered.[2]

As opposed to these examples, not all vertex separators are balanced, but that property is most useful for applications in computer science, such as the planar separator theorem.

Minimal separators

Let S be an (a,b)-separator, that is, a vertex subset that separates two nonadjacent vertices a and b. Then S is a minimal (a,b)-separator if no proper subset of S separates a and b. More generally, S is called a minimal separator if it is a minimal separator for some pair (a,b) of nonadjacent vertices. Notice that this is different from minimal separating set which says that no proper subset of S is a minimal (u,v)-separator for any pair of vertices (u,v). The following is a well-known result characterizing the minimal separators:[3]

Lemma. A vertex separator S in G is minimal if and only if the graph , obtained by removing S from G, has two connected components and such that each vertex in S is both adjacent to some vertex in and to some vertex in .

The minimal "(a,b)"-separators also form an algebraic structure: For two fixed vertices a and b of a given graph G, an (a,b)-separator S can be regarded as a predecessor of another (a,b)-separator T, if every path from a to b meets S before it meets T. More rigorously, the predecessor relation is defined as follows: Let S and T be two (a,b)-separators in 'G'. Then S is a predecessor of T, in symbols , if for each , every path connecting x to b meets T. It follows from the definition that the predecessor relation yields a preorder on the set of all (a,b)-separators. Furthermore, Escalante (1972) proved that the predecessor relation gives rise to a complete lattice when restricted to the set of minimal (a,b)-separators in G.

See also

Notes

  1. ^ George (1973). Instead of using a row or column of a grid graph, George partitions the graph into four pieces by using the union of a row and a column as a separator.
  2. ^ Jordan (1869)
  3. ^ Golumbic (1980).

References

  • Escalante, F. (1972). "Schnittverbände in Graphen". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 38: 199–220. doi:10.1007/BF02996932.
  • George, J. Alan (1973), "Nested dissection of a regular finite element mesh", SIAM Journal on Numerical Analysis, 10 (2): 345–363, doi:10.1137/0710032, JSTOR 2156361.
  • Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7.
  • Jordan, Camille (1869). "Sur les assemblages de lignes". Journal für die reine und angewandte Mathematik (in French). 70 (2): 185–190.
  • Rosenberg, Arnold; Heath, Lenwood (2002). Graph Separators, with Applications. Springer. doi:10.1007/b115747.