Gráfico de conductividad

La conductividad gráfica G = ( V , E ) es una medida de densidad gráfica que controla la rapidez con la que un recorrido aleatorio en G converge en una distribución uniforme . La conductividad de un gráfico a menudo se conoce como la constante de Cheeger de un gráfico como un análogo de su contraparte en geometría espectral . Dado que los circuitos eléctricos están estrechamente relacionados con los paseos aleatorios y tienen una larga historia del término "conductividad", este nombre alternativo ayuda a evitar posibles confusiones.

La conductancia de un corte gráfico se define como: ${\ estilo de visualización (S, {\ bar {S)))}$

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

donde son los elementos de la matriz de adyacencia del grafo G , tal que $a_{{ij}}$

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

es el número total (o peso) de aristas que inciden en S . El valor también se denomina volumen del conjunto . ${\ estilo de visualización a (S)}$ $S\subconjunto V$

La conductividad de todo el gráfico es igual a la conductividad mínima sobre todos los cortes posibles:

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

De manera equivalente, la conductividad de un gráfico se define de la siguiente manera:

\phi (G):=\min_{S\subseteq V;0\leq a(S)\leq a(V)/2}{\frac {\sum_{i\in S,j\ en {\bar {S}}}a_{ij}}{a(S))).\,

Para un gráfico d -regular, la conductividad es igual al número isoperimétrico , dividido por d .

Generalizaciones y aplicaciones

En aplicaciones prácticas, la conductividad a menudo se considera solo a lo largo de la sección. Una generalización común de la conductividad es tener en cuenta los pesos asignados a los bordes; luego se suman los pesos. Si se utilizan pesos en forma de resistencia, se suman los recíprocos de los pesos.

El concepto de conducción proporciona una base para la filtración en la física y otros campos. Entonces, por ejemplo, la permeabilidad del aceite a través de los poros de una piedra se puede modelar en términos de la conductividad de un gráfico con pesos dados por los tamaños de los poros.

La conductividad también ayuda a medir la calidad del agrupamiento espectral . Las conductividades máximas de los agrupamientos proporcionan un límite que se puede usar junto con los pesos dentro de un agrupamiento para determinar una medida de la calidad del agrupamiento. Intuitivamente, la conductividad de un grupo (que se puede considerar como un conjunto de vértices en un gráfico) debería ser baja. Además, también se puede utilizar la conductancia del subgrafo generado por el grupo (llamado "conductancia intrínseca").

Cadenas de Markov

Para una cadena de Markov ergódica reversible con gráfico G , la conductancia es una forma de medir qué tan difícil es dejar un pequeño conjunto de nodos. Formalmente, la conductividad de un gráfico se determina al menos sobre todos los conjuntos de la capacidad del conjunto dividido por el flujo ergódico de . Alistair Sinclair demostró que la conductividad está estrechamente relacionada con el tiempo de mezcla en una cadena de Markov reversible ergódica. También podemos pensar en la conductancia en un sentido más probabilístico, como la mínima probabilidad de dejar un pequeño conjunto de nodos si partimos de un nodo dentro de ese conjunto. Denotado por la probabilidad condicional de abandonar el conjunto de nodos S, entonces la conductividad es igual al mínimo sobre todos los conjuntos que tienen una probabilidad estacionaria total que no excede 1/2. $S$ $S$ $S$ ${\ estilo de visualización \ Phi _ {S}}$ ${\ estilo de visualización \ Phi _ {S}}$ $S$

La conductividad está relacionada con el tiempo de mezclado en condiciones reversibles.

Véase también

Distancia resistiva

Notas

Literatura

Bella Bollobas. Teoría de grafos moderna. - Springer-Verlag , 1998. - T. 184. - S. 321. - ( GTM ). — ISBN 0-387-98488-7 .
Kannan R., Vempala S., Vetta A. Sobre agrupaciones: buenas, malas y espectrales // J. ACM. - 2004. - mayo ( vol. 51 , número 3 ). — S. 497–515 . -doi : 10.1145/ 990308.990313 .
ventilador chung. Teoría de grafos espectrales. - AMS Publications, 1997. - T. 92. - S. 212. - (CBMS Lecture Notes). — ISBN 0-8218-0315-8 .
Sinclair A. Algoritmos para generación y conteo aleatorios: un enfoque de cadena de Markov. - Boston-Basilea-Berlín: Birkhauser, 1993. - (Progreso en Informática Teórica). — ISBN 0-8176-3658-7 .
Levin D., Peres Y., Wilmer E. L. Markov Cadenas y tiempos de mezcla. —AMS, 2007.