Матрица лапласа

В математической области теории графов , в лапласиана матрицы , которая также называется граф лапласиан , проводимость матрицы , матрицы Кирхгофа или дискретного лапласиана , является матрица представление графа . Матрицу Лапласа можно использовать для нахождения многих полезных свойств графа. Вместе с теоремой Кирхгофа его можно использовать для вычисления количества остовных деревьев для данного графа. Самый разреженный разрез графа может быть аппроксимирован вторым наименьшим собственным значением его лапласиана неравенством Чигера. Его также можно использовать для построения низкоразмерных вложений , которые могут быть полезны для различных приложений машинного обучения .

Определение [ править ]

Матрица Лапласа для простых графиков [ править ]

Для простого графа с вершинами его матрица лапласиана определяется как: ^[1]${\ displaystyle G}$${\ displaystyle n}$${\ textstyle L_ {п \ раз п}}$

${\ displaystyle L = DA,}$

где D - матрица степеней, а A - матрица смежности графа. Поскольку это простой граф, он содержит только единицы или нули, а его диагональные элементы - все нули.${\ textstyle G}$${\ textstyle A}$

В случае ориентированных графов , в зависимости от приложения, может использоваться степень или исходящая степень .

Элементы представлены${\ textstyle L}$

${\ Displaystyle L_ {я, j}: = {\ begin {case} \ deg (v_ {i}) & {\ mbox {if}} \ i = j \\ - 1 & {\ mbox {if}} \ i \ neq j \ {\ mbox {and}} \ v_ {i} {\ mbox {находится рядом с}} v_ {j} \\ 0 & {\ mbox {в противном случае}} \ end {cases}}}$

где - степень вершины .${\ displaystyle \ operatorname {deg} (v_ {i})}$${\ displaystyle i}$

Симметричный нормализованный лапласиан [ править ]

Симметричная нормализованная матрица Лапласа определяется как: ^[1]

${\ displaystyle L ^ {\ text {sym}}: = D ^ {- {\ frac {1} {2}}} LD ^ {- {\ frac {1} {2}}} = ID ^ {- { \ frac {1} {2}}} AD ^ {- {\ frac {1} {2}}}}$,

Элементы представлены${\ textstyle L ^ {\ text {sym}}}$

${\displaystyle L_{i,j}^{\text{sym}}:={\begin{cases}1&{\mbox{if }}i=j{\mbox{ and }}\deg(v_{i})\neq 0\\-{\frac {1}{\sqrt {\deg(v_{i})\deg(v_{j})}}}&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}}$

Нормализованный лапласиан случайного блуждания [ править ]

Нормированная матрица лапласиана случайного блуждания определяется как:

${\displaystyle L^{\text{rw}}:=D^{-1}L=I-D^{-1}A}$

Элементы представлены${\textstyle L^{\text{rw}}}$

${\displaystyle L_{i,j}^{\text{rw}}:={\begin{cases}1&{\mbox{if }}i=j{\mbox{ and }}\deg(v_{i})\neq 0\\-{\frac {1}{\deg(v_{i})}}&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}}$

Обобщенный лапласиан [ править ]

Обобщенный лапласиан определяется как: ^[2]${\displaystyle Q}$

${\displaystyle {\begin{cases}Q_{i,j}<0&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\Q_{i,j}=0&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is not adjacent to }}v_{j}\\{\mbox{any number}}&{\mbox{otherwise}}.\end{cases}}}$

Обратите внимание, что обычный лапласиан является обобщенным лапласианом.

Пример [ править ]

Вот простой пример помеченного неориентированного графа и его матрицы Лапласа.

Маркированный график	Матрица степеней	Матрица смежности	Матрица лапласа
	${\textstyle \left({\begin{array}{rrrrrr}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{array}}\right)}$	${\textstyle \left({\begin{array}{rrrrrr}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{array}}\right)}$

Свойства [ править ]

Для (неориентированного) графа G и его матрицы Лапласа L с собственными значениями :${\textstyle \lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}}$

