Reach-preservable graph

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

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.