Проводимость графа: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
мНет описания правки Метки: через визуальный редактор с мобильного устройства из мобильной версии |
Liasmi (обсуждение | вклад) м оформление, проверка орф., пункт. |
||
Строка 1:
'''Проводимость''' [[Граф (математика)|графа]] ''G''=(''V'',''E'')
Проводимость [[Разрез графа|разреза]] <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''-регулярного графа проводимость равна [[Константа Чигера (теория графов)|изопериметрическому числу]],
== Обобщения и приложения ==
В практических приложениях часто рассматривается проводимость только по разрезу. Частым обобщением проводимости является учёт весов, назначенных рёбрам
Понятие проводимости подводит основу к [[Перколяция|перколяции]] в физике и другим областям. Тогда, например, проницаемость масла через поры камня можно моделировать в терминах проводимости графа с весами, заданными размерами пор.
Строка 29:
== Марковские цепи ==
Для [[Эргодичность|эргодичной]] обратимой [[Цепь Маркова|цепи Маркова]] с [[Объектный граф|графом]] ''G'', проводимость является способом измерения, насколько трудно покинуть малое множество узлов. Формально проводимость графа определяется как минимум по всем множествам <math>S</math>
▲Для [[Эргодичность|эргодичной]] обратимой [[Цепь Маркова|цепи Маркова]] с [[Объектный граф|графом]] ''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 :
== Примечания ==
{{примечания
== Литература ==
* {{книга
|автор=Béla Bollobás
Строка 94 ⟶ 92 :
|заглавие=Markov Chains and Mixing Times
}}
[[Категория:Марковские процессы]]
[[Категория:Алгебраическая теория графов]]
[[Категория:Инварианты графов]]
{{rq|checktranslate|style
|