Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.4. Граф остовов

Каждому остову графа сопоставим определенную вершину (нового графа). Две вершины в новом графе соединяются ребром только тогда, когда соответствующие им остовы графа являются соседними (т. е. расстояние между этими остовами, определяемое в соответствии с разд. 2.1, равно единице). Граф, построенный таким образом, называется графом остовое (графа Для графа изображенного на рис. полный список остовов приведен на рис. а граф остовов — на рис. 7.10 (в).

Каммингс [15] и Шэнк [51] доказали, что граф остовов любого связного графа является гамильтоновым. Позже Киси и Кадзитани [37, 38] и Камаз [33] разработали методы нахождения гамильтоновых циклов в графе остовов (и, следовательно, методы построения всех остовов графа Эти методы представляют в основном теоретический интерес и не эффективны с вычислительной точки зрения.

Рис. 7.10. (см. скан) Граф G и его граф остовов. (а) Граф G. (б) Остовы графа G. (в) Граф остовов графа G.

<< Предыдущий параграф Следующий параграф >>
Оглавление