Провідність графа — міра щільності графа, яка показує, наскільки швидко випадкове блукання на збігається до рівномірного розподілу. Провідність графа часто називають сталою Чіґера графа, як аналог її двійника в [en]. Оскільки електричні кола тісно пов'язані з випадковими блуканнями та мають довгу історію застосування терміна «провідність», ця альтернативна назва допомагає уникнути можливої плутанини.
Провідність розрізу графа визначають як:
де — елементи матриці суміжності графа , так що
є повним числом (або вагою) ребер, інцидентних . Значення також називають об'ємом множини .
Провідність усього графа дорівнює найменшій провідності за всіма можливими розрізами:
Еквівалентно, провідність графа визначають так:
Для -регулярного графа провідність дорівнює ізопериметричному числу, поділеному на .
Узагальнення та застосування
У практичних застосуваннях часто розглядають провідність лише за розрізом. Частим узагальненням провідності є врахування ваг, призначених ребрам — тоді підсумовують ваги. Якщо ваги відіграють роль опору, то підсумовують величини, обернені вагам.
Поняття провідності лежить застосовується для вивчення перколяції у фізиці та в інших галузях. Тоді, наприклад, проникнення нафти через пори каменю можна моделювати в термінах провідності графа з вагами, заданими розмірами пор.
Провідність допомагає також виміряти якість спектрального кластерування. Максимум провідностей кластерів дає межу, яку можна використати разом із вагами всередині кластера для визначення міри якості кластеризації. Інтуїтивно провідність кластера (який можна розглядати як множину вершин графа) має бути низькою. Крім того, можна також використовувати провідність підграфа, породженого кластером (називану внутрішньою провідністю).
Марковські ланцюги
Для ергодичного оборотного ланцюга Маркова з графом провідність є способом вимірювання, наскільки важко покинути невелику множину вузлів. Формально провідність графа визначають як мінімум за всіма множинами ємності множини , поділеної на [en] із . [en] показав, що провідність тісно пов'язана з [en] в ергодичному оборотному ланцюгу Маркова. Можна також розглядати провідність у більш імовірнісному сенсі як найменшу ймовірність покинути малу множину вузлів, якщо почати з вузла всередині цієї множини. Позначимо через умовну ймовірність покинути множину вузлів , тоді провідність дорівнює найменшому за всіма множинами , які мають повну стаціонарну ймовірність, що не перевищує 1/2.
Провідність пов'язана з часом змішування в оборотних умовах.
Див. також
Примітки
Література
- Béla Bollobás. Modern graph theory. — Springer-Verlag, 1998. — Т. 184. — С. 321. — () — .
- Kannan R., Vempala S., Vetta A. On clusterings: Good, bad and spectral // J. ACM. — 2004. — Т. 51, вип. 3 (May). — С. 497–515. — DOI: .
- Fan Chung. Spectral Graph Theory. — AMS Publications, 1997. — Т. 92. — С. 212. — (CBMS Lecture Notes) — .
- Sinclair A. Algorithms for Random Generation and Counting: A Markov Chain Approach. — Boston-Basel-Berlin : Birkhauser, 1993. — (Progress in Theoretical Computer Science) — .
- Levin D., Peres Y., Wilmer E. L. Markov Chains and Mixing Times. — AMS, 2007.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Providnist grafa G V E displaystyle G V E mira shilnosti grafa yaka pokazuye naskilki shvidko vipadkove blukannya na G displaystyle G zbigayetsya do rivnomirnogo rozpodilu Providnist grafa chasto nazivayut staloyu Chigera grafa yak analog yiyi dvijnika v en Oskilki elektrichni kola tisno pov yazani z vipadkovimi blukannyami ta mayut dovgu istoriyu zastosuvannya termina providnist cya alternativna nazva dopomagaye uniknuti mozhlivoyi plutanini Providnist rozrizu S S displaystyle S bar S grafa viznachayut yak f S i S j S aijmin a S a S displaystyle varphi S frac sum i in S j in bar S a ij min a S a bar S de aij displaystyle a ij elementi matrici sumizhnosti grafa G displaystyle G tak sho a S i S j Vaij displaystyle a S sum i in S sum j in V a ij ye povnim chislom abo vagoyu reber incidentnih S displaystyle S Znachennya a S displaystyle a S takozh nazivayut ob yemom mnozhini S V displaystyle S subseteq V Providnist usogo grafa dorivnyuye najmenshij providnosti za vsima mozhlivimi rozrizami ϕ G minS Vf S displaystyle phi G min S subseteq V varphi S Ekvivalentno providnist grafa viznachayut tak ϕ G minS V 0 a S a V 2 i S j S aija 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 Dlya d displaystyle d regulyarnogo grafa providnist dorivnyuye izoperimetrichnomu chislu podilenomu na d displaystyle d Uzagalnennya ta zastosuvannyaU praktichnih zastosuvannyah chasto rozglyadayut providnist lishe za rozrizom Chastim uzagalnennyam providnosti ye vrahuvannya vag priznachenih rebram todi pidsumovuyut vagi Yaksho vagi vidigrayut rol oporu to pidsumovuyut velichini oberneni vagam Ponyattya providnosti lezhit zastosovuyetsya dlya vivchennya perkolyaciyi u fizici ta v inshih galuzyah Todi napriklad proniknennya nafti cherez pori kamenyu mozhna modelyuvati v terminah providnosti grafa z vagami zadanimi rozmirami por Providnist dopomagaye takozh vimiryati yakist spektralnogo klasteruvannya Maksimum providnostej klasteriv daye mezhu yaku mozhna vikoristati razom iz vagami vseredini klastera dlya viznachennya miri yakosti klasterizaciyi Intuyitivno providnist klastera yakij mozhna rozglyadati yak mnozhinu vershin grafa maye buti nizkoyu Krim togo mozhna takozh vikoristovuvati providnist pidgrafa porodzhenogo klasterom nazivanu vnutrishnoyu providnistyu Markovski lancyugiDlya ergodichnogo oborotnogo lancyuga Markova z grafom G displaystyle G providnist ye sposobom vimiryuvannya naskilki vazhko pokinuti neveliku mnozhinu vuzliv Formalno providnist grafa viznachayut yak minimum za vsima mnozhinami S displaystyle S yemnosti mnozhini S displaystyle S podilenoyi na en iz S displaystyle S en pokazav sho providnist tisno pov yazana z en v ergodichnomu oborotnomu lancyugu Markova Mozhna takozh rozglyadati providnist u bilsh imovirnisnomu sensi yak najmenshu jmovirnist pokinuti malu mnozhinu vuzliv yaksho pochati z vuzla vseredini ciyeyi mnozhini Poznachimo cherez FS displaystyle Phi S umovnu jmovirnist pokinuti mnozhinu vuzliv S displaystyle S todi providnist dorivnyuye najmenshomu FS displaystyle Phi S za vsima mnozhinami S displaystyle S yaki mayut povnu stacionarnu jmovirnist sho ne perevishuye 1 2 Providnist pov yazana z chasom zmishuvannya v oborotnih umovah Div takozhRezistivna vidstanPrimitkiLiteraturaBela Bollobas Modern graph theory Springer Verlag 1998 T 184 S 321 ISBN 0 387 98488 7 Kannan R Vempala S Vetta A On clusterings Good bad and spectral J ACM 2004 T 51 vip 3 May S 497 515 DOI 10 1145 990308 990313 Fan Chung Spectral Graph Theory AMS Publications 1997 T 92 S 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