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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Bridged graph''' --- граф с мостами. A graph <math>G</math> is a '''bridged graph''' if each cycle <math>C</math> of length at least 4 contains two …»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Bridged graph''' --- граф с мостами.  
'''Bridged graph''' — ''[[граф с мостами]].''


A graph <math>G</math> is a '''bridged graph''' if each cycle <math>C</math> of length at least 4
A [[graph, undirected graph, nonoriented graph|graph]] <math>G</math> is a '''bridged graph''' if each [[cycle]] <math>C</math> of length at least 4
contains two vertices whose distance from each other in <math>G</math> is
contains two [[vertex|vertices]] whose distance from each other in <math>G</math> is
strictly less than that in <math>C</math>.
strictly less than that in <math>C</math>.
A graph is called '''bridged''' if every cycle of length at least 4
A graph is called '''bridged''' if every cycle of length at least 4
has a ''bridge''. Observe that in a bridged graph every cycle of
has a ''bridge''. Observe that in a bridged graph every cycle of
length 4 or 5 has a chord. Bridged graphs are in general not perfect,
length 4 or 5 has a chord. Bridged graphs are in general not perfect,
as the ''wheel'' <math>W_{7}</math> shows.
as the ''[[wheel]]'' <math>W_{7}</math> shows.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

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

Bridged graphграф с мостами.

A graph [math]\displaystyle{ G }[/math] is a bridged graph if each cycle [math]\displaystyle{ C }[/math] of length at least 4 contains two vertices whose distance from each other in [math]\displaystyle{ G }[/math] is strictly less than that in [math]\displaystyle{ C }[/math]. A graph is called bridged if every cycle of length at least 4 has a bridge. Observe that in a bridged graph every cycle of length 4 or 5 has a chord. Bridged graphs are in general not perfect, as the wheel [math]\displaystyle{ W_{7} }[/math] shows.

Литература

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