Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

Практические задания по графам

1. В табл. 3.44 даны вероятности сообщений по вариантам, например:

3 × 0,01 + 0,02 + 0,05 + 3 × 0,1 + 3 × 0,2.

Такая запись означает, что имеются три сообщения с вероятностью 0,01, три с вероятностью 0,1 и три с вероятностью 0,2, а также два сообщения с вероятностями 0,02 и 0,05; в сумме все вероятности равны 1,0. Требуется построить таблицы и кодовые деревья Фано и Хаффмана. Вычислить и сравнить средние длины кодовых слов. Далее, приняв для своего ряда событий вероятности обращения к внешним и внутренним вершинам в следующем порядке:

p₀, q₁, p₁, q₂, p₂, q₃, …,

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

Таблица 3.44

2. В табл. 3.45 для 30 вариантов приведены дуги ориентированного графа, вершины которого пронумерованы от 01 до 16, причем первое число указывает начало, второе — конец дуги. На основе аналитических выражений для прямого и обратного транзитивных замыканий найти все классы эквивалентности для графа вашего варианта. Результаты вычислений проверить путем непосредственных преобразований матрицы смежности. В отчете о проделанной практической работе привести два рисунка: графическое изображение исходного графа, когда его вершины в порядке возрастания номеров расположены по окружности, наподобие циферблата, и этого же графа, но разложенного уже на сильно связанные подграфы.

Таблица 3.45

3. В табл. 3.46 для 30 вариантов приведены дуги ориентированного графа с 18 вершинами, который не содержит контуров (первое число указывает начало, второе — конец дуги). Каждая дуга имеет вес, который численно равен сумме номеров вершин, инцидентных началу и концу дуги. Необходимо произвести разбивку графа на классы порядка. Затем найти два оптимальных пути, отвечающих минимальному и максимальному общему весу. Пути начинаются с вершины нижнего уровня, а заканчиваются на вершине верхнего уровня.

Таблица 3.46

4. В табл. 3.47 для 30 вариантов перечислены дуги ориентированного графа (первое число указывает начало, второе — конец дуги). Определить центр графа и отклонение от центра для каждой вершины. Используя матрицу смежности, рассчитать общее число путей в 1, 2, 3, 4, 5 и 6 дуг, а также с помощью поименнованной матрицы смежности получить все элементарные пути указанной длины. (В каждой последующей поименнованной матрице все неэлементарные пути следует опускать.)

Таблица 3.47

5. В табл. 3.48 для 30 вариантов перечислены ребра симметричного графа. Для графа своего варианта построить дополнительный граф и определить полную группу подстановок, оставляющую графы без изменения. Коммутационное соотношение привести только для двух подстановок, используя матрицы смежности исходного и дополнительного графа. Относительно обоих графов построить соответствующие им двойственные графы, затем для каждого из четырех графов найти элементы матроида, т.е. перечислить все базы и циклы, найти ранг и цикломатическое число, подсчитать количество возможных остовов.

Таблица 3.48

6. В табл. 3.49 для 30 вариантов приведены семейства вершин для двудольного графа и гиперграфа.

(а) По данным вашего варианта построить двудольный граф и реберный ему граф. Для двудольного графа выписать максимальные паросочетания и минимальные реберные покрытия. Для реберного графа определить все максимальные вершинные независимые множества и все минимальные вершинные покрытия. С этой целью использовать булеву функцию реберного графа, записав ее в КНФ; далее, воспользовавшись законами поглощения, найти булеву функцию в ДНФ; и, наконец, произвести проверку найденных выражений с помощью принципа двойственности.

(б) По данным вашего варианта построить гиперграф и, воспользовавшись матрицей инцидентности, — двойственный ему граф. Для обоих графов указать наибольшие паросочетания и наименьшие реберные покрытия. Используя булевы функции, найти минимальные трансверсальные покрытия и максимальные множества независимых вершин. Проверить правильность нахождения этих множеств, исходя из принципа двойственности булевых функций.

Таблица 3.49

7. На рис. 3.73 приведены 30 многогранников. Для многогранника своего варианта вычертите соответствующий граф, постройте двойственный ему, найдите для обоих графов их матрицы смежности и определите группу симметрии. Две подстановки проверьте на выполнение коммутационного соотношения.