• L является симметричным .
• L является положительным полуопределенным (то есть для всех ). Это проверено в разделе матрицы инцидентности (ниже). Это также видно из того факта, что лапласиан симметричен и доминирует по диагонали .${\textstyle \lambda _{i}\geq 0}$${\textstyle i}$
• L является M-матрицей (ее недиагональные элементы неположительны, но действительные части ее собственных значений неотрицательны).
• Каждая сумма строки и сумма столбца L равна нулю. Действительно, в сумме степень вершины суммируется с «-1» для каждого соседа.
• Следовательно, поскольку вектор удовлетворяет Этому также следует, что матрица Лапласа сингулярна.${\textstyle \lambda _{0}=0}$${\textstyle \mathbf {v} _{0}=(1,1,\dots ,1)}$${\textstyle L\mathbf {v} _{0}=\mathbf {0} .}$
• Количество компонент связности в графе - это размерность нулевого пространства лапласиана и алгебраическая кратность нулевого собственного значения.
• Наименьшее ненулевое собственное значение оператора L называется спектральной щелью .
• Второе наименьшее собственное значение L (может быть нулем) является алгебраической связностью (или значением Фидлера ) G и аппроксимирует самый разреженный разрез графа.
• Лапласиан является оператором на п-мерном векторном пространстве функций , где есть множество вершин G, а .${\textstyle f:V\to \mathbb {R} }$${\textstyle V}$${\textstyle n=|V|}$
• Когда G является k-регулярным , нормализованный лапласиан равен:, где A - матрица смежности, а I - единичная матрица.${\textstyle {\mathcal {L}}={\tfrac {1}{k}}L=I-{\tfrac {1}{k}}A}$
• Для графа с множеством компонент связности , L представляет собой блочно - диагональная матрица, в которой каждый блок является соответствующая лапласиан матрица для каждого компонента, возможно , после переупорядочения вершины (т.е. L является перестановкой-подобна блочно - диагональной матрицы).
• След лапласианской матрицы L равен где - количество ребер рассматриваемого графа.${\textstyle 2m}$${\textstyle m}$

Матрица заболеваемости [ править ]

Определите ориентированную матрицу инцидентности M с элементом M _ev для ребра e (соединяющего вершину i и j , при i  >  j ) и вершину v, заданную формулой${\textstyle |e|\times |v|}$

${\displaystyle M_{ev}=\left\{{\begin{array}{rl}1,&{\text{if }}v=i\\-1,&{\text{if }}v=j\\0,&{\text{otherwise}}.\end{array}}\right.}$

Тогда матрица Лапласа L удовлетворяет

${\displaystyle L=M^{\textsf {T}}M}$

где это транспонированная матрица из M .${\textstyle M^{\textsf {T}}}$

Теперь рассмотрим собственное разложение с собственными векторами единичной нормы и соответствующими собственными значениями :${\textstyle L}$${\textstyle \mathbf {v} _{i}}$${\textstyle \lambda _{i}}$

${\displaystyle {\begin{aligned}\lambda _{i}&=\mathbf {v} _{i}^{\textsf {T}}L\mathbf {v} _{i}\\&=\mathbf {v} _{i}^{\textsf {T}}M^{\textsf {T}}M\mathbf {v} _{i}\\&=\left(M\mathbf {v} _{i}\right)^{\textsf {T}}\left(M\mathbf {v} _{i}\right).\\\end{aligned}}}$

Поскольку это может быть записано как внутреннее произведение вектора на себя, это показывает, что все собственные значения неотрицательны.${\textstyle \lambda _{i}}$${\textstyle M\mathbf {v} _{i}}$${\textstyle \lambda _{i}\geq 0}$${\textstyle L}$

Деформированный лапласиан [ править ]

Деформируется лапласиан обычно определяется как

${\displaystyle \Delta (s)=I-sA+s^{2}(D-I)}$

где I - единичная матрица, A - матрица смежности, D - матрица степеней, а s - (комплексное) число. ^[3]
Стандартный лапласиан справедлив и является беззнаковым лапласианом.${\textstyle \Delta (1)}$${\textstyle \Delta (-1)=D+A}$

Беззнаковый лапласиан [ править ]

Не имеющие маркировки лапласиан определяются как

$${\displaystyle Q=D+A}$$

${\displaystyle D}$

${\displaystyle A}$

${\displaystyle L}$

${\displaystyle Q}$

$${\displaystyle Q=RR^{\textsf {T}}}$$

${\textstyle R}$

${\displaystyle Q}$

$${\displaystyle \mathbf {x} ^{\textsf {T}}Q\mathbf {x} =\mathbf {x} ^{\textsf {T}}RR^{\textsf {T}}\mathbf {x} \implies R^{\textsf {T}}\mathbf {x} =\mathbf {0} .}$$

${\displaystyle \mathbf {x} \neq \mathbf {0} }$

Симметричный нормализованный лапласиан [ править ]

(Симметричный) нормализованы лапласиан определяется как

${\displaystyle L^{\text{sym}}:=D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}=I-D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}}$

