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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Connected graph''' - связный граф)
 
Нет описания правки
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
'''Connected graph''' - [[связный граф|связный граф]]
'''Connected graph''' — ''[[связный граф]].''
 
A [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> is a '''connected graph''' if for all <math>\,u,v \in V(G)</math>, <math>\,u \neq v</math>, there is a ''[[chain]]'' <math>\,(v_{1}, \ldots, v_{k})</math> in <math>\,G</math> with <math>\,\{v_{1},
v_{k}\} = \{u,v\}</math>, (the chain connects <math>\,u</math> and <math>\,v</math>). Otherwise, the graph is called '''[[disconnected graph|disconnected]]'''.
 
A graph <math>\,G = (V,E)</math> is '''[[maximum edge-connected graph|maximum edge-connected]]''' (in short, '''max'''-<math>\,\lambda</math>) if <math>\,\lambda = [2q/p]</math>, where <math>\,p = |V|, \; q = |E|</math> and <math>\,\lambda = \lambda(G)</math> is ''[[edge connectivity|edge-connectivity]]'' of <math>\,G</math>. Note that the set of [[edge|edges]] adjacent to a point <math>\,u</math> of degree <math>\,\lambda</math> is certainly a minimum edge-disconneting set. Similarly, <math>\,G</math> is '''[[maximum point-connected graph|maximum point-connected]]''' (in short, '''max'''-<math>\,\kappa</math>) if <math>\,\kappa =
[2q/p]</math>, where <math>\,\kappa = \kappa(G)</math> is the point-connectivity of <math>\,G</math>.
Also, the set of points adjacent to <math>\,u</math> of degree <math>\,\kappa</math> is
certainly a minimum point-disconnecting set. In this context, such an edge or a point set is called [[trivial graph|trivial]]. A graph <math>\,G</math> is called '''[[super edge-connected graph|super edge-connected]]''' if <math>\,G</math> is max-<math>\,\lambda</math> and every minimum edge-disconnecting set is trivial. Analogously, <math>\,G</math> is '''super point connected''' if <math>\,G</math> is max-<math>\,\kappa</math> and every minimum point-disconnecting set is trivial.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия от 14:04, 24 ноября 2014

Connected graphсвязный граф.

A graph [math]\displaystyle{ \,G }[/math] is a connected graph if for all [math]\displaystyle{ \,u,v \in V(G) }[/math], [math]\displaystyle{ \,u \neq v }[/math], there is a chain [math]\displaystyle{ \,(v_{1}, \ldots, v_{k}) }[/math] in [math]\displaystyle{ \,G }[/math] with [math]\displaystyle{ \,\{v_{1}, v_{k}\} = \{u,v\} }[/math], (the chain connects [math]\displaystyle{ \,u }[/math] and [math]\displaystyle{ \,v }[/math]). Otherwise, the graph is called disconnected.

A graph [math]\displaystyle{ \,G = (V,E) }[/math] is maximum edge-connected (in short, max-[math]\displaystyle{ \,\lambda }[/math]) if [math]\displaystyle{ \,\lambda = [2q/p] }[/math], where [math]\displaystyle{ \,p = |V|, \; q = |E| }[/math] and [math]\displaystyle{ \,\lambda = \lambda(G) }[/math] is edge-connectivity of [math]\displaystyle{ \,G }[/math]. Note that the set of edges adjacent to a point [math]\displaystyle{ \,u }[/math] of degree [math]\displaystyle{ \,\lambda }[/math] is certainly a minimum edge-disconneting set. Similarly, [math]\displaystyle{ \,G }[/math] is maximum point-connected (in short, max-[math]\displaystyle{ \,\kappa }[/math]) if [math]\displaystyle{ \,\kappa = [2q/p] }[/math], where [math]\displaystyle{ \,\kappa = \kappa(G) }[/math] is the point-connectivity of [math]\displaystyle{ \,G }[/math]. Also, the set of points adjacent to [math]\displaystyle{ \,u }[/math] of degree [math]\displaystyle{ \,\kappa }[/math] is certainly a minimum point-disconnecting set. In this context, such an edge or a point set is called trivial. A graph [math]\displaystyle{ \,G }[/math] is called super edge-connected if [math]\displaystyle{ \,G }[/math] is max-[math]\displaystyle{ \,\lambda }[/math] and every minimum edge-disconnecting set is trivial. Analogously, [math]\displaystyle{ \,G }[/math] is super point connected if [math]\displaystyle{ \,G }[/math] is max-[math]\displaystyle{ \,\kappa }[/math] and every minimum point-disconnecting set is trivial.

Литература

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