В метрике теории графов выпуклым подграфом неориентированного графа G называется подграф, который включает любой кратчайший путь в G между любыми двумя вершинами. Таким образом, это аналогично определению выпуклого множества в геометрии — такое множество содержит отрезок, соединяющий любые две точки множества.
Выпуклые подграфы играют важную роль в теории неполных кубов[en] и медианных графов. В частности, в медианных графах выпуклые подграфы имеют свойство Хэлли[en] — если элементы семейства выпуклых подграфов попарно пересекаются, то и всё семейство имеет непустое пересечение.
Ссылки
- H.-J. Bandelt, V. Chepoi. Surveys on Discrete and Computational Geometry: Twenty Years Later / Jacob E. Goodman, János Pach, R. Pollack. — Providence, RI: AMS, 2008. — Т. 453. — С. 49–86..
- Wilfried Imrich, Sandi Klavžar. A convexity lemma and expansion procedures for bipartite graphs // European Journal of Combinatorics. — Т. 19, вып. 6. — P. 677–686. — DOI:10.1006/eujc.1998.0229..
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .