Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
§ 4. л-сети
Важным подклассом двухполюсных сетей из двух объектных наборов является класс л-сетей.
Определение. Сеть, являющаяся суперпозицией сетей Г?(а,Ь) и Г* (а, ?), называется п-сетъю.
Данное определение эквивалентно другому: двухполюсная сеть из двухобъектных наборов, которая сильно связна, будет л-сетью, если каноническое расщепление содержит сети двух типов Г/Да, Ь) и Г?(а, Ь).
Пример 9. Сеть Г (а, ?>), изображенная на рис. 31, будет л-сетью.
Каждой л-сетп можно поставить в соответствие множество укладок дерева, неконцевым вершинам которых сопоставлены символы р и я. Возможны два случая:
1) Г (а, Ъ) = Г?(а, 6), где а=р или о=в. Сети Г?(а, Ь) ставим в соответствие пучок из к (И ^ 2) ребер*), корень которого помечен символом о {рис. 32).
2) Г (а, Ь) расщепляется на сеть Г?(а, Ь) и сети Г1{а(1,| Ь(1)), ГА(а('1), Ь1Н)) (с — р или о = з). Выпуска-,
ем из корня, помеченного символом о, к (к** 2) ребер*),
а
Рис. 31
Рис. 32
•) Порядок ребер в пучке при о = р произволен, при О — Я
соответствует порядку ребер в сети Г^(а, Ъ).
Ч. Ш. ІҐАЧЛЬІ 11 ЬЫИ
которые соответствуют внутренним сетям (рис. 32). Далее, концам ребер, которым соответствуют нетривиальные сети, приписываем символ, отличный от о (его обозначим через о*)). После этого для каждой нетривиальной сети
Гі(л(1\ Ь(0) применяют либо п. 1, либо п. 2 и строят пучки в вершинах о и т. д. (рис. 33). В построенной укладке дерева каждый пучок ребер содержит не мепее двух ребер. Таким образом, каждой я-сети соответствует множество укладок дерева. Неизоморфным я-сетпм соответствуют непересекающиеся множества укладок. Значит число я-се-тей не превосходит числа укладок деревьев.
Рассмотрим укладку дерева для я-сети из примера 9 (рис. 34). Легко видеть, что укладка дерева, соответствующая я-сети с к ребрами, имеет к концевых вершин.
Итак, изучение я-сетей может быть сведено к изучению укладок деревьев специального вида. Покажем, что эта связь позволяет переносить некоторые факты, известные для деревьев, на я-сети.
Теорема '5. Пусть а {к)—максималыюе число попарно неизоморфных я-сетей с Н ребрами. Тогда я(/г)^ < 42\
Доказательство. Очевидно, что искомое число не превосходит числа укладок выше указанного типа деревьев с к концевыми вершинами, у которых каждый пучок исходящих ребер содержит не менее двух ребер. Обозначим через I число ребер в дереве из этого класса. По индукции докажем, что К2к — 2 при к > 2.
Базис индукции. Если я-сеть содержит два ребра: к => 2, то очевидно, что соответствующее1 дерево содержит
*) Где 0 = 5, если С = Р И 0 = Р, если 0 = 5.
\Р
Рис. 34
Рис. 33
две концевые вершины, т. е. 1 — 2 и неравенство выполнено.
Индуктивный переход. Пусть неравенство верно для деревьев, соответствующих я-сетям с менее, чем К ребрами. Рассмотрим я-сеть Г (а, 6) с И ребрами и соответствующее ей дерево (рис. 35). Если Г (а, Ь) = = Г”(я, Ь), то 1 = Ь> 2 и неравенство, очевидно, выполнено. Если Г (о, Ь) допускает расщепление, то в дереве число тп исходящих из корня ребер равно числу ребер внешней сети расщепления сети Г (а, Ь) и по условию т> 2. Деревья ?>!, ..., ?>, соответствуют нетривиальным внутренним сетям этого расщепления, t< т. Обозначим через и и (1 = 1, ..?) число ребер и число концевых вершин в Рис. 35
дереве По предположению индукции 2й{ —2 (г = 1, ..О? кроме того, очевидно,
2 и + т = 1у; 2 + (иг — ?) = Н. Мы имеем
1=1 1=1
* I
I = 2 *1 + т<22 4- т =*
1=1 1=1
= 2^2 + (т — г)) “ т ** 2А — т 2Н —? 2,
так как т-^ 2.
Для оценки величины я (А) , заметим, что в каждой укладке дерева из данного класса символы р и в можно расставить двумя способами. Б силу этого, используя оценку для числа укладок деревьев с заданным числом ребер, имеем
я(/г.) < 2 • 42Н~2 < 42\
ТЕОРИЯ КОДИРОВАНИЯ
Вопросы кодирования играют существенную роль в математике. Кодирование позволяет изучение одпих объектов сводить к изучению других. Хорошо известно, какую роль сыграло изображение чисел в десятичной системе счисления. Весьма важным в развитии математики было появление метода координат, который позволил
Рис. і
кодировать геометрические объекты при помощи аналитических выражений. Однако, здесь средства кодирования являлись вспомогательным аппаратом и не были предметом изучения. Совсем другое значение получили коды в связи с изучением управляющих систем. Появилась необходимость систематического исследования в области теории кодирования. Основной круг задач может быть прослежен на примере из области связи, который характеризуется схемой, представленной на рис. 1.
Пусть задан алфавит лг}, состоящий из
конечного числа букв. Конечную последовательность символов из %
будем называть словом в алфавите 9(, а число п — длиной слова А. Длину слова А будем обозначать через 1{А).
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
257
Пусть 5~&(2[) —множество всех непустых слов в алфавите ?Г, и ?' — некоторое подмножество мпожества ?. Объект, порождающий слова из называется источником сообщений, а слова из *5" — сообщениями. Источником сообщений может быть автомат, человек и т. п. Обычно при рассмотрении задач теории кодирования используется дополнительная информация об источнике сообщений в виде некоторого его описания. Существует ряд способов описаний источников сообщений:
