Емкость Шеннона графа

В теории графов пропускная способность Шеннона графа — это инвариант графа , определяемый числом независимых множеств сильных графовых произведений . Он назван в честь американского математика Клода Шеннона . Он измеряет пропускную способность Шеннона канала связи , определяемого из графа, и ограничен сверху числом Ловаса , которое может быть вычислено за полиномиальное время . Однако вычислительная сложность самой пропускной способности Шеннона остается неизвестной.

Графовые модели каналов связи

Пропускная способность Шеннона моделирует объем информации, который может быть передан по шумному каналу связи, в котором определенные значения сигнала могут быть спутаны друг с другом. В этом приложении граф путаницы ^[1] или граф путаницы описывает пары значений, которые могут быть спутаны. Например, предположим, что канал связи имеет пять дискретных значений сигнала, любое из которых может быть передано за один временной шаг. Эти значения могут быть математически смоделированы как пять чисел 0, 1, 2, 3 или 4 в модульной арифметике по модулю 5. Однако предположим, что когда значение отправляется по каналу, полученное значение равно (mod 5), где представляет шум на канале и может быть любым действительным числом в открытом интервале от −1 до 1. Таким образом, если получатель получает значение, например, 3,6, невозможно определить, было ли оно изначально передано как 3 или как 4; два значения 3 и 4 можно спутать друг с другом. Эту ситуацию можно смоделировать с помощью графа — цикла длиной 5, в котором вершины соответствуют пяти значениям, которые могут быть переданы, а ребра графа представляют значения, которые можно спутать друг с другом. $я$ $i+\xi$ $\xi$ $C_{5}$

Для этого примера можно выбрать два значения, которые могут быть переданы на каждом временном шаге без двусмысленности, например, значения 1 и 3. Эти значения достаточно далеки друг от друга, чтобы их нельзя было спутать друг с другом: когда получатель получает значение от 0 до 2, он может сделать вывод, что отправленное значение должно быть 1, а когда получатель получает значение от 2 до 4, он может сделать вывод, что отправленное значение должно быть 3. Таким образом, на этапах коммуникации отправитель может передавать до двух разных сообщений. Два — это максимальное количество значений, которые получатель может отличить друг от друга: каждое подмножество из трех или более значений 0, 1, 2, 3, 4 включает по крайней мере одну пару, которые можно спутать друг с другом. Несмотря на то, что канал имеет пять значений, которые могут быть отправлены на временной шаг, фактически только два из них можно использовать с этой схемой кодирования. $x$ $x$ $n$ $2^{n}$

Однако более сложные схемы кодирования позволяют передавать большее количество информации по одному и тому же каналу, используя кодовые слова длиной больше единицы. Например, предположим, что на двух последовательных этапах отправитель передает одно из пяти кодовых слов «11», «23», «35», «54» или «42». (Здесь кавычки указывают, что эти слова следует интерпретировать как строки символов, а не как десятичные числа.) Каждая пара этих кодовых слов включает по крайней мере одну позицию, где ее значения отличаются на два или более по модулю 5; например, «11» и «23» отличаются на два во второй позиции, в то время как «23» и «42» отличаются на два в первой позиции. Поэтому получатель одного из этих кодовых слов всегда сможет однозначно определить, какое из них было отправлено: никакие два из этих кодовых слов нельзя спутать друг с другом. Используя этот метод, на этапах коммуникации отправитель может передавать до сообщений, что значительно больше, чем можно было бы передать с помощью более простого однозначного кода. Эффективное число значений, которые могут быть переданы за единицу времени, равно . В терминах теории графов это означает, что пропускная способность Шеннона 5-цикла составляет по крайней мере . Как показал Ловас (1979), эта граница узкая: невозможно найти более сложную систему кодовых слов, которая позволяла бы отправлять еще больше различных сообщений за то же время, поэтому пропускная способность Шеннона 5-цикла составляет ровно . $n$ $5^{n/2}$ $2^{n}$ ${\textstyle (5^{n/2})^{1/n}={\sqrt {5}}}$ ${\sqrt {5}}$ ${\sqrt {5}}$

Отношение к независимым множествам

Если граф представляет собой набор символов и пар символов, которые можно спутать друг с другом, то подмножество символов избегает всех спутываемых пар тогда и только тогда, когда является независимым набором в графе, подмножеством вершин, которое не включает обе конечные точки какого-либо ребра. Максимально возможный размер подмножества символов, которые можно отличить друг от друга, — это число независимости графа, размер его максимального независимого набора . Например, ' : 5-цикл имеет независимые наборы из двух вершин, но не больше. $G$ $S$ $S$ $\альфа (G)$ $\альфа (C_{5})=2$

Для кодовых слов большей длины можно использовать независимые наборы в больших графах для описания наборов кодовых слов, которые могут быть переданы без путаницы. Например, для того же примера из пяти символов, граф путаницы которых равен , существует 25 строк длины два, которые могут быть использованы в схеме кодирования длины 2. Эти строки могут быть представлены вершинами графа с 25 вершинами. В этом графе каждая вершина имеет восемь соседей, восемь строк, с которыми ее можно спутать. Подмножество строк длины два образует код без возможной путаницы тогда и только тогда, когда оно соответствует независимому набору этого графа. Набор кодовых слов {"11", "23", "35", "54", "42"} образует один из этих независимых наборов максимального размера. $C_{5}$

