Bondy-Chvatal closure operation

Материал из WikiGrapp
Версия от 12:35, 20 апреля 2012; KEV (обсуждение | вклад) (Новая страница: «'''<math>Bondy-Chv\acute{a}tal</math> closure operation''' — ''операция замыкания Бонди-Хватала.'' Given a [[graph, undirected g…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

[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.