где L - (ненормализованный) лапласиан, A - матрица смежности, а D - матрица степеней. Поскольку степень матрица D диагональная и положителен, его обратный квадратный корень только диагональная матрица, диагональные элементы являются обратными положительными квадратными корнями из диагональных элементов D . Симметричный нормализованный лапласиан - это симметричная матрица.${\textstyle D^{-{\frac {1}{2}}}}$

У одного есть:, где S - матрица, строки которой индексированы вершинами, а столбцы которой индексированы ребрами G, так что каждый столбец, соответствующий ребру e = {u, v}, имеет запись в строке, соответствующей u , запись в строке, соответствующая v, и имеет 0 записей в другом месте. ( обозначает транспонирование S).${\textstyle L^{\text{sym}}=SS^{*}}$${\textstyle {\frac {1}{\sqrt {d_{u}}}}}$${\textstyle -{\frac {1}{\sqrt {d_{v}}}}}$${\textstyle S^{*}}$

Все собственные значения нормированного лапласиана действительны и неотрицательны. Мы можем увидеть это следующим образом. Поскольку он симметричен, его собственные значения действительны. Они также неотрицательны: рассмотрим собственный вектор из с собственным значением Х и пусть . (Мы можем рассматривать g и f как действительные функции на вершинах v.) Тогда:${\textstyle L^{\text{sym}}}$${\textstyle g}$${\textstyle L^{\text{sym}}}$${\textstyle g=D^{\frac {1}{2}}f}$

${\displaystyle \lambda \ =\ {\frac {\langle g,L^{\text{sym}}g\rangle }{\langle g,g\rangle }}\ =\ {\frac {\left\langle g,D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}g\right\rangle }{\langle g,g\rangle }}\ =\ {\frac {\langle f,Lf\rangle }{\left\langle D^{\frac {1}{2}}f,D^{\frac {1}{2}}f\right\rangle }}\ =\ {\frac {\sum _{u\sim v}(f(u)-f(v))^{2}}{\sum _{v}f(v)^{2}d_{v}}}\ \geq \ 0,}$

где мы используем скалярное произведение , сумму по всем вершинам v, и обозначаем сумму по всем неупорядоченным парам смежных вершин {u, v}. Величина называется суммой Дирихле функции f, а выражение - коэффициентом Рэлея g.${\textstyle \langle f,g\rangle =\sum _{v}f(v)g(v)}$${\textstyle \sum _{u\sim v}}$${\textstyle \sum _{u,v}(f(u)-f(v))^{2}}$${\textstyle {\frac {\left\langle g,L^{\text{sym}}g\right\rangle }{\langle g,g\rangle }}}$

Пусть 1 будет функцией, которая принимает значение 1 в каждой вершине. Тогда - собственная функция с собственным значением 0. ^[5]${\textstyle D^{\frac {1}{2}}1}$${\textstyle L^{\text{sym}}}$

