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.

Текущая версия от 16:31, 23 октября 2018

Bridgeмост.

1. A bridge of a cycle [math]\displaystyle{ C }[/math] is the shortest path in [math]\displaystyle{ C }[/math] joining nonconsecutive vertices of [math]\displaystyle{ C }[/math] which is shorter than both of the edges of [math]\displaystyle{ C }[/math] joining those vertices. Thus a chord is a bridge of length 1, and a graph is bridged iff every cycle of length at least 4 has a bridge.

2. A bridge of [math]\displaystyle{ G }[/math] is an edge whose removal disconnects [math]\displaystyle{ G }[/math].

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.