Gráfico de disposición

En teoría de grafos , el grafo de disposición${\displaystyle A_{n,k}}$es un grafo definido en el conjunto de vértices que consta de todas las permutaciones de${\displaystyle k}$elementos distintos elegidos de${\displaystyle \{1,2,\ldots ,n\}}$donde dos vértices están conectados por una arista siempre que sus permutaciones correspondientes difieran en exactamente uno de sus${\displaystyle k}$posiciones. ^{[ 1 ] [ 2 ]}

El${\displaystyle (n,k)}$-el gráfico de disposición tiene${\displaystyle n!/(nk)!}$vértices, es regular con grado de vértice${\displaystyle k(nk)}$y es${\displaystyle k(nk)}$- conectado . Tiene diámetro de gráfico${\displaystyle \lfloor 3k/2\rfloor }$y distancia promedio${\displaystyle H_{k}+k(k-2)/n}$, dónde${\displaystyle H_{k}=\sum _{i=1}^{k}{\frac {1}{i}}}$es el${\displaystyle k}$número armónico . El grafo de disposición es transitivo en vértices y transitivo en aristas . ^{[ 1 ] [ 2 ]}

El${\displaystyle (n,k)}$-El grafo de disposición se puede descomponer en${\displaystyle n}$subgrafos isomorfos a${\displaystyle A_{n-1,k-1}}$fijando cada elemento diferente en una posición particular. ^{[ 2 ]}

Los valores propios de la matriz de adyacencia de un grafo de arreglo son enteros. Para valores fijos${\displaystyle k}$y suficientemente grande${\displaystyle n}$,${\displaystyle -k}$es el único valor propio negativo en el espectro. ^{[ 3 ]}

Configuración${\displaystyle k=1}$produce el gráfico completo${\displaystyle K_{n}}$, configuración${\displaystyle k=n-1}$produce el gráfico de estrellas y la configuración${\displaystyle k=n-2}$produce el grafo de grupo alternante . ^{[ 2 ] [ 4 ]} El grafo de disposición${\displaystyle A_{n,2}}$es el gráfico de líneas de la${\displaystyle n}$-gráfico de corona .

Los grafos de disposición se propusieron como una generalización de los grafos estrella para proporcionar una elección más flexible de parámetros de red al diseñar una red de interconexión para sistemas multiprocesador o multicomputadora . ^{[ 2 ]} Conservan muchas propiedades atractivas de los grafos estrella, incluyendo la transitividad de vértices y aristas, al tiempo que permiten el ajuste de ambos parámetros.${\displaystyle n}$y${\displaystyle k}$para un tamaño de red adecuado. ^{[ 1 ]}