Фактически, собственные значения нормализованного симметричного лапласиана удовлетворяют условию 0 = μ ₀ ≤… ≤ μ _{n − 1} ≤ 2. Эти собственные значения (известные как спектр нормализованного лапласиана) хорошо связаны с другими инвариантами графов для общих графов. ^[6]

Нормализованный лапласиан случайного блуждания [ править ]

Случайная прогулка нормализованы лапласиан определяется как

${\displaystyle L^{\text{rw}}:=D^{-1}L}$

где D - матрица степеней. Так как степень матрицы D является диагональным, его обратным просто определяются как диагональная матрица, имеющей диагональные элементы , которые являются обратными соответствующими положительными диагональными элементами D .${\textstyle D^{-1}}$

Для изолированных вершин (имеющих степень 0) обычно выбирают для соответствующего элемента значение 0.${\textstyle L_{i,i}^{\text{rw}}}$

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

Матричные элементы имеют вид${\textstyle L^{\text{rw}}}$

${\displaystyle L_{i,j}^{\text{rw}}:={\begin{cases}1&{\mbox{if}}\ i=j\ {\mbox{and}}\ \deg(v_{i})\neq 0\\-{\frac {1}{\deg(v_{i})}}&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}}$

Название нормализованного лапласиана случайного блуждания происходит от того факта, что эта матрица имеет вид , где - просто матрица перехода случайного блуждающего на графе. Например, пусть обозначает i-й стандартный базисный вектор. Затем - вектор вероятности, представляющий распределение местоположений случайного блуждающего человека после того, как он сделал один шаг из вершины ; то есть . В более общем смысле, если вектор представляет собой распределение вероятностей местоположения случайного пешехода в вершинах графа, то это распределение вероятности пешехода после шагов.${\textstyle L^{\text{rw}}=I-P}$${\textstyle P=D^{-1}A}$${\textstyle e_{i}}$${\textstyle x=e_{i}P}$${\textstyle i}$${\textstyle x_{j}=\mathbb {P} \left(v_{i}\to v_{j}\right)}$${\textstyle x}$${\textstyle x'=xP^{t}}$${\textstyle t}$

Это можно проверить

${\displaystyle L^{\text{rw}}=I-D^{-{\frac {1}{2}}}\left(I-L^{\text{sym}}\right)D^{\frac {1}{2}}}$,

то есть, это аналогично нормированный лапласиан . По этой причине, даже если он в целом не эрмитов, он имеет действительные собственные значения. В самом деле, его собственные значения совпадают с собственными значениями (что является эрмитовым). ${\textstyle L^{\text{rw}}}$${\textstyle L^{\text{sym}}}$${\textstyle L^{\text{rw}}}$${\textstyle L^{\text{sym}}}$

Графики [ править ]

Помимо случайных блужданий по графам , рассмотрим простой неориентированный граф . Рассмотрим вероятность того, что пешеход находится в вершине i в момент времени t , учитывая распределение вероятностей того, что он был в вершине j в момент времени t - 1 (при условии равномерного шанса сделать шаг по любому из ребер, прикрепленных к данной вершине) :

${\displaystyle p_{i}(t)=\sum _{j}{\frac {A_{ij}}{\deg \left(v_{j}\right)}}p_{j}(t-1),}$

или в матрично-векторной нотации:

${\displaystyle p(t)=AD^{-1}p(t-1).}$

(Равновесие, которое наступает как , определяется формулой .)${\textstyle t\rightarrow \infty }$${\textstyle p=AD^{-1}p}$

Мы можем переписать это соотношение в виде

${\displaystyle D^{-{\frac {1}{2}}}p(t)=\left[D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}\right]D^{-{\frac {1}{2}}}p(t-1).}$

${\textstyle A_{\text{reduced}}\equiv D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}}$является симметричной матрицей, называемой приведенной матрицей смежности . Таким образом, выполнение шагов в этом случайном блуждании требует использования степеней , что является простой операцией, поскольку она симметрична.${\textstyle A_{\text{reduced}}}$${\textstyle A_{\text{reduced}}}$

Интерпретация как дискретный оператор Лапласа [ править ]

