Распечатать запись Распечатать запись

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

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

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

Рональд Грэм и Генри Поллак предложили считать каждый цикл вершиной графа, которую отмечали последовательностью символов из алфавита \{0,1,*\} таким образом, чтобы расстояние Хэмминга между строками соответствовало расстояниям в графе. Тогда переходить на другой цикл следовало, когда адрес нового цикла имел меньшее расстояние Хэмминга до точки назначения.

Расстояние между строками символов трехэлементного алфавита \{0,1,*\} определялось следующим образом. Расстояние d(x,y) между двумя символами x и y равно

d(x,y)=\left\{\begin{array}{ll}<br />
1,&if\ \{ x,y\}=\{0,1\},\\<br />
0,&if\ x=*\vee y=*.<br />
\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.

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

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