Шенноновская емкость графа
В теории графов шенноновская емкость графа представляет собой инвариант графа, определяемый числом независимых наборов сильных графовых произведений . Он назван в честь американского математика Клода Шеннона . Он измеряет пропускную способность Шеннона канала связи , определенного на графике, и ограничен сверху числом Ловаса , которое можно вычислить за полиномиальное время . Однако вычислительная сложность самой емкости Шеннона остается неизвестной.
Графовые модели каналов связи
[ редактировать ]Пропускная способность Шеннона моделирует объем информации, который может быть передан по зашумленному каналу связи, в котором определенные значения сигналов можно спутать друг с другом. В этом приложении граф путаницы [1] или график путаницы описывает пары значений, которые можно спутать. Например, предположим, что канал связи имеет пять дискретных значений сигнала, любое из которых может быть передано за один временной шаг. Эти значения можно математически смоделировать как пять чисел 0, 1, 2, 3 или 4 в модульной арифметике по модулю 5. Однако предположим, что когда значение передается по каналу, полученное значение равно (мод 5) где представляет шум в канале и может быть любым действительным числом в открытом интервале от -1 до 1. Таким образом, если получатель получает значение, например 3,6, невозможно определить, было ли оно первоначально передано как 3 или как 4; два значения 3 и 4 можно спутать друг с другом. Эту ситуацию можно смоделировать графом, циклом длины 5, в котором вершины соответствуют пяти значениям, которые могут быть переданы, а ребра графа представляют значения, которые можно спутать друг с другом.
В этом примере можно выбрать два значения, которые могут передаваться на каждом временном шаге без двусмысленности, например, значения 1 и 3. Эти значения находятся достаточно далеко друг от друга, чтобы их нельзя было спутать друг с другом: когда получатель получает значение между 0 и 2, можно сделать вывод, что отправленное значение должно быть равно 1, и когда получатель получает значение между 2 и 4, можно сделать вывод, что отправленное значение должно было быть 3. Таким образом, в шагов связи, отправитель может общаться до разные сообщения. Два — это максимальное количество значений, которые получатель может отличить друг от друга: каждое подмножество из трех или более значений 0, 1, 2, 3, 4 включает в себя хотя бы одну пару, которую можно спутать друг с другом. Несмотря на то, что канал имеет пять значений, которые могут быть отправлены за один временной шаг, эффективно с этой схемой кодирования можно использовать только два из них.
Однако более сложные схемы кодирования позволяют отправлять больший объем информации по одному и тому же каналу за счет использования кодовых слов длиной больше единицы. Например, предположим, что за два последовательных шага отправитель передает одно из пяти кодовых слов «11», «23», «35», «54» или «42». (Здесь кавычки указывают, что эти слова следует интерпретировать как строки символов, а не как десятичные числа.) Каждая пара этих кодовых слов включает по крайней мере одну позицию, в которой ее значения отличаются на два или более по модулю 5; например, «11» и «23» различаются на два во второй позиции, а «23» и «42» отличаются на два в первой позиции. Поэтому получатель одного из этих кодовых слов всегда сможет однозначно определить, какое из них было отправлено: никакие два этих кодовых слова нельзя спутать друг с другом. Используя этот метод, в шагов связи, отправитель может общаться до сообщений значительно больше, чем который можно было бы передать с помощью более простого однозначного кода. Эффективное количество значений, которые могут быть переданы за единицу времени, равно .В терминах теории графов это означает, что пропускная способность Шеннона 5-цикла не менее . Как показал Ловас (1979) , эта граница точна: невозможно найти более сложную систему кодовых слов, которая позволяла бы отправлять еще больше разных сообщений за один и тот же промежуток времени, поэтому пропускная способность Шеннона 5-цикла это точно .
Отношение к независимым множествам
[ редактировать ]Если график представляет собой набор символов и пары символов, которые можно спутать друг с другом, а затем подмножество символов позволяет избежать всех путаемых пар тогда и только тогда, когда — независимое множество в графе, подмножество вершин, не включающее обе конечные точки ни одного ребра. Максимально возможный размер подмножества символов, которые можно отличить друг от друга, представляет собой число независимости. графа, размер его максимального независимого множества . Например, ' : 5-цикл имеет независимые множества из двух вершин, но не большего размера.
Для кодовых слов большей длины можно использовать независимые наборы в больших графах для описания наборов кодовых слов, которые можно передавать без путаницы. Например, для того же примера пяти символов, график путаницы которых равен , существует 25 строк длины два, которые можно использовать в схеме кодирования длины 2. Эти строки могут быть представлены вершинами графа с 25 вершинами. В этом графе каждая вершина имеет восемь соседей — восемь строк, с которыми ее можно спутать. Подмножество строк длины два образует код без возможной путаницы тогда и только тогда, когда оно соответствует независимому набору этого графа. Набор кодовых слов {"11", "23", "35", "54", "42"} образует один из этих независимых наборов максимального размера.
Если представляет собой граф, представляющий сигналы и смешиваемые пары канала, тогда граф, представляющий кодовые слова длины два и их смешиваемые пары, имеет вид , где символ представляет собой сильное произведение графов . Это граф, в котором для каждой пары есть вершина. вершины в первом аргументе произведения и вершины во втором аргументе произведения. Две разные пары и смежны в сильном произведении тогда и только тогда, когда и идентичны или соседствуют, и и идентичны или соседствуют. В более общем смысле, кодовые слова длины можно представить графиком , -кратное сильное произведение сам с собой, а максимальное количество кодовых слов этой длины, которые могут быть переданы без путаницы, определяется числом независимости . Эффективное количество сигналов, передаваемых за единицу времени, равно корень из этого числа, .
Используя эти концепции, емкость Шеннона можно определить как
предел (как становится сколь угодно большим) эффективного числа сигналов на временной шаг произвольно длинных кодов без путаницы.
Вычислительная сложность
[ редактировать ]Вычислительная сложность емкости Шеннона неизвестна, и даже значение емкости Шеннона для некоторых небольших графов, таких как ( граф-цикл из семи вершин) остается неизвестным. [2] [3]
Естественным подходом к этой проблеме было бы вычисление конечного числа степеней данного графа. , найдите их числа независимости и выведите из этих чисел некоторую информацию о предельном поведении последовательности, из которой определяется пропускная способность Шеннона. Однако (даже если не учитывать вычислительную сложность вычисления чисел независимости этих графов, что является NP-трудной проблемой) непредсказуемое поведение последовательности чисел независимости степеней подразумевает, что этот подход не может быть использован для точной аппроксимации емкости Шеннона. [4]
Верхние границы
[ редактировать ]Отчасти потому, что емкость Шеннона трудно вычислить, исследователи искали другие инварианты графа, которые легко вычислить и которые дают границы емкости Шеннона.
Номер Ловаша
[ редактировать ]Число Ловаса ϑ( G ) — это другой инвариант графа, который можно вычислить численно с высокой точностью за полиномиальное время с помощью алгоритма, основанного на методе эллипсоидов . Шенноновская емкость графа G ограничена снизу α( G ), а сверху ϑ( G ). [5] В некоторых случаях ϑ( G ) и емкость Шеннона совпадают; например, для графика пятиугольника оба равны √ 5 . Однако существуют и другие графы, для которых емкость Шеннона и число Ловаса различаются. [6]
Граница Хемерса
[ редактировать ]Хемерс предоставил еще одну верхнюю оценку емкости Шеннона, которая иногда лучше, чем граница Ловаса: [7]
где B — матрица размера n × n над некоторым полем , такая что b ii ≠ 0 и b ij = 0, если вершины i и j не смежны.
Ссылки
[ редактировать ]- ^ Эриксон, Мартин Дж. (2014). Введение в комбинаторику . Дискретная математика и оптимизация. Том. 78 (2-е изд.). Джон Уайли и сыновья. п. 134. ИСБН 978-1118640210 .
- ^ Риган, Кеннет В. (10 июля 2013 г.), «Грубые проблемы» , «Потерянное письмо Гёделя» и P=NP .
- ^ Чоу (19 февраля 2009 г.), «Шенноновская мощность семицикла» , Открытый сад проблем .
- ^ Алон, Нога ; Любецкий, Эял (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 . Определение здесь исправляет опечатку в этой статье.