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

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

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

$\mathrm{\phi <!--\; \phi \; -->}(S)=\frac{\underset{i\in <!--\; \in \; -->S,j\in <!--\; \in \; -->\stackrel{¯<!--\; ¯\; -->}{S}}{\sum <!--\; \sum \; -->}{a}_{ij}}{min(a(S),a(\stackrel{¯<!--\; ¯\; -->}{S}))}$$\varphi (S)={\frac {\sum _{i\in S,j\in {\bar {S}}}a_{ij}}{\min(a(S),a({\bar {S}}))}}$

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

$a(S)=\underset{i\in <!--\; \in \; -->S}{\sum <!--\; \sum \; -->}\underset{j\in <!--\; \in \; -->V}{\sum <!--\; \sum \; -->}{a}_{ij}$$a(S)=\sum _{i\in S}\sum _{j\in V}a_{ij}$

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

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

$\mathrm{\varphi <!--\; \varphi \; -->}(G)=\underset{S\subseteq <!--\; \subseteq \; -->V}{min}\mathrm{\phi <!--\; \phi \; -->}(S).$$\phi (G)=\min _{S\subseteq V}\varphi (S).$

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

$\mathrm{\varphi <!--\; \varphi \; -->}(G):=\underset{S\subseteq <!--\; \subseteq \; -->V;0\le <!--\; \le \; -->a(S)\le <!--\; \le \; -->a(V)/2}{min}\frac{\underset{i\in <!--\; \in \; -->S,j\in <!--\; \in \; -->\stackrel{¯<!--\; ¯\; -->}{S}}{\sum <!--\; \sum \; -->}{a}_{ij}}{a(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$$S$ , делённой на эргодический поток^[en] из $S$$S$ . Алистер Синклер показал, что проводимость тесно связана с временем смешивания^[en] в эргодичной обратимой цепи Маркова. Мы можем также рассматривать проводимость в более вероятностном смысле, как минимальную вероятность покинуть малый набор узлов, если мы начинаем из узла внутри этого множества. Обозначим через ${\mathrm{\Phi <!--\; \Phi \; -->}}_S$$\Phi _{S}$  условную вероятность покинуть множество узлов S, проводимость тогда равна минимальному ${\mathrm{\Phi <!--\; \Phi \; -->}}_S$$\Phi _{S}$  по всем множествам $S$$S$ , которые имеют полную стационарную вероятность, не превосходящую 1/2.

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

См. такжеПравить

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

ЛитератураПравить

• 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.