论文标题
最终幻想跨越图中的树木，没有正常的跨越树
End-faithful spanning trees in graphs without normal spanning trees
论文作者
论文摘要
Schmidt通过顺序级别函数表征了无光线图的类别，这使得通过转夹诱导证明有关Rayless图的陈述成为可能。哈林询问施密特的等级函数是否可以推广以表征其他重要的图形类。我们在肯定中回答了哈林的问题。哈林（Halin）提出的另一个很大程度上开放的问题要求用最终幻想的跨越树来表征一类图表。良好的子类是由具有正常生成树的图形形成的。我们确定了一个较大的子类，即正常可追溯的图形类别，该类别由连接的图组成，并将无射线的树分解为正常跨度的部分。进一步研究了正常可追溯图的类别，我们证明，对于每个正常可追溯的图，拥有无射线的跨越树都等同于其所有末端的主导。我们的证明依赖于我们提供的顺序级别函数对正常可追溯图的表征。
Schmidt characterised the class of rayless graphs by an ordinal rank function, which makes it possible to prove statements about rayless graphs by transfinite induction. Halin asked whether Schmidt's rank function can be generalised to characterise other important classes of graphs. We answer Halin's question in the affirmative. Another largely open problem raised by Halin asks for a characterisation of the class of graphs with an end-faithful spanning tree. A well-studied subclass is formed by the graphs with a normal spanning tree. We determine a larger subclass, the class of normally traceable graphs, which consists of the connected graphs with a rayless tree-decomposition into normally spanned parts. Investigating the class of normally traceable graphs further we prove that, for every normally traceable graph, having a rayless spanning tree is equivalent to all its ends being dominated. Our proofs rely on a characterisation of the class of normally traceable graphs by an ordinal rank function that we provide.