Матрицу Лапласа можно интерпретировать как матричное представление частного случая дискретного оператора Лапласа . Такая интерпретация позволяет, например, обобщить матрицу Лапласа на случай графов с бесконечным числом вершин и ребер, что приведет к матрице Лапласа бесконечного размера.

Предположим, описывает распределение тепла по графу , где - тепло в вершине . Согласно закону охлаждения Ньютона , тепло, передаваемое от узла к узлу , пропорционально тому, если узлы и соединены (если они не соединены, тепло не передается). Тогда для теплоемкости ,${\textstyle \phi }$${\textstyle \phi _{i}}$${\textstyle i}$${\textstyle i}$${\textstyle j}$${\textstyle \phi _{i}-\phi _{j}}$${\textstyle i}$${\textstyle j}$${\textstyle k}$

${\displaystyle {\begin{aligned}{\frac {d\phi _{i}}{dt}}&=-k\sum _{j}A_{ij}\left(\phi _{i}-\phi _{j}\right)\\&=-k\left(\phi _{i}\sum _{j}A_{ij}-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\left(\phi _{i}\ \deg(v_{i})-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\sum _{j}\left(\delta _{ij}\ \deg(v_{i})-A_{ij}\right)\phi _{j}\\&=-k\sum _{j}\left(\ell _{ij}\right)\phi _{j}.\end{aligned}}}$

В матрично-векторных обозначениях

${\displaystyle {\begin{aligned}{\frac {d\phi }{dt}}&=-k(D-A)\phi \\&=-kL\phi ,\end{aligned}}}$

который дает

${\displaystyle {\frac {d\phi }{dt}}+kL\phi =0.}$

Обратите внимание, что это уравнение принимает ту же форму, что и уравнение теплопроводности , где матрица - L заменяет оператор Лапласа ; отсюда и «лапласиан графа».${\textstyle \nabla ^{2}}$

Чтобы найти решение этого дифференциального уравнения, примените стандартные методы решения матричного дифференциального уравнения первого порядка . То есть, запись в виде линейной комбинации собственных векторов из L (так что ) с зависящим от времени coeficients,${\textstyle \phi }$${\textstyle \mathbf {v} _{i}}$${\textstyle L\mathbf {v} _{i}=\lambda _{i}\mathbf {v} _{i}}$${\textstyle \phi (t)=\sum _{i}c_{i}(t)\mathbf {v} _{i}.}$

Подставляем в исходное выражение (поскольку L - симметричная матрица, ее собственные векторы с единичной нормой ортогональны):${\textstyle \mathbf {v} _{i}}$

${\displaystyle {\begin{aligned}0={}&{\frac {d\left(\sum _{i}c_{i}(t)\mathbf {v} _{i}\right)}{dt}}+kL\left(\sum _{i}c_{i}(t)\mathbf {v} _{i}\right)\\{}={}&\sum _{i}\left[{\frac {dc_{i}(t)}{dt}}\mathbf {v} _{i}+kc_{i}(t)L\mathbf {v} _{i}\right]\\{}={}&\sum _{i}\left[{\frac {dc_{i}(t)}{dt}}\mathbf {v} _{i}+kc_{i}(t)\lambda _{i}\mathbf {v} _{i}\right]\\\Rightarrow 0={}&{\frac {dc_{i}(t)}{dt}}+k\lambda _{i}c_{i}(t),\\\end{aligned}}}$

чье решение

${\displaystyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}.}$

Как было показано выше, собственные значения из L неотрицательны, показывая , что решение уравнения диффузии приближается к равновесию, так как он только экспоненциально затухает или остается постоянной. Это также показывает, что при заданном начальном условии решение может быть найдено в любой момент времени t . ^[7]${\textstyle \lambda _{i}}$${\textstyle \lambda _{i}}$${\textstyle c_{i}(0)}$

Чтобы найти для каждого в терминах общего начального условия , просто спроецируйте на собственные векторы единичной нормы ;${\textstyle c_{i}(0)}$${\textstyle i}$${\textstyle \phi (0)}$${\textstyle \phi (0)}$${\textstyle \mathbf {v} _{i}}$

${\displaystyle c_{i}(0)=\left\langle \phi (0),\mathbf {v} _{i}\right\rangle }$.

В случае неориентированных графов это работает, потому что он симметричен, а по спектральной теореме все его собственные векторы ортогональны. Таким образом, проекция на собственные векторы - это просто ортогональное преобразование координат начального условия в набор координат, которые убывают экспоненциально и независимо друг от друга.${\textstyle L}$${\textstyle L}$

Равновесное поведение [ править ]

Чтобы понять , остаются только те термины , в которых , поскольку${\textstyle \lim _{t\to \infty }\phi (t)}$${\textstyle c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}}$${\textstyle \lambda _{i}=0}$

