K-Closure of a graph: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''<math>k</math>-Closure of a graph''' --- <math>k</math>-замыкание графа. The '''<math>k</math>-closure''' <math>G_{k}(G)</math> of a graph <math>G…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>k</math>-Closure of a graph''' - | '''<math>\,k</math>-Closure of a graph''' — ''[[k-Замыкание графа|<math>\,k</math>-Замыкание графа]].'' | ||
The '''<math>k</math>-closure''' <math>G_{k}(G)</math> of a graph <math>G</math> is obtained from <math>G</math> | The '''<math>\,k</math>-closure''' <math>\,G_{k}(G)</math> of a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> is obtained from <math>\,G</math> by recursively joining pairs of [[adjacent vertices|non-adjacent vertices]] whose degree-sum is at least <math>\,k</math> until no such pair remains. It is known that if <math>\,G_{n}(G)</math> is ''[[complete graph|complete]]'', then <math>\,G</math> contains a ''[[Hamiltonian cycle]]''. The <math>\,k</math>-closure of a graph can be computed in <math>{\mathcal O}(n^{3})</math> time in the worst case. | ||
by recursively joining pairs of non-adjacent vertices whose degree-sum | |||
is at least <math>k</math> until no such pair remains. It is known that if | ==Литература== | ||
<math>G_{n}(G)</math> is ''complete'', then <math>G</math> contains a ''Hamiltonian cycle''. The <math>k</math>-closure of a graph can be computed in <math>{\mathcal | |||
O}(n^{3})</math> time in the worst case. | * Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | ||
Текущая версия от 17:37, 11 ноября 2013
[math]\displaystyle{ \,k }[/math]-Closure of a graph — [math]\displaystyle{ \,k }[/math]-Замыкание графа.
The [math]\displaystyle{ \,k }[/math]-closure [math]\displaystyle{ \,G_{k}(G) }[/math] of a graph [math]\displaystyle{ \,G }[/math] is obtained from [math]\displaystyle{ \,G }[/math] by recursively joining pairs of non-adjacent vertices whose degree-sum is at least [math]\displaystyle{ \,k }[/math] until no such pair remains. It is known that if [math]\displaystyle{ \,G_{n}(G) }[/math] is complete, then [math]\displaystyle{ \,G }[/math] contains a Hamiltonian cycle. The [math]\displaystyle{ \,k }[/math]-closure of a graph can be computed in [math]\displaystyle{ {\mathcal O}(n^{3}) }[/math] time in the worst case.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.