Энергия графа

Энергия графа — в математике величина, определяемая как сумма абсолютных значений собственных значений матрицы смежности графа. Термин используется в спектральной теории графов и имеет корни в теоретической химии.

Пусть G — простой неориентированный граф без петель и кратных рёбер, имеющий n вершин. Обозначим через A его матрицу смежности, и пусть

${\displaystyle \lambda _{1},\lambda _{2},\dots ,\lambda _{n}}$

— собственные значения матрицы A. Тогда энергия графа определяется как:

${\displaystyle E(G)=\sum _{i=1}^{n}{\bigl |}\lambda _{i}{\bigr |}.}$

Эта формула является стандартной в литературе по спектральной теории графов.^[1]

Концепция энергии графа была введена Иваном Гутманом в конце 1970-х годов в контексте молекулярных графов и приближённых моделей π-электронов.^[2]

Энергия является спектральным инвариантом графа и обладает рядом интересных свойств и оценок.

• Энергия ${\displaystyle E(G)\geq 0}$, и она инвариантна относительно изоморфизмов графов.
• Один из классических нижних границ:

${\displaystyle E(G)\geq 2{\sqrt {m}},}$

где m — число рёбер графа.^[2]

• Существуют улучшенные нижние и верхние оценки, учитывающие степени вершин, хроматическое число, диаметр, детерминант матрицы смежности и др.^[3]
• Доказано, что энергия графа не может быть нечётным числом, квадратным корнем из нечётного числа или золотым сечением.^[4]

• Для полного графа ${\displaystyle K_{n}}$ энергия ${\displaystyle E(K_{n})=2(n-1)}$.
• Для графов, у которых спектр симметричен относительно нуля (например, двудольный граф), сумма собственных значений равна нулю, и энергия определяется «парной» структурой спектра.
• В обобщённых версиях — например, для взвешенных или ориентированных графов — определяют «энергию» через модифицированные матрицы (взвешенную матрицу смежности или её обобщения).^[5]

Энергия графа находит применение в нескольких областях:

• Химия — первоначально использовалась в теории химической устойчивости молекул, где молекула представляется как граф, а энергия графа соотносится с π-электронной энергией.^[2]
• Анализ сетей — в исследованиях комплексных сетей энергия локальных подпроцессов (эгосетей) коррелирует с центральностью вершин.^[6]
• Теория матриц — понятие энергии графа можно расширить на более общие матрицы (не обязательно смежности) и исследовать «энергию матрицы» как сумму сингулярных значений.^[7]

Некоторые исследуемые направления:

• Какой граф на n вершинах имеет максимальную энергию?
• Каково поведение энергии при присоединении или удалении рёбер, а также при операциях над графами (усечение, объединение и др.)?
• Энергия больших графов: приближённые методы вычисления спектра и энергии.
• Связь энергии с другими спектральными характеристиками графа (например, энергия Лапласиана, Randić-энергия и др.).

1. ↑ «Graph energy», English Wikipedia
2. ↑ ^{1 2 3} Stevanović, «Energy of Graphs», PDF-монография
3. ↑ Das & Gutman и соавт., «Bounds for the energy of graphs», Hacettepe Journal
4. ↑ Wolfram MathWorld: Graph Energy
5. ↑ Shaban et al., обобщённая энергия α-adjacency
6. ↑ Morzy & Kajdanowicz, Graph Energies of Egocentric Networks
7. ↑ Nikiforov, The Energy of Graphs and Matrices

• Cvetković, D., Doob, M., Sachs, H. Spectra of Graphs. New York: Academic Press, 1980.
• Gutman, I. «The energy of a graph». In: 10. Steiermärkisches Mathematisches Symposium (Stift Rein, Graz, 1978). 1978.
• Gutman, I. Algebraic combinatorics and applications. Berlin: Springer, 2001.
• Li, X., Shi, Y., Gutman, I. Graph Energy. New York: Springer, 2012.
• Das, K. C., Gutman, I. «Bounds for the energy of graphs». Hacettepe Journal of Mathematics and Statistics, 2016