Английская Википедия:Boundary (graph theory)
Материал из Онлайн справочника
Шаблон:Short description In graph theory, the outer boundary of a subset Шаблон:Mvar of the vertices of a graph Шаблон:Mvar is the set of vertices in Шаблон:Mvar that are adjacent to vertices in Шаблон:Mvar, but not in Шаблон:Mvar themselves. The inner boundary is the set of vertices in Шаблон:Mvar that have a neighbor outside Шаблон:Mvar. The edge boundary is the set of edges with one endpoint in the inner boundary and one endpoint in the outer boundary.[1]
These boundaries and their sizes are particularly relevant for isoperimetric problems in graphs, separator theorems, minimum cuts, expander graphs, and percolation theory.
References
