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

Проводимость графа 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.

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

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

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

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

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

Для эргодичной обратимой цепи Маркова с графом G, проводимость является способом измерения, насколько трудно покинуть малое множество узлов. Формально проводимость графа определяется как минимум по всем множествам ${\displaystyle S}$ ёмкости множества ${\displaystyle S}$, делённой на эргодический поток^[англ.] из ${\displaystyle S}$. Алистер Синклер показал, что проводимость тесно связана с временем смешивания^[англ.] в эргодичной обратимой цепи Маркова. Мы можем также рассматривать проводимость в более вероятностном смысле, как минимальную вероятность покинуть малый набор узлов, если мы начинаем из узла внутри этого множества. Обозначим через ${\displaystyle \Phi _{S}}$ условную вероятность покинуть множество узлов S, проводимость тогда равна минимальному ${\displaystyle \Phi _{S}}$ по всем множествам ${\displaystyle 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.

Эта страница в последний раз была отредактирована 20 июля 2021 в 13:52.