Теория графов и коммуникация
В начале 70-х годов прошлого века Джон Пирс предложил коммуникационную сеть, состоящую из соединенных между сосбой в различных точках направленных циклов. Чтобы сообщение попало из исходной точки одного цикла в точку назначения на другом цикле, необходимо было понять, в каких точках нужно переходить на следующие циклы.
Рональд Грэм и Генри Поллак предложили считать каждый цикл вершиной графа, которую отмечали последовательностью символов из алфавита таким образом, чтобы расстояние Хэмминга между строками соответствовало расстояниям в графе. Тогда переходить на другой цикл следовало, когда адрес нового цикла имел меньшее расстояние Хэмминга до точки назначения.
Расстояние между строками символов трехэлементного алфавита определялось следующим образом. Расстояние
между двумя символами
и
равно
Далее это определение распространяется на строки длины
и
следующим образом:
В целях более эффективной работы желательно было сделать строки-адреса как можно более короткими. Грэм и Поллак предположили, что длины строк , где
— число вершин графа, всегда достаточно. Это предположение было доказано П. Уинклером десять лет спустя.
Грэм и Поллак свели данную задачу к задаче о наименьшем числе полных двудольных графов, на которые можно разбить полный граф с вершинами. (Разбиение происходит так, чтобы равные двудольные графы не имели общих ребер).
Теорема (Грэм, Поллак, 1972 г.). Если множество ребер полного графа с вершинами есть объединение непересекающихся множеств ребер
полных двудольных графов, то
.
Доказательство. Предположим, что полный граф с набором вершин разбит на полные двудольные графы
. Обозначим через
— две части множества вершин графа
. Заметим, что множества
и
не имеют общих элементов.
Свяжем с каждым графом матрицу
размерности
следующим образом. Элемент матрицы, стоящий в
-й строке и
-м столбце положим равным
, если
, и
в противном случае.
Ясно, что каждая такая матрица имеет ранг
. Пусть
. Для всех
в точности один из элементов
или
отличен от нуля в
. Следовательно,
, где
— матрица
, все элементы которой равны
, а
— единичная матрица.
Докажем, что если матрица удовлетворяет данному уравнению, то ее
. Отсюда сразу же следует неравенство
, поскольку для ранга матриц справедливо неравенство
.
Предположим, что . В этом случае существует ненулевой вектор
, удовлетворяющий системе линейных уравнений
Для этого вектора имеем и, следовательно,
. Тем самым
. Получили противоречие, которое и доказывает теорему.
Источник: 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.
Оставьте свой отзыв