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

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

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

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

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

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

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

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

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

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

$\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.

Обобщения и приложения

В практических приложениях часто рассматривается проводимость только по разрезу. Частым обобщением проводимости является учёт весов, назначенных рёбрам — тогда складываются веса. Если веса употребляются в виде сопротивления, то складываются обратные весам величины.

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

Проводимость помогает также измерить качество спектральной кластеризации. Максимум проводимостей кластеров даёт границу, которая может быть использована вместе с весами внутри кластера для определения меры качества кластеризации. Интуитивно проводимость кластера (который можно рассматривать как множество вершин в графе) должна быть низкой. Кроме того, может также использоваться проводимость подграфа, порождённого кластером (называемая «внутренней проводимостью»).

Марковские цепи

Для эргодичной обратимой цепи Маркова с графом G, проводимость является способом измерения, насколько трудно покинуть малое множество узлов. Формально проводимость графа определяется как минимум по всем множествам $S$ ёмкости множества $S$, делённой на эргодический поток из $S$. Алистер Синклер показал, что проводимость тесно связана с временем смешивания в эргодичной обратимой цепи Маркова. Мы можем также рассматривать проводимость в более вероятностном смысле, как минимальную вероятность покинуть малый набор узлов, если мы начинаем из узла внутри этого множества. Обозначим через $\Phi _{S}$ условную вероятность покинуть множество узлов S, проводимость тогда равна минимальному $\Phi _{S}$ по всем множествам $S$, которые имеют полную стационарную вероятность, не превосходящую 1/2.

Проводимость связана с временем смешивания в обратимых условиях.

См. также

• Резистивное расстояние

Литература

• Béla Bollobás. Modern graph theory. — Springer-Verlag, 1998. — Т. 184. — С. 321. — (GTM). — ISBN 0-387-98488-7.
• Kannan R., Vempala S., Vetta A. On clusterings: Good, bad and spectral // J. ACM. — 2004. — Май (т. 51, вып. 3). — С. 497–515. — doi:10.1145/990308.990313.
• Fan Chung. Spectral Graph Theory. — AMS Publications, 1997. — Т. 92. — С. 212. — (CBMS Lecture Notes). — ISBN 0-8218-0315-8.
• Sinclair A. Algorithms for Random Generation and Counting: A Markov Chain Approach. — Boston-Basel-Berlin: Birkhauser, 1993. — (Progress in Theoretical Computer Science). — ISBN 0-8176-3658-7.
• Levin D., Peres Y., Wilmer E. L. Markov Chains and Mixing Times. — AMS, 2007.