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

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

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

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

Ссылки

• Бандельт, Х.-Ю.; Чепой, В. (2008), «Метрическая теория графов и геометрия: обзор», в Гудмане, Дж. Э .; Пах, Дж .; Поллак Р. (ред.), Обзоры по дискретной и вычислительной геометрии: двадцать лет спустя (PDF) , Contemporary Mathematics, vol. 453, Провиденс, Род-Айленд: AMS, стр. 49–86 .
• Имрих, Вильфрид; Клавжар, Санди (1998), «Лемма о выпуклости и процедуры расширения двудольных графов», European Journal of Combinatorics , 19 (6): 677–686, doi : 10.1006/eujc.1998.0229 , MR   1642702 .