Википедия

Проводимость графа: различия между версиями

Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
мНет описания правки
Метки: через визуальный редактор с мобильного устройства из мобильной версии
м оформление, проверка орф., пункт.
Строка 1:
'''Проводимость''' [[Граф (математика)|графа]] ''G''=(''V'',''E'')  — это измерение плотности графа, которое контролирует, насколько быстро [[случайное блуждание]] на ''G'' сходится к [[Дискретное равномерное распределение|равномерному распределению]]. Проводимость графа часто называется [[Константа Чигера (теория графов)|константой Чигера]] графа как аналог его [[Константа Чигера|двойника]] в {{не переведено 5|спектральная геометрия|спектральной геометрии||spectral geometry}}. Поскольку [[Электрическая цепь|электрические цепи]] тесно связаны со [[Случайное блуждание|случайными блужданиями]] и имеют длинную историю применения термина «проводимость», это альтернативное название помогает избежать возможную путаницу.
 
Проводимость [[Разрез графа|разреза]] <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>.
Строка 19:
: <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''.
 
== Обобщения и приложения ==
В практических приложениях часто рассматривается проводимость только по разрезу. Частым обобщением проводимости является учёт весов, назначенных рёбрам  — тогда складываются веса. Если веса употребляются в виде сопротивления, то складываются обратные весам величины.
 
Понятие проводимости подводит основу к [[Перколяция|перколяции]] в физике и другим областям. Тогда, например, проницаемость масла через поры камня можно моделировать в терминах проводимости графа с весами, заданными размерами пор.
Строка 29:
 
== Марковские цепи ==
Для [[Эргодичность|эргодичной]] обратимой [[Цепь Маркова|цепи Маркова]] с [[Объектный граф|графом]] ''G'', проводимость является способом измерения, насколько трудно покинуть малое множество узлов. Формально проводимость графа определяется как минимум по всем множествам <math>S</math> [[Транспортная сеть|ёмкости]] множества <math>S</math>, делённой на {{не переведено 5|эргодический поток|||ergodic flow}} из <math>S</math>. [[Синклер, Алистер|Алистер Синклер]] показал, что проводимость тесно связана с {{не переведено 5|Время смешивания марковской цепи|временем смешивания||markov chain mixing time}} в эргодичной обратимой цепи Маркова. Мы можем также рассматривать проводимость в более вероятностном смысле, как минимальную вероятность покинуть малый набор узлов, если мы начинаем из узла внутри этого множества. Обозначим через <math>\Phi_S</math> условную вероятность покинуть множество узлов S, проводимость тогда равна минимальному <math>\Phi_S</math> по всем множествам <math>S</math>, которые имеют полную [[Стационарное распределение|стационарную вероятность]], не превосходящую 1/2.▼
 
▲Для [[Эргодичность|эргодичной]] обратимой [[Цепь Маркова|цепи Маркова]] с [[Объектный граф|графом]] ''G'', проводимость является способом измерения, насколько трудно покинуть малое множество узлов. Формально проводимость графа определяется как минимум по всем множествам <math>S</math> [[Транспортная сеть|ёмкости]] множества <math>S</math>, делённой на {{не переведено 5|эргодический поток|||ergodic flow}} из <math>S</math>. [[Синклер, Алистер|Алистер Синклер]] показал, что проводимость тесно связана с {{не переведено 5|Время смешивания марковской цепи|временем смешивания||markov chain mixing time}} в эргодичной обратимой цепи Маркова. Мы можем также рассматривать проводимость в более вероятностном смысле, как минимальную вероятность покинуть малый набор узлов, если мы начинаем из узла внутри этого множества. Обозначим через <math>\Phi_S</math> условную вероятность покинуть множество узлов S, проводимость тогда равна минимальному <math>\Phi_S</math> по всем множествам <math>S</math>, которые имеют полную [[Стационарное распределение|стационарную вероятность]], не превосходящую 1/2.
 
Проводимость связана с {{не переведено 5|Время смешивания марковской цепи|временем смешивания||markov chain mixing time}} в обратимых условиях.
Строка 38 ⟶ 37 :
 
== Примечания ==
{{примечания|2}}
 
== Литература ==
{{refbegin|colwidth=30em}}
* {{книга
|автор=Béla Bollobás
Строка 94 ⟶ 92 :
|заглавие=Markov Chains and Mixing Times
}}
{{refend}}
 
[[Категория:Марковские процессы]]
[[Категория:Алгебраическая теория графов]]
[[Категория:Инварианты графов]]
{{rq|checktranslate|style|grammar}}
Источник — https://ru.wikipedia.org/wiki/Проводимость_графа