Vodivost (graf) - Conductance (graph)

Neusměrněný graf G a několik příkladů řezů s odpovídajícími vodivostmi

v teorie grafů the vodivost a graf G=(PROTI,E) měří, jak je graf „dobře propojený“: řídí, jak rychle a náhodná procházka na G konverguje k jeho stacionární distribuce. Vodivost grafu se často nazývá Cheegerova konstanta grafu jako analog jeho protějšek v spektrální geometrie.^{[Citace je zapotřebí ]} Od té doby elektrické sítě jsou úzce spjaty s náhodné procházky s dlouhou historií v používání termínu „vodivost“ tento alternativní název pomáhá předcházet možné záměně.

Vodivost a střih ${displaystyle (S, {ar {S}})}$ v grafu je definována jako:

{displaystyle varphi (S) = {frac {sum _ {iin S, jin {ar {S}}} a_ {ij}} {min (a (S), a ({ar {S}}))}}}

Kde ${displaystyle a_ {ij}}$ jsou položky matice sousedství pro G, aby

{displaystyle a (S) = součet _ {iin S} součet _ {jin V} a_ {ij}}

je celkový počet (nebo váha) okrajů dopadajících na S. ${displaystyle a (S)}$ se také nazývá svazek sady ${displaystyle Ssubseteq V}$ .

Vodivost celého grafu je minimální vodivost ve všech možných řezech:

{displaystyle phi (G) = min _ {Ssubseteq V} varphi (S).}

Ekvivalentně je vodivost grafu definována takto:

{displaystyle phi (G): = min _ {Ssubseteq V; 0leq a (S) leq a (V) / 2} {frac {sum _ {iin S, jin {ar {S}}} a_ {ij}} { tak jako)}}.,}

Pro d-pravidelný graf, vodivost se rovná izoperimetrické číslo děleno d.

Zobecnění a aplikace

V praktických aplikacích se často uvažuje vodivost pouze přes řez. Běžným zevšeobecněním vodivosti je zvládnout případ závaží přiřazených hranám: pak se váhy přidají; pokud je váha ve formě odporu, pak se vzájemné váhy přidají.

Pojem vodivosti je základem studie perkolace ve fyzice a dalších aplikovaných oblastech; například propustnost ropy přes porézní horninu lze modelovat z hlediska vodivosti grafu s váhami danými velikostmi pórů.

Vodivost také pomáhá měřit kvalitu a Spektrální shlukování. Maximum mezi vodivostí klastrů poskytuje hranici, kterou lze spolu s hraniční váhou mezi klastry použít k definování míry kvality klastrování. Intuitivně by měla být vodivost klastru (kterou lze v grafu vidět jako soubor vrcholů) nízká. Kromě toho lze také použít vodivost podgrafu indukovanou klastrem (nazývanou „vnitřní vodivost“).

Markovovy řetězy

Pro ergodický reverzibilní Markovův řetězec s podkladem graf G, vodivost je způsob, jak měřit, jak těžké je opustit malou sadu uzlů. Formálně je vodivost grafu definována jako minimum ve všech sadách ${displaystyle S}$ z kapacita z ${displaystyle S}$ děleno ergodický tok mimo ${displaystyle S}$ . Alistair Sinclair ukázal, že vodivost je úzce spjata doba míchání v ergodických reverzibilních Markovových řetězcích. Můžeme také zobrazit vodivost pravděpodobnějším způsobem, jako minimální pravděpodobnost opuštění malé sady uzlů vzhledem k tomu, že jsme v této sadě začali. Psaní ${displaystyle Phi _ {S}}$ pro podmíněnou pravděpodobnost opuštění sady uzlů S vzhledem k tomu, že jsme byli v této sadě pro začátek, je vodivost minimální ${displaystyle Phi _ {S}}$ přes sady ${displaystyle S}$ které mají celkovou stacionární pravděpodobnost nejvýše 1/2.

Vodivost souvisí s Doba míchání Markovova řetězce v reverzibilním nastavení.

Viz také

Reference

Béla Bollobás (1998). Moderní teorie grafů. GTM. 184. Springer-Verlag. p. 321. ISBN 0-387-98488-7.
Kannan, R .; Vempala, S .; Vetta, A. (květen 2004). „O shlucích: dobré, špatné a spektrální“ (PDF). J. ACM. 51 (3): 497–515. doi:10.1145/990308.990313.
Fan Chung (1997). Teorie spektrálního grafu. Poznámky k přednášce CBMS. 92. Publikace AMS. p. 212. ISBN 0-8218-0315-8.
A. Sinclair. Algoritmy pro náhodnou generaci a počítání: Markovův řetězový přístup. Birkhauser, Boston-Basel-Berlin, 1993.
D. Levin, Y. Peres, E. L. Wilmer: Markovovy řetězce a časy míchání