${\displaystyle \lim _{t\to \infty }e^{-k\lambda _{i}t}={\begin{cases}0,&{\text{if}}&\lambda _{i}>0\\1,&{\text{if}}&\lambda _{i}=0\end{cases}}}$

Другими словами, равновесное состояние системы полностью определяется ядром из . ${\textstyle L}$

Поскольку по определению, вектор всех единиц находится в ядре. Если в графе есть непересекающиеся компоненты связности , то этот вектор всех единиц можно разбить на сумму независимых собственных векторов единиц и нулей, где каждая компонента связности соответствует собственному вектору с единицами в элементах связной компоненты и нулями в других местах. .${\textstyle \sum _{j}L_{ij}=0}$${\textstyle \mathbf {v} ^{1}}$${\textstyle k}$${\textstyle k}$${\textstyle \lambda =0}$

Следствием этого является то, что для данного начального условия для графа с вершинами${\textstyle c(0)}$${\textstyle N}$

${\displaystyle \lim _{t\to \infty }\phi (t)=\left\langle c(0),\mathbf {v^{1}} \right\rangle \mathbf {v^{1}} }$

куда

${\displaystyle \mathbf {v^{1}} ={\frac {1}{\sqrt {N}}}[1,1,\ldots ,1]}$

Для каждого элемента из , т.е. для каждой вершины в графе, то его можно переписать в виде${\textstyle \phi _{j}}$${\textstyle \phi }$${\textstyle j}$

${\displaystyle \lim _{t\to \infty }\phi _{j}(t)={\frac {1}{N}}\sum _{i=1}^{N}c_{i}(0)}$.

Другими словами, в установившемся состоянии значение сходится к одному и тому же значению в каждой из вершин графа, которое является средним из начальных значений во всех вершинах. Поскольку это решение уравнения диффузии тепла, интуитивно это имеет смысл. Мы ожидаем, что соседние элементы на графике будут обмениваться энергией до тех пор, пока эта энергия не будет равномерно распределена по всем элементам, которые связаны друг с другом.${\textstyle \phi }$

Пример оператора на сетке [ править ]

В этом разделе показан пример функции, распространяющейся во времени на графике. График в этом примере построен на дискретной двумерной сетке, точки которой связаны со своими восемью соседями. У трех начальных точек указано положительное значение, а остальные значения в сетке равны нулю. Со временем экспоненциальный спад действует для равномерного распределения значений в этих точках по всей сетке.${\textstyle \phi }$

Полный исходный код Matlab, который использовался для создания этой анимации, представлен ниже. Он показывает процесс определения начальных условий, проецирования этих начальных условий на собственные значения матрицы Лапласа и моделирования экспоненциального убывания этих спроектированных начальных условий.

