Русская Википедия:Проводимость графа
Проводимость графа G=(V,E) — это измерение плотности графа, которое контролирует, насколько быстро случайное блуждание на G сходится к равномерному распределению. Проводимость графа часто называется константой Чигера графа как аналог его двойника в Шаблон:Не переведено 5. Поскольку электрические цепи тесно связаны со случайными блужданиями и имеют длинную историю применения термина «проводимость», это альтернативное название помогает избежать возможную путаницу.
Проводимость разреза <math>(S, \bar S)</math> графа определяется как:
- <math>\varphi(S)=\frac{\sum_{i \in S, j \in \bar S}a_{ij}}{\min(a(S),a(\bar S))}</math>
где <math>a_{ij}</math> являются элементами матрицы смежности графа G, так что
- <math>a(S)=\sum_{i \in S} \sum_{j \in V} a_{ij}</math>
является полным числом (или весом) рёбер, инцидентных S. Значение <math>a(S)</math> также называется объёмом множества <math>S \subseteq V</math>.
Проводимость всего графа равна минимальной проводимости по всем возможным разрезам:
- <math>\phi(G)=\min_{S \subseteq V}\varphi(S).</math>
Эквивалентно, проводимость графа определяется следующим образом:
- <math>\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)}.\,</math>
Для d-регулярного графа проводимость равна изопериметрическому числу, делённому на d.
Обобщения и приложения
В практических приложениях часто рассматривается проводимость только по разрезу. Частым обобщением проводимости является учёт весов, назначенных рёбрам — тогда складываются веса. Если веса употребляются в виде сопротивления, то складываются обратные весам величины.
Понятие проводимости подводит основу к перколяции в физике и другим областям. Тогда, например, проницаемость масла через поры камня можно моделировать в терминах проводимости графа с весами, заданными размерами пор.
Проводимость помогает также измерить качество спектральной кластеризации. Максимум проводимостей кластеров даёт границу, которая может быть использована вместе с весами внутри кластера для определения меры качества кластеризации. Интуитивно проводимость кластера (который можно рассматривать как множество вершин в графе) должна быть низкой. Кроме того, может также использоваться проводимость подграфа, порождённого кластером (называемая «внутренней проводимостью»).
Марковские цепи
Для эргодичной обратимой цепи Маркова с графом G, проводимость является способом измерения, насколько трудно покинуть малое множество узлов. Формально проводимость графа определяется как минимум по всем множествам <math>S</math> ёмкости множества <math>S</math>, делённой на Шаблон:Не переведено 5 из <math>S</math>. Алистер Синклер показал, что проводимость тесно связана с Шаблон:Не переведено 5 в эргодичной обратимой цепи Маркова. Мы можем также рассматривать проводимость в более вероятностном смысле, как минимальную вероятность покинуть малый набор узлов, если мы начинаем из узла внутри этого множества. Обозначим через <math>\Phi_S</math> условную вероятность покинуть множество узлов S, проводимость тогда равна минимальному <math>\Phi_S</math> по всем множествам <math>S</math>, которые имеют полную стационарную вероятность, не превосходящую 1/2.
Проводимость связана с Шаблон:Не переведено 5 в обратимых условиях.
См. также
Примечания
Литература
