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.
MAO Hua
,
XIE Li-wei
. Construction of Searching-arc Greedoids[J]. Journal of Hebei University(Natural Science Edition), 2010
, 30(2)
: 133
-136
.
DOI: 10.3969/j.issn.1000-1565.2010.02.006
[1] KORTE B, LOV(A)SZ L, SCHRADER R. Creedoids [M]. Berlin Heidelberg:Springer-Verlag Berlin 1991.
[2] BJ(O)RNER A, ZIEGLER G M. Introduction to Greedoids [M]. Cambridge:Cambridge University Press 1992.
[3] KORTE B, LOV(A)SZ L. Greeds-a structural framework for the greedy algorithm [M]. New York:Academic Press, Inc 1984.
[4] 王树禾. 图论 [M]. 北京:科学出版社 2004.
[5] BANDY J A, MURTY U S R. Graph theory with applications [M]. New York:Elasevier Science Publishing Co Inc 1976.
[6] 刘桂真, 陈庆华. 拟阵 [M]. 长沙:国防科技大学出版社 1995.
