Английская Википедия: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

Шаблон:Reflist


Шаблон:Graph-stub