subgrafo convexo
En la teoría de grafos métricos , un subgrafo convexo de un grafo no dirigido G es un subgrafo que incluye todos los caminos más cortos de G entre dos de sus vértices. Por lo tanto, es análogo a la definición de un conjunto convexo en geometría, un conjunto que contiene el segmento de línea entre cada par de sus puntos.
Los subgrafos convexos juegan un papel importante en la teoría de cubos parciales y gráficos medianos . En particular, en los gráficos medianos, los subgráficos convexos tienen la propiedad de Helly : si una familia de subgráficos convexos tiene la propiedad de que todas las intersecciones por pares son no vacías, entonces toda la familia tiene una intersección no vacía.
