Граф Серпинского

Графы Серпинского

Графы Серпинского (или сети Серпинского) — это семейство графов, определяемое в теории графов двумя параметрами $n$ и $k$ и обозначаемое $S (n, k)$ . Эти графы находят применение в топологии, задаче о Ханойских башнях и в качестве сетей соединений для архитектур многопроцессорных систем. Графы названы в честь Вацлава Серпинского из-за их связи с треугольником Серпинского.

Определение[править | править код]

Для любых целых чисел $n \geq 1$ и $k \geq 2$ граф Серпинского $S (n, k)$ определяется следующим образом:

**Вершины**: Множество вершин $V (S (n, k))$ состоит из всех $n$ -кортежей $(i_{1}, i_{2}, \dots, i_{n})$ , где каждый $i_{j} \in {1, 2, \dots, k}$ . Таким образом, $| V (S (n, k)) | = k^{n}$ .

**Рёбра**: Две вершины I=(i1,i2,…,in) и J=(j1,j2,…,jn) являются смежными тогда и только тогда, когда существует h∈{1,2,…,n} такое, что:
- $i_{t} = j_{t}$ для всех $t < h$
- $i_{h} \neq j_{h}$
- $i_{t} = j_{h}$ и $j_{t} = i_{h}$ для всех $t > h$

Свойства[править | править код]

Количество вершин в $S (n, k)$ равно $k^{n}$ . Количество рёбер равно $\frac{n k (k - 1)}{2} k^{n - 1}$ .

Диаметр графа $S (n, k)$ равен $2^{n} - 1$ , а хроматическое число равно $k$ .

Они имеют низкую и ограниченную степень, что упрощает расширение и соответствует ограничениям на количество контактов в СБИС.
Их иерархическая структура соответствует шаблонам трафика во многих параллельных приложениях.
Они обеспечивают масштабируемые затраты и производительность для будущих параллельных компьютерных систем и локальных сетей.

Совершенные доминирующие множества[править | править код]

Графы Серпинского $S (n, k)$ обладают по существу единственными совершенными доминирующими множествами для всех параметров $n$ и $k$ , что делает их важными примерами в изучении доминирования в графах. Совершенное доминирующее множество также известно как 1-совершенный код.