Reach-preservable graph

Материал из WEGA
Перейти к навигации Перейти к поиску

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.