Теория графов и коммуникация

Джон Робинсон Пирс

В начале 70-х годов прошлого века Джон Пирс предложил коммуникационную сеть, состоящую из соединенных между сосбой в различных точках направленных циклов. Чтобы сообщение попало из исходной точки одного цикла в точку назначения на другом цикле, необходимо было понять, в каких точках нужно переходить на следующие циклы.

Рональд Грэм и Генри Поллак предложили считать каждый цикл вершиной графа, которую отмечали последовательностью символов из алфавита

    \[\{0,1,*\}\]

таким образом, чтобы расстояние Хэмминга между строками соответствовало расстояниям в графе. Тогда переходить на другой цикл следовало, когда адрес нового цикла имел меньшее расстояние Хэмминга до точки назначения.

Расстояние между строками символов трехэлементного алфавита

    \[\{0,1,*\}\]

определялось следующим образом. Расстояние

    \[d(x,y)\]

между двумя символами

    \[x\]

и

    \[y\]

равно

    \[d(x,y)=\left\{\begin{array}{ll} 1,&if\ \{ x,y\}=\{0,1\},\\ 0,&if\ x=*\vee y=*. \end{array}\right.\]

Рональд Льюис Грэм

Генри Отто Поллак

Далее это определение распространяется на строки длины

    \[m\]

    \[x=(x_1,x_2,\ldots,x_m)\]

и

    \[y=(y_1,y_2,\ldots,y_m)\]

следующим образом:

    \[\displaystyle d(x,y)=\sum_{i=1}^m d(x_i,y_i).\]

В целях более эффективной работы желательно было сделать строки-адреса как можно более короткими. Грэм и Поллак предположили, что длины строк

    \[m=n-1\]

, где

    \[n\]

— число вершин графа, всегда достаточно. Это предположение было доказано П. Уинклером десять лет спустя.

Грэм и Поллак свели данную задачу к задаче о наименьшем числе полных двудольных графов, на которые можно разбить полный граф с

    \[n\]

вершинами. (Разбиение происходит так, чтобы раные двудольные графы не имели общих ребер).

Теорема (Грэм, Поллак, 1972 г.). Если множество ребер полного графа с

    \[n\]

вершинами есть объединение непересекающихся множеств ребер

    \[m\]

полных двудольных графов, то

    \[m\ge n-1\]

.

Доказательство. Предположим, что полный граф с набором вершин

    \[\{1,2,\ldots,n\}\]

разбит на полные двудольные графы

    \[B_1,B_2,\ldots,B_m\]

. Обозначим через

    \[(X_k,Y_k)\]

— две части множества вершин графа

    \[B_k\]

. Заметим, что множества

    \[X_k\]

и

    \[Y_k\]

не имеют общих элементов.

Свяжем с каждым графом

    \[B_k\]

матрицу

    \[A_k\]

размерности

    \[n\times n\]

следующим образом. Элемент матрицы, стоящий в

    \[i\]

-й строке и

    \[j\]

-м столбце положим равным

    \[1\]

, если

    \[i\in X_k,j\in Y_k\]

, и

    \[0\]

в противном случае.

Ясно, что каждая такая матрица

    \[A_k\]

имеет ранг

    \[1\]

. Пусть

    \[\displaystyle S=\sum_{k=1}^mA_k\]

. Для всех

    \[i\ne j\]

в точности один из элементов

    \[(i,j)\]

или

    \[(j,i)\]

отличен от нуля в

    \[S\]

. Следовательно,

    \[S+S^T=J_n-E_n\]

, где

    \[J_n\]

— матрица

    \[n\times n\]

, все элементы которой равны

    \[1\]

, а

    \[E_n\]

— единичная матрица.

Докажем, что если матрица

    \[S\]

удовлетворяет данному уравнению, то ее

    \[{\rm rank}\,S\ge n-1\]

. Отсюда сразу же следует неравенство

    \[m\ge n-1\]

, поскольку для ранга матриц справедливо неравенство

    \[{\rm rank}\,(A+B)\le {\rm rank}\,A+{\rm rank}\, B\]

.

Предположим, что

    \[{\rm rank}\,S \le n-2\]

. В этом случае существует ненулевой вектор

    \[x^T=(x_1,x_2,\ldots,x_n)\in\mathbb{R}^n\]

, удовлетворяющий системе линейных уравнений

    \[\displaystyle Sx=0,\sum_{i=1}^nx_i=0.\]

Для этого вектора имеем

    \[Jx=0\]

и, следовательно,

    \[S^Tx=-x\]

. Тем самым

    \[-||x||^2=x^TSx=x^TSx=0\]

. Получили противоречие, которое и доказывает теорему.

Источник: László Babai, Péter Frankl, Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science, Preliminary Version 2 (September 1992), The University of Chicago.

Оставьте свой отзыв

Добавить изображение