全弧搜索广义拟阵的构造

Construction of Searching-arc Greedoids

根据图论中有向树的性质,在此构造了一个由有向树中弧生成的广义拟阵——全弧搜索广义拟阵.另外还给出了一个构造此广义拟阵的方法——全弧搜索法.此法是根据深度优先来构造的,其可行集由两部分组成.第一部分是由从有向树的根到该有向树各个顶点的路上的弧集组成,另一部分是由第1部分中任意不同集合的并集组成.最后以实例说明了当所给的是一个非树的图时,由全弧搜索法生成的数学结构不是一个广义拟阵.

According to the properties of directed trees,this paper presents a new greedoid——Searching-arc greedoid which is generated from the set of arcs of a directed trees.In addition,it gives a method to produce this kind of greedoids,this way is called as Searching-arc method.Actually,it is come from the idea of way of Depth-First-Searching.The feasible sets of a Searching-arc greedoid is consisted by the two parts.The first part is the set of arcs which are born by the root walking to every vertex of this directed graph,and the second is consisted by all the unions of any different members in the set of first part.Finally,by two examples,it illustructes that the mathematical construction produced by searching arc method will not be pledged as a greedoid when the correspording graph is not a tree.