Bondy-Chvatal closure operation: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) (Новая страница: «'''<math>Bondy-Chv\acute{a}tal</math> closure operation''' — ''операция замыкания Бонди-Хватала.'' Given a [[graph, undirected g…») |
(нет различий)
|
Текущая версия от 12:35, 20 апреля 2012
[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.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.