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

Перейти к навигации Перейти к поиску

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

Точнее, пусть G — граф с n вершинами. Предполагается, что G — простой, то есть не содержащий петель или параллельных рёбер. Пусть A — матрица смежности G и пусть $\lambda _{i}$ , $i=1,\ldots ,n$ — собственные значения матрицы A. Тогда энергия графа определяется как:

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

Литература

Dragoš M. Cvetković, Michael Doob, Horst Sachs. Spectra of graphs. — New York: Academic Press Inc. [Harcourt Brace Jovanovich Publishers], 1980. — Т. 87. — ISBN 0-12-195150-2.
Ivan Gutman. 10. Steiermärkisches Mathematisches Symposium (Stift Rein, Graz, 1978). — 1978. — Vol. 103. — С. 1—22.
Ivan Gutman. Algebraic combinatorics and applications (Gößweinstein, 1999). — Berlin: Springer, 2001.
Xueliang Li, Yongtang Shi, Ivan Gutman. Graph Energy. — New York: Springer, 2012. — ISBN 978-1-4614-4219-6.

Похожие исследовательские статьи

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

Характеристический многочлен матрицы — многочлен, определяющий её собственные значения.

Со́бственный ве́ктор — понятие в линейной алгебре, определяемое для произвольного линейного оператора как ненулевой вектор, применение к которому оператора даёт коллинеарный вектор — тот же вектор, умноженный на некоторое скалярное значение. Скаляр, на который умножается собственный вектор под действием оператора, называется собственным числом линейного оператора, соответствующим данному собственному вектору. Одним из представлений линейного оператора является квадратная матрица, поэтому собственные векторы и собственные значения часто определяются в контексте использования таких матриц.

Метод главных компонент — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретён Карлом Пирсоном в 1901 году. Применяется во многих областях, в том числе в эконометрике, биоинформатике, обработке изображений, для сжатия данных, в общественных науках.

Матрица смежности — один из способов представления графа в виде матрицы.

<span class="mw-page-title-main">Регулярный граф</span> граф, степени всех вершин которого равны

Регуля́рный (одноро́дный) граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается $\text{[math]}$ . Для нерегулярных графов $\text{[math]}$ не определено. Регулярные графы представляют особую сложность для многих алгоритмов.

Спектральное разложение матрицы или разложение матрицы на основе собственных векторов — это представление квадратной матрицы $\text{[math]}$ в виде произведения трёх матриц $\text{[math]}$ , где $\text{[math]}$ — матрица, столбцы которой являются собственными векторами матрицы $\text{[math]}$ , $\text{[math]}$ — диагональная матрица с соответствующими собственными значениями на главной диагонали, $\text{[math]}$ — матрица, обратная матрице $\text{[math]}$ .

Экспандер — сильносвязный разреженный граф, при этом связность может определяться по вершинам, дугам или спектру.

<span class="mw-page-title-main">Сильно регулярный граф</span> регулярный граф с v вершинами и степенью k, у которого число общих соседей зависит только от смежности пары вершин

Сильно регулярный граф — вариация понятия регулярный граф.

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

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

В спектральной теории графов граф Рамануджана, названный по имени индийского математика Рамануджана, — это регулярный граф, спектральная щель которого почти настолько велика, насколько это возможно. Такие графы являются прекрасными спектральными экспандерами.

Группы Конвея — это три введённые Конвеем спорадические простые группы Co₁, Co₂ и Co₃ вместе со связанной с ними конечной группой Co₀.

Неравенство Фишера — это необходимое условие существования сбалансированной неполной блок-схемы, то есть системы подмножеств, которые удовлетворяют определённым предписанным условиям в комбинаторной математике. Неравенство описал Рональд Фишер, специалист по популяционной генетике и статистике, который изучал планирование эксперимента, изучая различия среди некоторых отличающихся разновидностей растений при различных условиях произрастания, называемых блоками.

Показатель центральности или близости к центру в теории графов и анализе сетей определяет наиболее важные вершины графа. Приложения показателя применяются для выявления наиболее влиятельного лица (лиц) в социальной сети, ключевых узлов инфраструктуры в интернете или городских сетей и разносчиков болезни. Концепции центральности первоначально развивались в анализе социальных сетей и многие термины центральности используются для измерения социологических первоисточников. Не следует путать эти показатели с метриками влияния узлов, которые ищут количественные характеристики влияния каждого узла в сети.

Степень влиятельности — это мера влияния узла в сети. Относительные величины показателя назначаются всем узлам на основе концепции, что связь с узлом высокой степени влиятельности вкладывает больше в показатель рассматриваемого узла, чем аналогичная связь с узлом низкой степени влиятельности. Высокая степень влиятельности означает, что узел связан со многими узлами, имеющими высокие степени влиятельности.

Симметрии в квантовой механике — преобразования пространства-времени и частиц, которые оставляют неизменными уравнения квантовой механики. Рассматриваются во многих разделах квантовой механики, которые включают релятивистскую квантовую механику, квантовую теорию поля, стандартную модель и физику конденсированного состояния. В целом, симметрия в физике, законы инвариантности и сохранения являются основополагающими ограничениями для формулирования физических теорий и моделей. На практике это мощные методы решения задач и прогнозирования того, что может случиться. Хотя законы сохранения не всегда дают конечное решение проблемы, но они формируют правильные ограничения и наметки к решению множества задач.

Спектр графа - это множество собственных значений матрицы смежности графа.

Обобщённый собственный вектор $\text{[math]}$ матрицы $\text{[math]}$ — вектор, который удовлетворяет определённым критериям, которые слабее, чем критерии для (обычных) собственных векторов.

Спектральный радиус — понятие в математике, определяемое для квадратной матрицы как максимум абсолютных значений её собственных значений. В более общем случае, спектральный радиус линейного ограниченного оператора — это точная верхняя граница абсолютных значений элементов его спектра. Спектральный радиус часто обозначается ρ(·).

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.