K-Connected graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''<math>k</math>-Connected graph''' --- <math>k</math>-связный граф. A graph <math>G</math> is '''<math>k</math>-connected''' if there exist <math>k</m…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>k</math>-Connected graph''' - | '''<math>\,k</math>-Connected graph''' — ''[[k-Связный граф|<math>\,k</math>-связный граф]].'' | ||
A graph <math>G</math> is '''<math>k</math>-connected''' if there exist <math>k</math> internally | A [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> is '''<math>\,k</math>-connected''' if there exist <math>\,k</math> internally node-disjoint chains between every pair of distinct nodes in <math>\,G</math>. A <math>\,k</math>-connected graph <math>\,G</math> is '''minimal''' if for any [[edge]] <math>\,e \in E</math>, <math>\,G - e</math> is not <math>\,k</math>-connected. Usually, [[2-Connected graph|<math>\,2</math>-connected graphs]] are called ''biconnected graphs'' and <math>\,3</math>-connected graphs are called '''triconnected graphs'''. | ||
node-disjoint chains between every pair of distinct nodes in <math>G</math>. A | |||
<math>k</math>-connected graph <math>G</math> is '''minimal''' if for any edge <math>e \in E</math>, | ==Литература== | ||
<math>G - e</math> is not <math>k</math>-connected. Usually, 2-connected graphs are called | |||
''biconnected graphs'' and 3-connected graphs are called '''triconnected graphs'''. | * Евстигнеев В.А., Касьянов В.Н. Слhttp://pco.iis.nsk.su/wiki/skins/common/images/cyrl/button_link.pngоварь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
Версия от 13:32, 18 марта 2015
[math]\displaystyle{ \,k }[/math]-Connected graph — [math]\displaystyle{ \,k }[/math]-связный граф.
A graph [math]\displaystyle{ \,G }[/math] is [math]\displaystyle{ \,k }[/math]-connected if there exist [math]\displaystyle{ \,k }[/math] internally node-disjoint chains between every pair of distinct nodes in [math]\displaystyle{ \,G }[/math]. A [math]\displaystyle{ \,k }[/math]-connected graph [math]\displaystyle{ \,G }[/math] is minimal if for any edge [math]\displaystyle{ \,e \in E }[/math], [math]\displaystyle{ \,G - e }[/math] is not [math]\displaystyle{ \,k }[/math]-connected. Usually, [math]\displaystyle{ \,2 }[/math]-connected graphs are called biconnected graphs and [math]\displaystyle{ \,3 }[/math]-connected graphs are called triconnected graphs.
Литература
- Евстигнеев В.А., Касьянов В.Н. Слhttp://pco.iis.nsk.su/wiki/skins/common/images/cyrl/button_link.pngоварь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.