Проводимость графа

Проводимость графа G=(V,E) — это измерение плотности графа, которое контролирует, насколько быстро случайное блуждание на G сходится к равномерному распределению. Проводимость графа часто называется константой Чигера графа как аналог его двойника в спектральной геометрии. Поскольку электрические цепи тесно связаны со случайными блужданиями и имеют длинную историю применения термина «проводимость», это альтернативное название помогает избежать возможную путаницу.

Проводимость разреза ${\displaystyle (S,{\bar {S}})}$ графа определяется как:

${\displaystyle \varphi (S)={\frac {\sum _{i\in S,j\in {\bar {S}}}a_{ij}}{\min(a(S),a({\bar {S}}))}}}$

где ${\displaystyle a_{ij}}$ являются элементами матрицы смежности графа G, так что

${\displaystyle a(S)=\sum _{i\in S}\sum _{j\in V}a_{ij}}$

является полным числом (или весом) рёбер, инцидентных S. Значение ${\displaystyle a(S)}$ также называется объёмом множества ${\displaystyle S\subseteq V}$.

Проводимость всего графа равна минимальной проводимости по всем возможным разрезам:

${\displaystyle \phi (G)=\min _{S\subseteq V}\varphi (S).}$

Эквивалентно, проводимость графа определяется следующим образом:

${\displaystyle \phi (G):=\min _{S\subseteq V;0\leq a(S)\leq a(V)/2}{\frac {\sum _{i\in S,j\in {\bar {S}}}a_{ij}}{a(S)}}.\,}$

Для d-регулярного графа проводимость равна изопериметрическому числу, делённому на d.