Выпуклый подграф

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

В этом графе треугольник 1-2-5 выпуклый, но путь 2-3-4 выпуклым не является, поскольку он не включает один из двух кратчайших путей из 2 в 4.

Выпуклые подграфы играют важную роль в теории неполных кубов и медианных графов. В частности, в медианных графах выпуклые подграфы имеют свойство Хэлли — если элементы семейства выпуклых подграфов попарно пересекаются, то и всё семейство имеет непустое пересечение.