Vezetőképességi grafikon

A grafikon vezetőképesség G =( V , E ) egy gráfsűrűség-mérés, amely azt szabályozza, hogy a G -n egy véletlenszerű séta milyen gyorsan konvergál egy egyenletes eloszláshoz . Egy gráf vezetőképességét gyakran a gráf Cheeger-állandójának nevezik, mint a spektrális geometriában megfelelő megfelelőjének analógját . Mivel az elektromos áramkörök szorosan kapcsolódnak a véletlenszerű sétákhoz , és régóta használják a „vezetőképesség” kifejezést, ez az alternatív név segít elkerülni az esetleges összetévesztést.

A grafikonvágás vezetőképességét a következőképpen határozzuk meg: $(S,{\bar {S)))$

\varphi (S)={\frac {\sum _{i\in S,j\in {\bar {S))}a_{ij)){\min(a(S),a({ \bar {S}})))}}

hol vannak a G gráf szomszédsági mátrixának elemei , így $a_{{ij}}$

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

az S -re eső élek teljes száma (vagy súlya) . Az értéket a halmaz térfogatának is nevezik . $a(S)$ $S\subseteq V$

A teljes gráf vezetőképessége egyenlő a minimális vezetőképességgel az összes lehetséges vágáson:

\phi (G)=\min _{S\subseteq V}\varphi (S).

Ezzel egyenértékűen egy gráf vezetőképességét a következőképpen határozzuk meg:

\phi (G):=\min _{S\subseteq V;0\leq a(S)\leq a(V)/2}{\frac {\sum _{i\in S,j\ a {\barban {S}}}a_{ij}}{a(S))).\,

Egy d -szabályos gráf esetén a vezetőképesség egyenlő az izoperimetrikus számmal , osztva d -vel .

Általánosítások és alkalmazások

A gyakorlati alkalmazásokban a vezetőképességet gyakran csak a szakasz mentén veszik figyelembe. A vezetőképesség általános általánosítása, hogy figyelembe kell venni az élekhez rendelt súlyokat – ezután a súlyokat hozzáadjuk. Ha a súlyokat ellenállás formájában használjuk, akkor a súlyok reciprokait összeadjuk.

A vezetés fogalma alapot ad a perkolációhoz a fizikában és más területeken. Ekkor például a kő pórusain áthaladó olaj áteresztőképessége modellezhető a pórusméretek által megadott súlyokkal egy gráf vezetőképességével.

A vezetőképesség a spektrális klaszterezés minőségének mérésében is segít . A klaszterek maximális vezetőképessége olyan korlátot ad, amely a klaszteren belüli súlyokkal együtt használható a klaszter minőségének meghatározására. Intuitív módon egy klaszter vezetőképességének (amely egy gráf csúcsainak halmazaként fogható fel) alacsonynak kell lennie. Ezenkívül a klaszter által generált részgráf vezetőképessége (úgynevezett "belső vezetőképesség") is használható.

Markov láncok

A G gráfot tartalmazó ergodikus reverzibilis Markov-lánc esetében a vezetőképesség egy módja annak, hogy mérjük, mennyire nehéz elhagyni egy kis csomóponthalmazt. Formálisan egy gráf vezetőképességét legalább a halmaz kapacitásának az összes halmazára meghatározzuk , osztva az ergodikus áramlással ] . Alistair Sinclair kimutatta, hogy a vezetőképesség szorosan összefügg a keveredési idővel egy ergodikus reverzibilis Markov-láncban. Valószínűbb értelemben is gondolhatunk a vezetőképességre, mint annak minimális valószínűségére, hogy elhagyunk egy kis csomóponthalmazt, ha a halmazon belüli csomópontból indulunk ki. Jelölje az S csomópontok halmazának elhagyásának feltételes valószínűségét, ekkor a vezetőképesség egyenlő a minimummal minden olyan halmazra vonatkozóan, amelyek teljes stacionárius valószínűsége nem haladja meg az 1/2-t. $S$ $S$ $S$ $\Phi _{S}$ $\Phi _{S}$ $S$

A vezetőképesség a keverési idővel van összefüggésben reverzibilis körülmények között.

Lásd még

Ellenállási távolság

Jegyzetek

Irodalom

Bollobas Béla. Modern gráfelmélet. - Springer-Verlag , 1998. - T. 184. - S. 321. - ( GTM ). — ISBN 0-387-98488-7 .
Kannan R., Vempala S., Vetta A. A klaszterezésről: Jó, rossz és spektrális // J. ACM. - 2004. - május ( 51. évf. , 3. szám ). – S. 497–515 . - doi : 10.1145/990308.990313 .
fan chung. Spektrális gráf elmélet. - AMS Publications, 1997. - T. 92. - S. 212. - (CBMS Lecture Notes). — ISBN 0-8218-0315-8 .
Sinclair A. Véletlenszerű generálás és számlálás algoritmusai: Markov-lánc megközelítés. - Boston-Basel-Berlin: Birkhauser, 1993. - (Előrehaladás az elméleti számítástechnikában). — ISBN 0-8176-3658-7 .
Levin D., Peres Y., Wilmer E. L. Markov Chains and Mixing Times. – AMS, 2007.