Аноним

K-Closure of a graph: различия между версиями

Материал из WikiGrapp
нет описания правки
(Новая страница: «'''<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…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''<math>k</math>-Closure of a graph''' --- <math>k</math>-замыкание графа.  
'''<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.