Аноним

Bridge: различия между версиями

Материал из WEGA
нет описания правки
(Новая страница: «'''Bridge''' --- мост. '''1.''' A '''bridge''' of a ''cycle'' <math>C</math> is the shortest path in <math>C</math> joining nonconsecutive vertices of <math>C<…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Bridge''' --- мост.  
'''Bridge''' — ''[[мост]].''


'''1.''' A '''bridge''' of a ''cycle'' <math>C</math> is the shortest path in <math>C</math> joining
'''1.''' A '''bridge''' of a ''[[cycle]]'' <math>C</math> is the shortest [[path]] in <math>C</math> joining
nonconsecutive vertices of <math>C</math> which is shorter than both of the edges
nonconsecutive vertices of <math>C</math> which is shorter than both of the [[edge|edges]]
of <math>C</math> joining those vertices. Thus a ''chord'' is a bridge of
of <math>C</math> joining those [[vertex|vertices]]. Thus a ''[[chord]]'' is a bridge of
length 1, and a graph is bridged iff every cycle of length at least 4
length 1, and a [[graph, undirected graph, nonoriented graph|graph]] is bridged iff every cycle of length at least 4
has a bridge.
has a bridge.


'''2.''' A '''bridge''' of <math>G</math> is an edge whose removal disconnects <math>G</math>.
'''2.''' A '''bridge''' of <math>G</math> is an edge whose removal disconnects <math>G</math>.
==Литература==
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.