В метрике теории графов выпуклым подграфом неориентированного графа G называется подграф, который включает любой кратчайший путь в G между любыми двумя вершинами. Таким образом, это аналогично определению выпуклого множества в геометрии — такое множество содержит отрезок, соединяющий любые две точки множества.
Выпуклые подграфы играют важную роль в теории и медианных графов. В частности, в медианных графах выпуклые подграфы имеют — если элементы семейства выпуклых подграфов попарно пересекаются, то и всё семейство имеет непустое пересечение.
Ссылки . .
Категория:Теория графов