Выпуклый подграф - Convex subgraph - Wikipedia

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

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

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

Рекомендации

• Bandelt, H.J .; Чепой, В. (2008), "Метрическая теория графов и геометрия: обзор", в Гудман, Дж. Э.; Пах, Дж.; Поллак, Р. (ред.), Обзоры по дискретной и вычислительной геометрии: двадцать лет спустя (PDF), Современная математика, 453, Провиденс, Род-Айленд: AMS, стр. 49–86..
• Имрих, Вильфрид; Клавжар, Санди (1998), "Лемма о выпуклости и процедуры расширения для двудольных графов", Европейский журнал комбинаторики, 19 (6): 677–686, Дои:10.1006 / eujc.1998.0229, МИСТЕР  1642702.