Граница (теория графов)
 | Эта статья в значительной степени или полностью опирается на один источник . ( апрель 2024 г. ) |
В теории графов внешней границей подмножества S вершин , графа G G является множество вершин в S. которые смежны с вершинами в S , но не в самих Внутренняя граница — это набор вершин в S у которых есть сосед вне S. , Граница ребра — это набор ребер с одной конечной точкой на внутренней границе и одной конечной точкой на внешней границе. [1]
Эти границы и их размеры особенно актуальны для изопериметрических задач на графах , теорем о сепараторах , минимальных разрезах , графах-расширителях и теории перколяции .
Ссылки
[ редактировать ]- ^ Бенджамини, Итай (2013), Грубая геометрия и случайность: Летняя школа вероятностей Saint-Flour XLI – 2011 , лектор. Примечания Матем., вып. 2100, Чам: Спрингер, с. 2, номер домена : 10.1007/978-3-319-02576-6 , ISBN 978-3-319-02575-9
 | Эта теории графов статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |