Hispanopedia Wiki
Articulo de referencia

Subgrafo convexo

En este gráfico, el triángulo 1-2-5 es convexo, pero el camino 2-3-4 no lo es, porque no incluye uno de los dos caminos más cortos de 2 a 4. En la teoría de grafos métricos , un...

Hispanopedia WikiContenido en espanolLectura gratuita
En este gráfico, el triángulo 1-2-5 es convexo, pero el camino 2-3-4 no lo es, porque no incluye uno de los dos caminos más cortos de 2 a 4.

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 en 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 recta entre cada par de sus puntos. [ 1 ]

Los subgrafos convexos desempeñan un papel importante en la teoría de cubos parciales y grafos medianos . En particular, en los grafos medianos, los subgrafos convexos poseen la propiedad de Helly : si una familia de subgrafos 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. [ 2 ]

Notas

  1. ↑ Bandelt y Chepoi (2008) , 1. Nociones básicas, subgrafos convexos e isométricos; Imrich y Klavžar (1998) , pág. 678.
  2. ↑ Bandelt y Chepoi (2008) , discusión posterior al Teorema 2.1.

Referencias

  • Bandelt, H.-J.; Chepoi, V. (2008), "Teoría de grafos métricos y geometría: una revisión" (PDF) , en Goodman, JE ; Pach, J .; Pollack, R. (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later , Contemporary Mathematics, vol.  453, Providence, RI: AMS, pp. 49–86 . .
  • Imrich, Wilfried; Klavžar, Sandi (1998), "Un lema de convexidad y procedimientos de expansión para grafos bipartitos", European Journal of Combinatorics , 19 (6): 677– 686, doi : 10.1006/eujc.1998.0229 , MR 1642702 .