Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Каждому остову графа сопоставим определенную вершину (нового графа). Две вершины в новом графе соединяются ребром только тогда, когда соответствующие им остовы графа являются соседними (т. е. расстояние между этими остовами, определяемое в соответствии с разд. 2.1, равно единице). Граф, построенный таким образом, называется графом остовое (графа Для графа изображенного на рис. полный список остовов приведен на рис. а граф остовов — на рис. 7.10 (в).
Каммингс [15] и Шэнк [51] доказали, что граф остовов любого связного графа является гамильтоновым. Позже Киси и Кадзитани [37, 38] и Камаз [33] разработали методы нахождения гамильтоновых циклов в графе остовов (и, следовательно, методы построения всех остовов графа Эти методы представляют в основном теоретический интерес и не эффективны с вычислительной точки зрения.
Рис. 7.10. (см. скан) Граф G и его граф остовов. (а) Граф G. (б) Остовы графа G. (в) Граф остовов графа G.
сопоставим определенную вершину (нового графа). Две вершины в новом графе соединяются ребром только тогда, когда соответствующие им остовы графа 
являются соседними (т. е. расстояние между этими остовами, определяемое в соответствии с разд. 2.1, равно единице). Граф, построенный таким образом, называется графом остовое (графа 
Для графа 
изображенного на рис. 
полный список остовов приведен на рис. 
а граф остовов — на рис. 7.10 (в).
Эти методы представляют в основном теоретический интерес и не эффективны с вычислительной точки зрения.
