Элементы комбинаторики

ГЛАВА 1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

§1.1. Основные комбинаторные конфигурации

 

1.  Среди основных задач комбинаторики выделяют следующие: пересчет, перечисление, классификация и оптимизация. Если требуется определить количество элементов, обладающих некоторым свойством или совокупностью свойств, то это задача пересчета. Если при этом необходимо указать список элементов, то это задача перечисления. Если пересчет приводит  к  слишком большим числам,  то отказываются от соответствующего перечисления и только классифицируют элементы с помощью    какого-нибудь соотношения, - и тогда это задача классификации. В некоторых задачах на множестве решений можно ввести функцию величины и относительно этой функции рассматривать задачу оптимизации:   найти экстремум функции на определенном множестве объектов, либо указать все или некоторые объекты, для которых достигается экстремальное значение.

2.  Комбинаторная конфигурация- это расположение конечного множества элементов, удовлетворяющее ряду специальных свойств. К основным, комбинаторным конфигурациям относятся сочетания, размещения и перестановки. Ряд других конфигураций может быть сведен к ним.

Набор (множество или кортеж) элементов

составленный из элементов множества, называется выборкой объема k из n элементов,или (n,k –выборкой).Выборки, различающиеся составом элементов, всегда считаются различными.

Выборка называется упорядоченной,если порядок элементов в ней задан (т.е. она представляет из себя кортеж). Две упорядоченные выборки, различающиеся только порядком следования элементов, считаются различными. Если порядок элементов в выборке несуществен, то выборка называется неупорядоченной.

Упорядоченная (n,k)-выборка, в которой элементы могут повторяться, называется (n,k)-размещением с повторениями,или размещением с повторениями из n элементов по k.Если элементы (n,k)-выборки попарно различны, то она называется (n, k)- размещением без повторений,или размещением без повторений из n элементов по k.

N,n)-размещения без повторенийназываются n-перестановками,или перестановками из n элементов.

Если элементы в (n, К)-выборке не могут повторяться, то, очевидно, выполнено неравенство k < n. Для выборки с повторениями возможно условие k… 3. В комбинаторике можно выделить два основных правила: правило суммы и… Пусть X - конечное множество из n элементов. Тогда говорят, что один объект из X можно выбрать n способами, и…

Это правило суммы,или правило альтернатив.

Для пересекающихся множеств может выполняться более сложное соотношение    |X U Y| = |X| + |Y| - |X ∩ Y|.   §1.2. Формулы пересчета числа комбинаторных

конфигураций.

2. Числа (n,k) -сочетаний без повторений обозначаются символами  и называются…  

§2.1. Ориентированные и неориентированные графы.

Способы задания графов.

1. Граф  - это система некоторых объектов вместе с некоторыми парами этих объектов, изображающая отношения связи между ними. Неориентированный…   Для неориентированного графа значение V1 и V2 может быть произвольным. Для…  образует множество элементов графа;  при этом предполагается, что

§2.2. Цепи.  Циклы. Связность.

1. Последовательность вершин и ребер графа G называется путемиз вершиныв вершину,если

§2.3. Деревья.

1.  Ребро е произвольного графа G называется циклическим,если оно принадлежит хотя бы одному элементарному циклу в графе, и ациклическимв противном… Справедливы два простых утверждения: 1)  при удалении из связного графа циклического ребра граф остается связным;

в любом конечном дереве число ребер на единицу меньше числа вершин.

§2.5. Цикломатическое число.

