Reach-preservable graph: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''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.