Reach-preservable graph: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Reach-preservable graph''' --- сохраняющий достижимость граф. Given a '' spanning tree'' <math>T</math> of a graph <math>G</math>, a…») |
(нет различий)
|
Текущая версия от 13:31, 21 июня 2011
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.