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

1 Ноябрь 2013, 21:36

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

В начале 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.

Теги: задача, линейная алгебра, приложения, теория графов
Рубрика: Статьи по математике | Отзывы (RSS) | Трекбек

Математика, которая мне нравится

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

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

Навигация по сайту

Разделы

Новые комментарии

Хороший книжный магазин

Подписка на обновления сайта

Твиттер