Ponderado Regular Gráficos

Question

El siguiente gráfico teórico de la noción apareció en una economía de papel titulado: "Premio de la competencia en virtud de comparabilidad limitada, por Michele Piccione y Corrió Spiegler que los estudios de los modelos de la economía fueron las empresas son racionales, pero los consumidores no lo son.

Un grafo es ponderado-regular si los vértices (nodos) pueden ser asignados positivos pesos, de tal forma que cada nodo tiene el mismo ponderado total-espera-número de aristas (enlaces). Cada gráfico es, por supuesto, ponderado regular (dar todos los vértices de peso 1). Una estrella, un árbol con el centro de vértices conectados a k de las hojas se pondera-regular: Dar el centro de peso 1 y cada una de las hojas de peso 1/k.

(En el papel, cada vértice está también contenida en un bucle. Por lo tanto, su peso también se tiene en cuenta cuando se calcula su ponderado-espera-número de aristas. La estrella es todavía ponderado-regular: dar peso de 1 para el centro y peso de 0 a las hojas.)

Hay una caracterización de la ponderación de regular los gráficos? Es esta idea? No se han conocido las aplicaciones o las conexiones?

Answer 1

He aquí una observación acerca de una relación entre regular y ponderado regular los gráficos, cuando los bucles no están permitidos.

De cualquier ponderado gráfico regular con (wolog por la poliédrica de la caracterización integral de pesos, reemplazar cada vértice v con peso(v) en los clones. La nueva gráfica tiene |V| igual al peso original de la suma. Para cada arista uv en el antiguo gráfico, conecte cada clon de u para cada clon de v en el nuevo gráfico (por lo que hay una completa bipartito $K_{weight(u), weight(v)}$ entre los clones de u y v). Entonces este es un gráfico regular.

Por el contrario, usted puede invertir en esto, así que usted debe ser capaz de definir un uno-a-muchos tipos de "cociente" (a la inversa de la anterior construcción) que toma cualquier gráfico regular a un ponderado gráfico regular, y es surjective (genera todos los loopless ponderado regular gráficos).

Answer 2

Denotando por $A$ $n\times n$ adjaceny de la matriz (con bucles contribuyendo $1$ en la diagonal) de una finito gráfico de $\Gamma$ $n$ vértices, una condición necesaria para $A$ a ser ponderado regular es el hecho de que todas las $1$ vector $I_n=(1,1,\dots,1)$ de la dimensión de $n$ es en la imagen de $A$. Este es el caso si y sólo si $I_n$ es ortogonal al kernel $\ker(A)$$A$.

Si esta condición se mantiene, el vector $I_n$ puede escribir en forma exclusiva como $$I_n=\sum_{\lambda\in{\mathrm Spec}(A)\setminus\{0\}}v_\lambda$$ donde la suma es sobre todos distintos de cero autovalores de a $A$ con $v_\lambda$ que denota la proyección ortogonal de a $I_n$ en el espacio propio de valor propio $\lambda$. El gráfico de $\Gamma$ es ahora ponderado-regular si y sólo si el subespacio afín $\sum_{\lambda}\frac{1}{\lambda}v_\lambda+\ker(A)$ (correspondiente al conjunto de preimages de $I_n$) cruza el abierto de cono $({\mathbb R}_{>0})^n$ de los vectores que tengan sólo estrictamente positivo coordenadas. Esta última condición se puede comprobar mediante la programación lineal por la optimización del lineal arbitraria funcional (por ejemplo. la coordenada suma) en $\ker(A)$ sujeto a la condición de que todos los coeficientes de la solución es estrictamente mayor que el correspondiente a los coeficientes de $I_n-\sum_{\lambda}\frac{1}{\lambda}v_\lambda$.

En particular, un gráfico de $\Gamma$ con invertible la matriz de adyacencia $A$ es ponderado-regular si y sólo si todas las coordenadas del vector $\sum_\lambda \frac{1}{\lambda}v_\lambda$ son estrictamente positivos y estas coordenadas dar al conjunto único de pesos (arriba a la multiplicación por una constante positiva) de giro $\Gamma$ en peso-gráfico regular.

Esto por supuesto no es nada más que Kristall Cantwell al comentario de concretarse.

Answer 3

Los ejemplos que dio puede ser extendida. Si un grafo tiene un transitiva grupo, entonces es ponderado regular. También si el grafo tal que un punto está conectado a todos los otros puntos y si ese punto se retira el gráfico restante tiene un transitiva grupo, entonces es ponderado regular.

También existe gráficos que no están ponderados regular Fijamos en el gráfico de 5 puntos y buscar en el siguiente gráfico 1 está conectado a todos los otros puntos de $n$ igual a 2 al 4 $n$ está conectado a $n+1$. Entonces la suma de los pesos en 3 y 4 es igual a la suma de los pesos en todos los puntos de la gráfica, más la suma de peso. La suma de los pesos en 2 y de 5 es la suma de los pesos en 3 y 4, además de dos veces el peso de 1. La combinación de estas dos fuerzas, el peso en 2 y de 5 a ser cero y por lo tanto no es positivo por lo que no todos los gráficos son ponderados regular.

También para cualquier gráfico si un punto de $x$ sólo se conecta a un punto de $y$ si $z$ se conecta a punto de $y$ que no se puede conectar a cualquier otro punto t si se hace desde los pesos de $z$ $x$ son de la misma el valor asignado a $y$ debe ser igual a la suma de los valores asignados a $y + t$ y, por tanto, $t$ está obligado a ser cero. Esto significa que el único árbol que puede ser ponderado regular es una estrella y el único bosque uno con cada componente de una estrella y si cualquier grafo tiene un componente con un vértice conectado sólo a un punto que debe ser una estrella.

La combinación de cualquiera de los dos ponderado de regular los gráficos es ponderado regular. Deje que los gráficos se $G$ $H$ $m$ $n$ puntos respectivamente. Vamos allí pesos asignados a cada gráfico, de manera que cada nodo en cada gráfico tiene el mismo de peso. Deje que el peso de cada nodo en $G$ $w_1$ y el peso de cada nodo en $H$$w_2$. Deje que la suma de los pesos de los $G$ $w_3$ y la suma de los los pesos de $H$$w_4$. se multiplican los pesos de $G$$a$$H$$b$. Entonces el peso de cualquier nodo de $G$ en la combinación es $aw_1 + bw_4$, y la de cualquier nodo de H en la combinación es $aw_2 + bw_3$ así que para los que se unan para un ponderado gráfico regular $aw_1 + bw_4 = bw_2 + aw_3$ o $a(w_1-w_3)= b (w_2-w_4)$ o $a/b =(w_1-w_3)/(w_2-w_4)$ puede encontrar $a$ $b$ fib $w_1$ no es igual a $w_3$ $w_2$ no es igual a $w_4$.Pero la suma de los pesos en todos los puntos no es igual a la suma de los pesos en todos los puntos en el gráfico de modo que se satisface la condición.

Ahora con el comentario de Douglas Zare que el casco convexo de las filas de la matriz de adyacencia contiene un múltiplo de la todo-1s vector podemos encontrar si cualquier grafo es ponderado regular en el tiempo polinomio. Podemos convertirlo en un problema de programación lineal y no de algoritmos tales como el elipsoide método para resolver problemas de programación lineal en un polinomio cantidad de tiempo.

En este papel: "cuántica En la perfecta transferencia de estado en ponderados unirse gráfico", disponible en la URL: http://arxiv.org/abs/0909.0431 el concepto de un promedio ponderado de regular el gráfico se aplica perfecto estado transferencia cuántica en la redes.