Reach-preservable graph
Перейти к навигации
Перейти к поиску
Reach-preservable graph --- сохраняющий достижимость граф.
Given a spanning tree [math]\displaystyle{ T }[/math] of a graph [math]\displaystyle{ G }[/math], a vertex [math]\displaystyle{ v \in V(G) }[/math] is called reach-preserving if the distance [math]\displaystyle{ d_{T}(v,w) = d_{G}(v,w) }[/math] for all [math]\displaystyle{ w }[/math] in [math]\displaystyle{ G }[/math]. A graph is called reach-preservable graph if each of its spanning trees has a reach-preserving vertex.
By definition, it is clear that all trees are reach-preservable, and any cycle is reach-preservable. Furthermore, we can deduce that connected unicyclic graphs are reach-presevable.