4625
правок
K-Closure of a graph: различия между версиями
Материал из WikiGrapp
нет описания правки
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. | ||