1. Будем рассматривать подграфы, которые могут быть несвязными, но содержащие все вершины графа. Пусть G - граф, содержащий p занумерованных ребер…              если  ei H   и  ai = 0 если           (характеристический вектор…

2. Четный граф –если степени всех его вершин - четные числа. Любую   элементарную   цепь   (кроме   цикла)   в четном графе можно продлить ребром,  не принадлежащим цепи, так как конец цепи имеет степень 1   в цепи и степень не меньше 2 в графе.   Если граф конечен, то, продолжая цепь, мы через конечное число шагов вторично придем   в  уже пройденную вершину,   т.е.   часть полученной (уже не элементарной) цепи образует элементарный цикл,   после удаления которого остается  четный граф, так как все степени изменяются на четное число (2 - для вершин цикла и 0 - для вершин, не принадлежащих циклу). В этом графе можно снова выделить некоторый элементарный цикл и т.д., пока в графе не останется ни одного ребра. Таким образом, каждый конечный четный   граф можно представить   в   виде суммы попарно не пересекающихся (по ребрам) элементарных циклов, откуда следует, что каждое его ребро циклическое. Если конечный четный граф связан, то нетрудно показать что в нем существует простой (т.е.  не самопересекающийся по ребрам) цикл,  содержащий все ребра графа.   Такой цикл называется эйлеровым циклом,аобладающий им граф называется эйлеровым графом.

Теорема Эйлера.Для того чтобы конечный связный граф был эйлеровым, необходимо и достаточно, чтобы он был четным.

Из теоремы   Эйлера   можно вывести следствие:

В произвольном связном графе G раздвоим каждое ребро, т.е. заменим его парой  кратных  ребер   с  теми  же  вершинами.                     Степень каждой вершины удвоится и станет четной. В полученном четном графе  существует эйлеров цикл.

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

Итак, в каждом связном графе существует цикл, содержащий ровно 2 раза каждое ребро графа, что можно трактовать, как соответствующий обход лабиринта с возвращением в начало обхода.

3. Элементарный путь, проходящий через все вершины графа, называется гамильтоновым;если совпадают его начало и конец, то это гамильтонов цикл.

Известная задача о коммивояжере формулируется так: имеется n городов, попарные расстояния между которыми заданы. Коммивояжер желает посетить все города так, чтобы суммарная длина пути была минимальной. Это означает, что нужно найти гамильтонов путь минимальной длины в полном графе К_n, ребрам которого приписаны положительные числа - длины ребер (для варианта задачи - обхода с возвращением в начало пути - ищется минимальный гамильтонов цикл).

Рассмотрим граф G_n, вершины которого соответствуют всем (n!) перестановкам множества {1, 2,..., n}, а ребра связывают пары вершин, отличающиеся транспозицией соседних элементов (таким образом, каждая вершина соединена с (n - 1) другими вершинами). Тогда указанная последовательность соответствует гамильтонову пути в графе

4. Сумма двух четных подграфов любого графа есть также четный подграф. Еслии    - степени некоторой вершины в подграфахи соответственно, а – ее степень в пересечении, то степень s(α)

вершиныв подграферавна

Еслии-четные, тотакже четное. Поэтому четные подграфы образуют подпространство в пространстве всех подграфов, которое совпадает с подпространством, натянутым на множество всех элементарных циклов.

Перейдем к выяснению размерности v этого подпространства. Пусть G - связный граф с p ребрами и b вершинами, D - некоторый его остов. Число хорд равно (p - b + 1). Каждая хордавместе с единственной элементарной цепьюобразует элементарный цикл, причем векторы всех таких циклов (для разных хорд) образуют независимую системутак как каждый из циклов содержит ребро (свою хорду), не принадлежащее ни одному из остальных циклов системы. Отсюда

С другой стороны, каждый четный подграф, в частности любой простой цикл выражается через циклы системы Действительно, прибавим к четному подграфу Н те циклы изкоторые содержат хорды графа, принадлежащие Н. Полученная сумма не будет содержать ни одной хорды (каждая хорда входит в сумму дважды: в подграф Н и в один из циклов системы), т.е. будет некоторым подграфом дерева D, откуда следует, что это пустой подграф, так как в противном случае четный подграф (сумма Н и циклов), имеющий элементарные циклы, содержался бы в дереве D. Таким образом, v = p - b + 1.

Для несвязного графа с k компонентами связности базис пространства четных подграфов получается объединением базисов его связных компонент, а число ребер и вершин суммируется. Поэтому, если i-я компонента содержит p ребер и b вершин, то v = p - b + k, где

 .

 Число v называется цикломатическим числом графа.

§2.6. Технические приложения в теории графов.

1. Планарные графы.

- планарный, если в графе нет пересечений мимо узла ветвей.

Граф G считается k-планарным, если его ветви могут быть расположены на k-пересекающихся плоскостях, причем на каждой плоскости графы могут быть только планарными.

2. Сигнальные графы.

Граф где , в которой в каждой вершине приведем в соответствие некоторый сигнал а ветви передачи этого сигнала  называется сигнальным графом .

                                 

ГЛАВА 3. КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ ИНФОРМАЦИИ.

§3.1. Представление информации.

Кодирование – представление информации в виде сигналов и их характеристик. Декодирование – обратный процесс. Сигнал может представлять информацию в виде своих характеристик :

§3.2. Двоичные неизбыточные коды.

Основание этого кода равно 2 и длина должна обеспечивать передачу необходимого количества информации.

Рассмотрим преобразователь перемещения в двоичный неизбыточный код.

Рассмотрим возникновение ошибки при передаче от 3х до 4х 4 – 100

§3.3. Помехоустойчивые избыточные коды.

Такая ошибка в коде не обнаруживается и следовательно не может быть исправлена. Для обнаружения и исправления ошибок должны быть введены… Коды, в которых к разрядам несуществующей информации добавляя дополнительные… Для определения требуемого количества контрольных разрядов введем понятие «вес кодовой комбинации» или

            §3.4. Коды с проверкой на четность.

Код с проверкой на четность в системах передачи информации используется как код с проверкой на четность.  

§3.5. Код Хэмминга.

Исправляющую способность кода достигается за счет многократных проверок на четность определенных групп разрядов. L – число информационных разрядов… По результатам проверок на четность любого числа групп из k – контрольных… Общее число одиночных ошибок, которое может быть в n – разрядах, в том числе отсутствие ошибок дает нам n + 1 указание…