Necesito construir un gráfico expansor d-regular para algunos pequeños d fijos (como 3 o 4) de n vértices.
¿Cuál es el método más fácil para hacer esto en la práctica? ¿Construir un gráfico d-regular aleatorio, que se ha demostrado que es un expansor?
También leí sobre las construcciones de Margulis y los gráficos de Ramanujan que son expansores y una construcción que usa un producto en zig-zag. Wikipedia ofrece una descripción general agradable pero muy breve: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 ¿ Pero qué método elijo en la práctica?
Para mí, estos métodos parecen muy complicados de implementar y, en particular, de comprender y quizás bastante específicos. ¿No existen métodos más fáciles, tal vez basados en permutaciones o algo así, para generar prácticamente una secuencia de gráficos de expansores d-regulares?
¿Es quizás más fácil construir gráficos expansores bipartitos d-regulares?
También tengo otra pregunta: ¿qué pasa con las familias de expansores d-regulares malos? ¿Tiene sentido tal noción? ¿Se puede construir una familia de gráficos d-regulares (que por supuesto estén conectados) que sea tan mala como sea posible en el sentido de un expansor?
Gracias por adelantado.
fuente
Respuestas:
Si no le importan los gráficos con bucles automáticos, la familia de expansores "más fáciles" es probablemente esta, que proporciona expansores que son 3-regulares.
Comience con algún número primo , y construya vértices numerados de 0 a p - 1 . Para cada vértice u ≠ 0 , conecte T a T - 1 y T + 1 , módulo p . También conecte u al vértice único v de modo que u v ≡ 1pag 0 0 p - 1 u ≠ 0 tu u - 1 u + 1 pag tu v .u v ≡ 1modificaciónpag
Como ejemplo, el gráfico de 7 vértices en la familia es un ciclo de 7 con vértices numerados secuencialmente alrededor del ciclo; hay self-loops en , 0 y 1 ; finalmente, hay acordes que unen 3 y 5 , y 2 y 46 6 0 0 1 3 5 5 2 4 4 .
Ver /mathpro/124708/an-expander-graph para más discusión y referencias. Hay muchos punteros más detallados buscando "expansor" en CSTheory , Math.SE y MO .
Como señala Yuval Filmus, es probable que la construcción aleatoria dé mejores resultados en general, pero, por supuesto, puede que no produzca un expansor (especialmente para gráficos pequeños).
fuente
Dado que un gráfico regular aleatorio es un expansor whp (siga la referencia dada en la documentación del código MATLAB vinculado a continuación), una vez usé lo siguiente:
http://www.mathworks.com/matlabcentral/fileexchange/29786-random-regular-generator/content/randRegGraph/createRandRegGraph.m
fuente