Провідність графа

Провідність графа ${\displaystyle G=(V,E)}$ — міра щільності графа, яка показує, наскільки швидко випадкове блукання на ${\displaystyle G}$ збігається до рівномірного розподілу. Провідність графа часто називають сталою Чіґера графа, як аналог її двійника в спектральній геометрії^[en]. Оскільки електричні кола тісно пов'язані з випадковими блуканнями та мають довгу історію застосування терміна «провідність», ця альтернативна назва допомагає уникнути можливої плутанини.

Провідність розрізу ${\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}}$ — елементи матриці суміжності графа ${\displaystyle G}$, так що

${\displaystyle a(S)=\sum _{i\in S}\sum _{j\in V}a_{ij}}$

є повним числом (або вагою) ребер, інцидентних ${\displaystyle 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)}}.\,}$

Для ${\displaystyle d}$-регулярного графа провідність дорівнює ізопериметричному числу, поділеному на ${\displaystyle d}$.

Узагальнення та застосування

У практичних застосуваннях часто розглядають провідність лише за розрізом. Частим узагальненням провідності є врахування ваг, призначених ребрам — тоді підсумовують ваги. Якщо ваги відіграють роль опору, то підсумовують величини, обернені вагам.

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

Провідність допомагає також виміряти якість спектрального кластерування. Максимум провідностей кластерів дає межу, яку можна використати разом із вагами всередині кластера для визначення міри якості кластеризації. Інтуїтивно провідність кластера (який можна розглядати як множину вершин графа) має бути низькою. Крім того, можна також використовувати провідність підграфа, породженого кластером (називану внутрішньою провідністю).

Марковські ланцюги

Для ергодичного оборотного ланцюга Маркова з графом ${\displaystyle G}$ провідність є способом вимірювання, наскільки важко покинути невелику множину вузлів. Формально провідність графа визначають як мінімум за всіма множинами ${\displaystyle S}$ ємності множини ${\displaystyle S}$, поділеної на ергодичний потік^[en] із ${\displaystyle S}$. Алістер Синклер^[en] показав, що провідність тісно пов'язана з часом змішування^[en] в ергодичному оборотному ланцюгу Маркова. Можна також розглядати провідність у більш імовірнісному сенсі як найменшу ймовірність покинути малу множину вузлів, якщо почати з вузла всередині цієї множини. Позначимо через ${\displaystyle \Phi _{S}}$ умовну ймовірність покинути множину вузлів ${\displaystyle 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 (May). — С. 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.