Граф расположений

Граф перестановок

В теории графов граф перестановок $A_{n,k}$ — это граф, определённый на множестве вершин, состоящем из всех перестановок $k$ различных элементов, выбранных из множества $\{1,2,\dots ,n\}$, где две вершины соединены ребром, если соответствующие им перестановки отличаются ровно в одной из своих $k$ позиций.

Свойства

Граф перестановок $(n,k)$ имеет $n!/(n-k)!$ вершин, является регулярным графом со степенью $k(n-k)$ и обладает $k(n-k)$-вершинной связностью. Его диаметр равен $\lfloor 3k/2\rfloor$, а среднее расстояние составляет $H_k+k(k-2)/n$, где $H_k=\sum _{i=1}^k\frac{1}{i}$ — $k$-е гармоническое число. Граф перестановок является одновременно вершинно-транзитивным и рёберно-транзитивным.

Граф перестановок $(n,k)$ может быть разложен на $n$ подграфов, изоморфных $A_{n-1,k-1}$, путём фиксации каждого различного элемента в одной определённой позиции.

Частные случаи

При $k=n-1$ получается звёздный граф, а при $k=n-2$ — граф знакопеременной группы. Граф перестановок $A_{n,2}$ является рёберным графом графа-короны.

Применения

Графы перестановок были предложены как обобщение звёздных графов для обеспечения более гибкого выбора параметров сети при проектировании соединений для многопроцессорных или мультикомпьютерных систем. Они сохраняют многие привлекательные свойства звёздных графов, включая вершинную и рёберную транзитивность, при этом позволяя настраивать оба параметра $n$ и $k$ для подходящего размера сети.