On finite convexity spaces induced by sets of paths in graphs

摘要

A finite convexity space is a pair (V,C) consisting of a finite set V and a set C of subsets of V such that Combining long solidus overlay∈C, V∈C, and C is closed under intersection. A graph G with vertex set V and a set P of paths of G naturally define a convexity space (V,C(P)) where C(P) contains all subsets C of V such that whenever C contains the endvertices of some path P in P, then C contains all vertices of P. We prove that for a finite convexity space (V,C) and a graph G with vertex set V, there is a set P of paths of G with C=C(P) if and only if every set S which is not convex with respect to C contains two distinct vertices whose convex hull with respect to C is not contained in S andfor every two elements x and z of V and every element y distinct from x and z of the convex hull of x,z with respect to C, the subgraph of G induced by the convex hull of x,z with respect to C contains a path between x and z with y as an internal vertex. Furthermore, we prove that the corresponding algorithmic problem can be solved efficiently.