Connected graph: различия между версиями
Glk (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
Текущая версия от 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.