4745

Автор(ы): 

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Spanning Forests and the Golden Ratio

ISBN/ISSN: 

0166-218X

Наименование источника: 

  • Discrete Applied Mathematics

Обозначение и номер тома: 

V. 156. No. 5.

Город: 

  • Amsterdam

Издательство: 

  • Elsevier

Год издания: 

2008

Страницы: 

813-821
Аннотация
Для графа G через fij обозначим число остовных корневых лесов, где вершина j принадлежит дереву с корнем i. В статье показано, что для графа-цепи величины fij могут быть выражены как произведения чисел Фибоначчи для графа-цикла они являются произведениями чисел Фибоначчи и Люка. Дважды стохастическая матрица графа – это матрица F = (fij)n×n/f , где f – общее число остовных корневых лесов графа G, а n – число вершин G. Матрица F определяет меру близости для вершин графа. По матричной теореме о лесах F𕒵 = I + L, где L – лапласовская матрица графа G. В работе показано, что для графов-цепей и так называемых T-гусеничных графов некоторые диагональные элементы F (являющиеся мерой самосвязанности вершин) сходятся к Φ𕒵 или к 1 − Φ𕒵, где Φ – золотое сечение, при стремлении к бесконечности числа вершин. Тем самым, в асимптотике соответствующие вершины могут соответственно рассматриваться как “золотые интроверты” и “золотые экстраверты”. Эта метафора усиливается и углубляется марковской интерпретацией дважды стохастической матрицы графа, согласно которой матрица F равна итоговой матрице переходов случайного блуждания по графу G со случайным числом шагов.

Библиографическая ссылка: 

Чеботарев П.Ю. Spanning Forests and the Golden Ratio // Discrete Applied Mathematics. 2008. V. 156. No. 5. С. 813-821.