Bondy--Chvtal closure operation: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Bondy | '''<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 | 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'''. | ||
Текущая версия от 17:40, 3 мая 2011
[math]\displaystyle{ Bondy-Chv\acute{a}tal }[/math] closure operation — операция замыкания Бонди-Хватала.
Given a graph of order [math]\displaystyle{ \,n }[/math], repeat the following operation as long as possible. For each pair of nonadjacent vertices [math]\displaystyle{ a }[/math] and [math]\displaystyle{ \,b }[/math], if [math]\displaystyle{ d(a) + d(b) \geq n }[/math], then add the edge [math]\displaystyle{ \,ab }[/math] to [math]\displaystyle{ G }[/math]. We denote by [math]\displaystyle{ \,cl(G) }[/math] the resulting graph and call it the [math]\displaystyle{ Bondy-Chv\acute{a}tal }[/math] closure of [math]\displaystyle{ \,G }[/math].
The other name is Hamiltonian closure.