Convexity, distance invariants and longest paths in graphs

网络是交通、通信和计算机网络的有用模型。在这个方案中，我们感兴趣的是通过某个最优子网连接一个网络中的一组S节点的问题。这可以是(I)包含S的最短连通子网，即具有最小节点数，或(Ii)包含S的连通子网，其在以下意义上是最小的：如果从该子网中删除任何不在S中的节点，则这断开S。S相对于这两种连接S的最佳方式中的任一种的间隔由属于连接S的某个最短子网(或包含S的某个最小子网)的所有节点组成。一个节点集T是凸的或闭的，如果它包含对T的每个具有固定大小的子集S的区间。我们建议研究这些闭集具有一定性质的网络结构。

Networks are useful models for transportation, communication and computer networks. In this proposal we are interested in the problem of connecting a set S of nodes in a network by some optimal subnetwork. This could be (i) a shortest connected subnetwork containing S ,i.e., with the smallest number of nodes or (ii) a connected subnetwork containing S that is minimal in the sense that if any node not in S is deleted from the subnetwork, then this disconnects S. The interval for S with respect to either of these two optimal ways of connecting S consist of all nodes that belong to some shortest subnetwork connecting S (or some minimal subnetwork containing S). A set T of nodes is convex or closed if it contains the interval for every subset S of T having a fixed size. We propose to study structures of networks for which these closed sets have certain properties.