Przewodność (wykres)

Nieskierowany wykres

G

i kilka przykładowych cięć z odpowiednimi przewodnictwami

W teorii grafów przewodnictwo wykresu $G = (V, E) mierzy$ , jak „dobry” jest wykres: kontroluje, jak szybko błądzenie losowe na $G$ zbiega się z rozkładem stacjonarnym . Przewodnictwo wykresu jest często nazywane stałą Cheegera wykresu jako odpowiednik jego odpowiednika w geometrii widmowej . ^{[ Potrzebne źródło ]} Ponieważ sieci elektryczne są ściśle związane z przypadkowymi spacerami z długą historią używania terminu „przewodnictwo”, ta alternatywna nazwa pomaga uniknąć możliwych nieporozumień.

Przewodnictwo cięcia na wykresie definiuje się jako: ${\ Displaystyle (S, {\ bar {S}})}$

\ Displaystyle \ varphi (S) = {\ Frac {\ suma _ {i \ in S,j\in {\bar {S}}}a_{ij}}{\min(a(S),a({\bar {S}})}}}}

gdzie a $ij są$ wpisami macierzy sąsiedztwa dla $G$ , tak że

{ij}}

jest całkowitą liczbą (lub wagą) krawędzi incydentnych z $S$ . $za (S)$ jest również nazywany objętością zbioru ${\ Displaystyle S \ subseteq V}$ .

Przewodnictwo całego wykresu to minimalne przewodnictwo we wszystkich możliwych przekrojach:

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

Równoważnie przewodnictwo wykresu definiuje się następująco:

{\ Displaystyle \ phi (G): = \ min _ {S \ subseteq V; 0 \ równoważnik a (S) \ równoważnik a (V) / 2} {\ Frac {\ suma _ {i \ w S, j \ w {\bar {S}}}a_{ij}}{a(S)}}.\,}

Dla wykresu $d$ -regularnego przewodnictwo jest równe liczbie izoperymetrycznej podzielonej przez $d$ .

Uogólnienia i zastosowania

W praktycznych zastosowaniach często bierze się pod uwagę przewodnictwo tylko w przekroju. Powszechnym uogólnieniem przewodnictwa jest obsłużenie przypadku wag przypisanych do krawędzi: następnie wagi są dodawane; jeśli ciężar ma postać oporu, wówczas dodaje się odwrotne ciężary.

Pojęcie przewodnictwa leży u podstaw badań perkolacji w fizyce i innych stosowanych obszarach; tak więc na przykład przepuszczalność ropy naftowej przez porowatą skałę można modelować za pomocą wykresu przewodnictwa, z wagami określonymi przez rozmiary porów.

Przewodnictwo pomaga również mierzyć jakość klastrów spektralnych . Maksimum wśród przewodnictwa klastrów zapewnia granicę, której można użyć wraz z wagą krawędzi między klastrami do zdefiniowania miary jakości grupowania. Intuicyjnie przewodnictwo klastra (które można postrzegać jako zbiór wierzchołków grafu) powinno być niskie. Oprócz tego można również wykorzystać przewodnictwo podgrafu indukowane przez klaster (zwane „przewodnictwem wewnętrznym”).

Łańcuchy Markowa

W przypadku ergodycznego odwracalnego łańcucha Markowa z podstawowym wykresem G przewodnictwo jest sposobem na zmierzenie, jak trudno jest opuścić mały zestaw węzłów. Formalnie przewodnictwo wykresu definiuje się jako minimum we wszystkich zestawach $S}$ podzielonej przez ergodyczny wypływ z $S$ { $displaystyle$ Alistair Sinclair wykazał, że przewodnictwo jest ściśle związane z czasem mieszania w ergodycznych odwracalnych łańcuchach Markowa. Możemy również spojrzeć na przewodnictwo w sposób bardziej probabilistyczny, jako minimalne prawdopodobieństwo pozostawienia małego zestawu węzłów, biorąc pod uwagę, że zaczynaliśmy od tego zestawu. Pisząc ${S}} Φ S {\ displaystyle \ Phi _$ , biorąc pod uwagę, że byliśmy w tym zestawie na początku, przewodnictwo jest minimalne $S}} }}$ nad zbiorami $.$ które mają całkowite stacjonarne prawdopodobieństwo co najwyżej 1/2

Przewodnictwo jest związane z czasem mieszania łańcucha Markowa w układzie odwracalnym.

Zobacz też

Béla Bollobás (1998). Współczesna teoria grafów . GTM . Tom. 184. Springer-Verlag . P. 321. ISBN 0-387-98488-7 .
Kannan, R.; Vempala, S.; Vetta, A. (maj 2004). „O klastrach: dobre, złe i widmowe” (PDF) . J.ACM . 51 (3): 497–515. doi : 10.1145/990308.990313 .
Fan Chung (1997). Teoria grafów widmowych . Notatki z wykładów CBMS. Tom. 92. Publikacje AMS. P. 212. ISBN 0-8218-0315-8 .
A. Sinclaira. Algorytmy generowania i liczenia losowego: podejście łańcuchowe Markowa . Birkhauser, Boston-Bazylea-Berlin, 1993.
D. Levin, Y. Peres , EL Wilmer : Łańcuchy Markowa i czasy mieszania