Bondy--Chvtal closure operation: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Bondy--Chv\'{a}tal closure operation''' --- операция замыкания
'''<math>Bondy-Chv\acute{a}tal</math> closure operation''' операция замыкания
Бонди-Хватала.  
Бонди-Хватала.  


Given a graph of order <math>n</math>,  repeat the following operation as long as
Given a graph of order <math>\,n</math>,  repeat the following operation as long as
possible. For each pair of nonadjacent vertices <math>a</math> and <math>b</math>,  if <math>d(a)
possible. For each pair of nonadjacent vertices <math>a</math> and <math>\,b</math>,  if <math>d(a)
+ d(b) \geq n</math>,  then add the edge <math>ab</math> to <math>G</math>.  We denote by  <math>cl(G)</math>
+ d(b) \geq n</math>,  then add the edge <math>\,ab</math> to <math>G</math>.  We denote by  <math>\,cl(G)</math>
the resulting graph and call it the '''Bondy--Chv\'{a'''tal closure} of
the resulting graph and call it the '''<math>Bondy-Chv\acute{a}tal</math> closure''' of
<math>G</math>.
<math>\,G</math>.


The other name is '''Hamiltonian closure'''.
The other name is '''Hamiltonian closure'''.

Навигация