Энергия графа — в математике величина, определяемая как сумма абсолютных значений собственных значений матрицы смежности графа. Термин используется в спектральной теории графов и имеет корни в теоретической химии.
Определение Пусть G — простой неориентированный граф без петель и кратных рёбер, имеющий n вершин. Обозначим через A его матрицу смежности, и пусть
— собственные значения матрицы A. Тогда энергия графа определяется как:
Эта формула является стандартной в литературе по спектральной теории графов.«Graph energy», English Wikipedia
Исторический контекст Концепция энергии графа была введена Иваном Гутманом в конце 1970-х годов в контексте молекулярных графов и приближённых моделей π-электронов.Stevanović, «Energy of Graphs», PDF-монография
Свойства и границы Энергия является спектральным инвариантом графа и обладает рядом интересных свойств и оценок.
Энергия , и она инвариантна относительно изоморфизмов графов. Один из классических нижних границ:
где m — число рёбер графа.
Существуют улучшенные нижние и верхние оценки, учитывающие степени вершин, хроматическое число, диаметр, детерминант матрицы смежности и др.Das & Gutman и соавт., «Bounds for the energy of graphs», Hacettepe Journal Доказано, что энергия графа не может быть нечётным числом, квадратным корнем из нечётного числа или золотым сечением.Wolfram MathWorld: Graph Energy
Особые случаи
Для полного графа энергия . Для графов, у которых спектр симметричен относительно нуля (например, двудольный граф), сумма собственных значений равна нулю, и энергия определяется «парной» структурой спектра. В обобщённых версиях — например, для взвешенных или ориентированных графов — определяют «энергию» через модифицированные матрицы (взвешенную матрицу смежности или её обобщения).Shaban et al., обобщённая энергия α-adjacency
Применения Энергия графа находит применение в нескольких областях:
Химия — первоначально использовалась в теории химической устойчивости молекул, где молекула представляется как граф, а энергия графа соотносится с π-электронной энергией. Анализ сетей — в исследованиях комплексных сетей энергия локальных подпроцессов (эгосетей) коррелирует с центральностью вершин.Morzy & Kajdanowicz, Graph Energies of Egocentric Networks Теория матриц — понятие энергии графа можно расширить на более общие матрицы (не обязательно смежности) и исследовать «энергию матрицы» как сумму сингулярных значений.Nikiforov, The Energy of Graphs and Matrices
Открытые вопросы Некоторые исследуемые направления:
Какой граф на n вершинах имеет максимальную энергию? Каково поведение энергии при присоединении или удалении рёбер, а также при операциях над графами (усечение, объединение и др.)? Энергия больших графов: приближённые методы вычисления спектра и энергии. Связь энергии с другими спектральными характеристиками графа (например, энергия Лапласиана, Randić-энергия и др.).
Примечания
Литература
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
Категория:Алгебраическая теория графов