N = 20 ; % Количество пикселей по размеру изображения   А = нули ( N , N ); % Изображение    Adj = нули ( N * N , N * N ); % Матрица смежности        % Используйте 8 соседей и заполните матрицу смежностиdx = [ - 1 , 0 , 1 , - 1 , 1 , - 1 , 0 , 1 ];            dy = [ - 1 , - 1 , - 1 , 0 , 0 , 1 , 1 , 1 ];            для x = 1 : N    для y = 1 : N    индекс = ( х - 1 ) * N + y ;         для ne = 1 : длина ( dx )    newx = x + dx ( ne );     newy = y + dy ( ne );     если newx > 0 && newx <= N && newy > 0 && newy <= N                index2 = ( newx - 1 ) * N + newy ;         Adj ( index , index2 ) = 1 ;    конец конец конецконец% НИЖЕ КЛЮЧЕВЫЙ КОД, ВЫЧИСЛЯЮЩИЙ РЕШЕНИЕ ДИФФЕРЕНЦИАЛЬНОГО УРАВНЕНИЯ.Deg = diag ( сумма ( Adj , 2 )); % Вычислить матрицу степеней    L = Градус - Регулировка ; % Вычислить матрицу лапласиана в терминах матриц степени и смежности     [ V , D ] = eig ( L ); % Вычислить собственные значения / векторы матрицы Лапласа    D = диаг ( D );  % Начальное условие (поместите несколько больших положительных значений вокруг и% обнулить все остальное)C0 = нули ( N , N );   С0 ( 2 : 5 , 2 : 5 ) = 5 ;   C0 ( 10 : 15 , 10 : 15 ) = 10 ;   C0 ( 2 : 5 , 8 : 13 ) = 7 ;   C0 = C0 (:);  C0V = V '* C0 ; % Преобразуйте начальное условие в систему координат   % собственных векторовдля t = 0 : 0,05 : 5    % Время цикла и распад каждого начального компонента Фи = C0V *. Ехр ( - Д * т ); % Экспоненциальный распад для каждого компонента         Phi = V * Phi ; % Преобразование из системы координат собственного вектора в исходную систему координат      Phi = изменить форму ( Phi , N , N );     % Показать результаты и записать в файл GIF imagesc ( Phi ); caxis ([ 0 , 10 ]);  title ( sprintf ( 'Diffusion t =% 3f' , t ));  кадр = getframe ( 1 );   im = frame2im ( кадр );   [ imind , cm ] = rgb2ind ( im , 256 );     если t == 0    imwrite ( imind , cm , 'out.gif' , 'gif' , 'Loopcount' , inf , 'DelayTime' , 0.1 );        еще imwrite ( imind , cm , 'out.gif' , 'gif' , 'WriteMode' , 'append' , 'DelayTime' , 0.1 );        конецконец

Аппроксимация отрицательного непрерывного лапласиана [ править ]

Матрица Лапласа графа может далее рассматриваться как матричная форма приближения к (положительно полуопределенному) оператору Лапласа, полученному методом конечных разностей . (См. Дискретное уравнение Пуассона ) ^[8] В этой интерпретации каждая вершина графа рассматривается как точка сетки; локальная связность вершины определяет шаблон конечно-разностной аппроксимации в этой точке сетки, размер сетки всегда один для каждого ребра, и нет никаких ограничений на какие-либо точки сетки, что соответствует случаю однородного граничного условия Неймана , т. е. , свободная граница.

Направленные мультиграфы [ править ]

Аналог матрицы Лапласа можно определить для ориентированных мультиграфов. ^[9] В этом случае матрица Лапласа L определяется как

${\displaystyle L=D-A}$

где D - диагональная матрица с D _{i , i,} равным исходной степени вершины i, а A - матрица с A _{i , j,} равным количеству ребер от i до j (включая петли).

См. Также [ править ]

• Матрица жесткости
• Расстояние сопротивления
• Матрица скорости перехода
• Исчисление на конечных взвешенных графах
• Графическое преобразование Фурье

Ссылки [ править ]

• Т. Сунада, "Дискретный геометрический анализ", Труды симпозиумов по чистой математике, (под ред. П. Экснера, Дж. П. Китинга, П. Кучмента, Т. Сунада, А. Тепляева), 77 (2008), 51–86.
• Б. Боллобас , Современная теория графов , Springer-Verlag (1998, исправленное издание 2013 г.), ISBN 0-387-98488-7 , главы II.3 (Векторные пространства и матрицы, связанные с графами), VIII.2 (Матрица смежности и лапласиан), IX.2 (Электрические сети и случайные блуждания).