Если — граф, представляющий сигналы и спутываемые пары канала, то граф, представляющий кодовые слова длины два и их спутываемые пары, — это , где символ представляет сильное произведение графов . Это граф, имеющий вершину для каждой пары вершины в первом аргументе произведения и вершину во втором аргументе произведения. Две различные пары и являются смежными в сильном произведении тогда и только тогда, когда и идентичны или смежны, а и идентичны или смежны. В более общем смысле кодовые слова длины могут быть представлены графом , -кратным сильным произведением с самим собой, а максимальное количество кодовых слов этой длины, которое может быть передано без путаницы, задается числом независимости . Эффективное количество сигналов, переданных за единицу времени, является корнем th степени этого числа, . $G$ $G\boxtimes G$ $\boxtimes$ $(u,v)$ $(u_{1},v_{1})$ $(u_{2},v_{2})$ $u_{1}$ $u_{2}$ $v_{1}$ $v_{2}$ $к$ $G_{k}$ $к$ $G$ $\альфа (G_{k})$ $к$ $\альфа (G_{k})^{1/k}$

Используя эти концепции, емкость Шеннона можно определить как

\Theta (G)=\sup _{k}{\sqrt[{k}]{\alpha (G_{k})}}=\lim _{k\rightarrow \infty }{\sqrt[{k}]{\alpha (G_{k})}},

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

Сложность вычислений

Нерешенная задача по математике :

Какова емкость Шеннона для 7-тактного двигателя?

(еще нерешенные проблемы по математике)

Вычислительная сложность емкости Шеннона неизвестна, и даже значение емкости Шеннона для некоторых небольших графов, таких как ( граф-цикл из семи вершин), остается неизвестным. ^[2]^[3] $C_{7}$

Естественным подходом к этой проблеме было бы вычислить конечное число степеней данного графа , найти их числа независимости и вывести из этих чисел некоторую информацию о предельном поведении последовательности, из которой определяется емкость Шеннона. Однако (даже игнорируя вычислительную сложность вычисления чисел независимости этих графов, NP-трудную задачу) непредсказуемое поведение последовательности чисел независимости степеней подразумевает, что этот подход не может быть использован для точного приближения емкости Шеннона. ^[4] $G$ $G$

Верхние границы

Отчасти потому, что емкость Шеннона трудно вычислить, исследователи искали другие инварианты графа, которые легко вычислить и которые обеспечивают границы емкости Шеннона.

Число Ловаса

Число Ловаса ϑ( G ) — это другой инвариант графа, который может быть вычислен численно с высокой точностью за полиномиальное время с помощью алгоритма, основанного на методе эллипсоидов . Емкость Шеннона графа G ограничена снизу α( G ), а сверху ϑ( G ). ^[5] В некоторых случаях ϑ( G ) и емкость Шеннона совпадают; например, для графа пятиугольника оба равны √ 5 . Однако существуют другие графы, для которых емкость Шеннона и число Ловаса различаются. ^[6]

Связанный Хеймерс

Хемерс предоставил еще одну верхнюю границу пропускной способности Шеннона, которая иногда лучше границы Ловаса: ^[7]

\Theta (G)\leq R(G)=\min _{B}\operatorname {rank} (B),

где B — матрица размера n × n над некоторым полем , такая, что b _ii ≠ 0 и b _ij = 0, если вершины i и j не являются смежными.

Ссылки

^ Эриксон, Мартин Дж. (2014). Введение в комбинаторику . Дискретная математика и оптимизация. Т. 78 (2-е изд.). John Wiley & Sons. стр. 134. ISBN 978-1118640210.
↑ Regan, Kenneth W. (10 июля 2013 г.), «Сложные проблемы», Потерянное письмо Гёделя и P=NP.
^ tchow (19 февраля 2009 г.), "Шенноновская емкость семицикла", Open Problem Garden.
^ Алон, Нога ; Любецки, Эял (2006), «Ёмкость Шеннона графа и числа независимости его степеней», IEEE Transactions on Information Theory , 52 (5): 2172–2176, arXiv : cs/0608021 , doi : 10.1109/tit.2006.872856, S2CID 889.
^ Ловас, Ласло (1979), «О емкости графа по Шеннону», IEEE Transactions on Information Theory , IT-25 (1): 1–7, doi : 10.1109/TIT.1979.1055985, Zbl 0395.94021.
^ Хемерс, Виллем Х. (1979), «О некоторых проблемах Ловаса относительно емкости Шеннона графа», IEEE Transactions on Information Theory , 25 (2): 231–232, doi :10.1109/tit.1979.1056027, Zbl 0402.94029.
^ Хамерс, Виллем Х. (1978), «Верхняя оценка емкости графа по Шеннону» (PDF) , Colloquia Mathematica Societatis János Bolyai , 25 : 267–272. Приведенное здесь определение исправляет опечатку в данной статье.