Аноним

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

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Connected graph''' --- связный граф.  
'''Connected graph''' — ''[[связный граф]].''


A graph <math>G</math> is a '''connected graph''' if for all <math>u,v \in V(G)</math>, <math>u \neq v</math>, there
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},
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]]'''.
v_{k}\} = \{u,v\}</math>, (the chain connects <math>u</math> and <math>v</math>). Otherwise, the graph is called '''disconnected'''.


A graph <math>G = (V,E)</math> is '''maximum edge-connected''' (in short, '''max'''-<math>\lambda</math>) if <math>\lambda = [2q/p]</math>, where <math>p = |V|, \; q = |E|</math> and
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 =
<math>\lambda = \lambda(G)</math> is ''edge-connectivity'' of <math>G</math>. Note that
[2q/p]</math>, where <math>\,\kappa = \kappa(G)</math> is the point-connectivity of <math>\,G</math>.
the set of edges adjacent to a point <math>u</math> of degree <math>\lambda</math> is
Also, the set of points adjacent to <math>\,u</math> of degree <math>\,\kappa</math> is
certainly a minimum edge-disconneting set. Similarly, <math>G</math> is '''maximum point-connected''' (in short, '''max'''-<math>\kappa</math>) if <math>\kappa =
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.
[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. A graph <math>G</math> is called '''super edge-connected''' if <math>G</math> is max-<math>\lambda</math> and every minimum
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.
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.