Теория множеств

Размещено на http://www.allbest.ru/

[Введите текст]

Дискретная математика

Методические указания

для самостоятельной работы студентов очной формы обучения

(I семестр)

Брянск 2008

УДК 518

Математика. Дискретная математика: методические указаниядля самостоятельной работы студентов очной формы обучения (I семестр). - Брянск: БГТУ, 2008. - 35 с.

Разработали: В.М. Кобзев, ст.преп.

Г.Г. Вискина, ст.преп

А.О Алейникова, асс.

К.А. Сенько, асс.

Рекомендовано кафедрой «Высшая математика» БГТУ(протокол № 1 от 30.08.07)

ПРЕДИСЛОВИЕ

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

Методические указания предназначены для студентов специальностей «Программное обеспечение», «Системы автоматизированного проектирования», «Основы защиты информации», «Профессиональное обучение», «Математическое обеспечение и администрирование информационных систем» и ряда других специальностей, изучающих дискретную математику.

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

1. РАЗБОР ТИПИЧНЫХ ЗАДАЧ

1.1 Элементы теории множеств

Множества. Операции над множествами

Объединением множеств А и В называется множество АВ = {x|xА или хВ}.

Пересечением множеств А и В называется множество АВ = {x|xА и хВ}.

Разностью множеств А и В называется множество А\В = {х|хА и хВ}.

Декартовым или прямым произведением множеств А и В называется множество всех пар вида (а, b), где аА, bВ.

1. Найти пересечение, объединение, разности и прямое (декартово) произведение множеств А и В.

а) А = {-1;0;3;4}, В = {0;4;6}

АВ = {-1;0;3;4;6}.

АВ = {0;4}.

А\В = {-1;3}; В\А={6}

= {(-1,0), (-1,4), (-1,6), (0,0), (0,4), (0,6), (3,0), (3,4), (3,6), (4,0), (4,4), (4,6)}.

б) А = [0;2], B=[1;5].

AB = [0;5]

AB = [1;2]

A\B = [0;1);B\A = (2;5]

= {(x;y)| x[0;2], y[1;5]}.

2. Доказать методом встречных включение и продемонстрировать на диаграммах Эйлера-Венна

A\(BC) = (A\B)(A\C).

Обозначим левую часть Х, правую часть У. Докажем, что Х = У.

1. Докажем, что ХУ. Пусть выбран произвольный элемент хХ, т.е. хА\(BC). Значит, хА и хBC, поэтому хА, х B и хС, тогда хА\B и хА\С, следовательно, х(А\B)(А\С). Значит, ху. Так как элемент x выбран произвольно, то ХУ.

2. Докажем, что УХ. Пусть выбран произвольный элемент уУ, т.е. у(А\B)(А\C). Значит, у(А\B) и y(A\C). Тогда уА и уВ, уА и уС, следовательно, уА и у(BC), поэтому уА\(BС). Значит, уХ. Так как элемент y выбран произвольно, то УХ.

Из 1. и 2. следует, что Х = У (рис.1).

3. Из 100 студентов 28 изучают английский язык, 30 - немецкий язык, 42 - французский язык, 8 - английский и немецкий язык, 10 - английский и французский язык, 5 - немецкий и французский язык и 3 студента - все 3 языка. Сколько человек не изучают ни одного языка? Сколько изучают только французский язык?



Пусть u - множество студентов. По условию мощность множества |u|=100 (рис.2). Пусть А - множество студентов, изучающих английский язык, N - множество студентов, изучающих немецкий язык, F - множество студентов, изучающих французский язык.

По условию |A| = 28, |N| = 30, |F| = 42, |AN| = 8, |AF| = 10, |NF| = 5, |ANF| = 3.

Необходимо найти множество студентов, не изучающих ни одного языка, т.е. |u\(ANF)| = |U| - (|A| + |N| + |F|) + |AN| + |AF| + |NF| - |ANF| = 20 и множество студентов, изучающих только французский язык |F\(AN)| = |F| - (|AF| + |NF|) + |ANF| = 30.

множество граф кодирование эквивалентность

1.2 Отображения. Инъективные и сюръективные отображения

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

Отображение АВ называется инъективным, если разные элементы множества A переходят в разные элементы множества B: если а в, то .

Отображение АВ называетсясюръективным, если каждый элемент множества В имеет свой прообраз в множестве А.

Если отображение одновременно инъективное и сюръективное, то оно называется биективным.

1. Пусть f: RR задано формулой f(x) = x2-1 (рис.3). Определить, является ли отображение f инъективным, сюръективным, биективным.

Область определения функции - R, область значений функции -
[-1;+).

f - отображение. Если (х,у)  f и (х,z)  f , то y = z, так как (x,y)f, т.е. y = x2-1, (x,z)f, т.е. z = x2-1.

Найдутся х1, х2R, такие что х1 х2, но: f(x1) = f(x2), например, пусть х1 = 1, х2 = -1, тогда f(x1) = 0 и f(x2) = 0, т.е. х1 х2, а f(x1) = f(x2). Таким образом, это неинъективное отображение.

Так как область значений функции [1;+) не совпадает с R, то отображение несюръективно.

2. Пусть f: RR задано формулой f(x) = x4. Является ли отображение инъективным, сюръективным?

Поскольку х1=2R, х2 = -2R, f(2) = f(-2) = 16, т.е. х1 х2, а f(x1) = f(x2), то отображение неинъективно.

Для любого xR не существует f(х), такого что f(х) = -16, так как х4 -16, поэтому отображение несюръективно.

3. Пусть отображение f: [0;+)[0;+) задано формулой f(x)=x2. Является ли оно инъективным, сюръективным?

Для любых х1, х2[0;+), х1 х2, f(x1)=x12, f(x2)=x22, но f(x1) f(x2), т.е для каждого х существует единственное f(x), следовательно, f(х) - инъективное отображение.

Для каждого значения f(x)[0;+) найдётся х[0;+), поэтому f(х) - сюръективное отображение.

из 1. и 2. следует, что отображение биективно.

1.3 Отношение эквивалентности

Всякое подмножество Г декартова произведения АхА называется отношением на множестве А.

Отношение Г называют рефлексивным, если aГа для всех aA.

Отношение Г называют симметричным, если аГbbГа.

Отношение Г называют транзитивным, если аГb, bГааГс.

Если отношение рефлексивно, симметрично, транзитивно, то оно называется отношением эквивалентности.

1. Проверить, является ли D отношением эквивалентности на R, если D={(x;y)| sin x = sin y}.

D - рефлексивно, так как для любого R ()D, т.е. для любого xR имеем sin x = sin x.

D - симметрично, так как для любой пары (,)D имеем ()D, т.е. для любых R из (x,y)D следует, что sin x = sin y, тогда и sin y = sin x, следовательно, (y,x)D.

D - транзитивно, так как для любых а,b,cR из того что ()D и ()D следует, что ()D, т. е. если (x,y)D, то sinx=siny, если (y,z)D, то sin y = sin z, тогда sin x=sin z, следовательно, (x,z) D.

Из 1., 2., 3. следует, что D - отношение эквивалентности на R (где R - множество действительных чисел).

2. Упражнение. Выяснить, является ли отношением эквивалентности, если ху = {(x,y)| x = 3y}.

1.4 Элементы теории кодирования

1. Закодировать слово «факультет».

Решение.

Создадим алфавит:

а00000 б00001 в00010 г00011 д00100 е00101 ж00110 з00111	и01000 й01001 к01010 л01011 м01100 н01101 о01110 п01111	р10000 с10001 т10010 у10011 ф10100 х10101 ц10110 ч10111	ш11000 щ11001 ъ11010 ы11011 ь11100 э11101 ю11110 я11111

Теперь каждую букву слова «факультет» закодируем в соответствии с алфавитом.

10100.00000.01010.10011.01011.11100.10010.00101.10010.

Разбиваем фразу на слова по 4 бита:

1010.0000.0001.0101.0011.0101.1111.0010.0100.0101.1001.0

К каждым четырём битам приписываем проверочные символы

р1 = ,

р2 = ,

р3 = ,

например, 1010 1010011 и т.д.

Закодированная фраза готова:

1010011.0000000.0001011.0101100.0011110.0101100.1111111.0010101.0100111.0101100.1001101.0

2. По каналу связи, в котором возможны единичные ошибки, получено слово

0010110.0001011.0001100.0010110.0000000

0100111.0000000.0010110.0010110.

Раскодировать исходное слово, используя алгоритм декодера (7,4)-кода Хемминга.

Решение.

Исходное слово разбиваем по 7 битов и высчитываем синдромы:

S1=,

S2=,

S3=.

Отбросив три проверочных бита, записываем слова в одну строку

По 7 битов	S1	S2	S3	Позиция ошибки	Исправленный вариант	Первые 4 бита
1)0010110	0	1	1	4	0011110	0011
2)0001011	0	0	0	0	0001011	0001
3)0001100	1	1	1	2	0101100	0101
4)0010110	0	1	1	4	0011110	0011
5)0000000	0	0	0	0	0000000	0000
6)1100111	1	1	0	1	0100111	0100
7)0000000	0	0	0	0	0000000	0000
8)0010110	0	1	1	4	0011110	0011
9)0010110	0	1	1	4	0011110	0011

00110.00101.01001.10000.01000.00000.11001.1.

Разбиваем по 5 битов, записываем получившиеся слова:

00110.00101.01001.10000.01000.00000.11001.1.

жейриащ

В соответствие с алфавитом записываем получившееся слово: «жейриащ».

Задание 3. (Упражнение). Закодирована «фраза»:

0110001.0000100.0011101.1110100.0010110.0110001.1011000.1100000.1011000.1110000.0100111.0111010.1110100.1110100.0000000.0111010.0010110.0100111.0001011.1111111.0001011.1011000.0101100.1110100.1000101.1000101.1000101.

Раскодировать ее, используя алгоритм декодера (7,4)-кода Хемминга.

Задание 4. Дана матрица . Определить, является ли она кодом, кодом Хемминга.

Решение.

Так как данная матрица содержит две строки и четыре столбца, то она может быть (4,2) кодом. Для проверки умножим каждую строку на данную матрицу слева. Имеем:



Таким образом,

Поскольку все полученные строки различны, то отображение инъективно, а следовательно, является кодом.

Так как строки (1) и (3) множества отличаются ровно на два бита (), то код не является кодом Хемминга.

1.5 Элементы теории графов.Поиск путей в графе

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

Вершины х и у графа, соединенные дугой, называют смежными.

Говорят, что вершины инцидентны ребру (дуге).

Степень вершины графа - это число ребер, ей инцидентных.

Зафиксируем в графе 2 вершины А и В. Исторически возникли 3 задачи о поиске путей в графе.

Задача 1. Найти любой (или простой, или гамильтонов, или эйлеров) путь (цепь) из А в В.

1. Дан граф (рис.4).

Найти все простые пути из А в В. Показать один из них на рисунке.

Решение. Обозначим все вершины графа буквами. Используя определение простого пути, получим простые пути в данном графе. Перечислим их (рис.5).

АСВ

АСМВ

АСМДВ

АДВ

АДМВ

АДМСВ

АМВ

АМСВ

АМДВ

Покажем один из этих путей на рис. 6.

Задача 2. Найти кратчайший путь из А в Вв смысле количества ребёр (дуг).

2. Дан граф (рис.7).

а) определить степени вершин А и В.

б) найти кратчайший путь из точки А в точку В (в смысле наименьшего количества ребер).

Решение

а) используя определение степени вершины, выясним, какие степени имеют вершины А и В. Вершина А имеет степень 3, так как 3 - число ребер, ей инцидентных. Аналогично, и вершина В имеет степень 3.

б) используем алгоритм решения задачи о нахождении кратчайшего пути из А в Вв смысле наименьшего количества ребер:

Вершине А припишем индекс 0.

Всем вершинам, смежным с А, припишем индекс 1.

Всем вершинам, смежным с вершинами индекса 1 и не имеющим индекса, припишем индекс 2 и т.д.

Как только вершина В получит некоторый индекс, процесс останавливаем (даже если остались непронумерованные вершины).

Итак, (рис.8)

Следовательно, n = 2 - длина кратчайшего пути. Построим этот путь.

Среди вершин, смежных с В, обязательно найдется вершина с индексом (n - 1) (одна или несколько), возвращаемся в эту вершину и продолжаем этот процесс.

Через n шагов придем в вершину с индексом 0, т.е. в А. Один или несколько путей построены.

Итак, (рис. 9).



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

Задача 3. Найти кратчайший путь из А в В во взвешенном графе (в смысле суммы весов ребер (дуг)).

Рассмотрим следующий алгоритм решения задачи 3.

Будем постепенно приписывать всем вершинам графа числовые индексы:

Вершине А припишем индекс 0, всем остальным вершинам приписываем значение +.

Замечание: в реальных программах в роли + используется любое большое число, заведомо большее суммы всех весов рёбер.

Будем постоянно перебирать все пары смежных вершин х и у, каждый раз проверяя неравенство . Если оно выполняется, то уменьшаем индекс , заменив его на (рис.10).

y

Рис.10

3. Процесс останавливаем, когда ни один индекс уже нельзя уменьшить. В этот момент вершина В имеет некий индекс . Это и есть наименьшая сумма весов всех дуг.

4. Построим путь с такой суммой. Будем возвращаться извершины В в А. Среди вершин, смежных с В, обязательно найдётся вершина С, для которой выполняется точное равенство (если бы , то индекс можно было бы ещё уменьшить, если бы для всех смежных вершин, то непонятно, откуда взялся индекс .)

Возвращаемся к С и повторяем процесс. Поскольку индексы всё время уменьшаются, то через несколько шагов придём в вершину с индексом 0, т.е. в вершину А.

Задача. Задан граф.

а) превратить его во взвешенный граф с помощью набора данных (веса на горизонтальных ребрах отмечены буквой X, на вертикальных ребрах - буквой Y);

б) найти кратчайший путь (или пути) из вершины А в вершину В.

X: 93314359716255718352;

Y: 77166529261868239721.

Решение.



а)

Рис. 11

Превращаем граф в нагруженный, подставляя веса ребер слева направо (по оси Ox) и снизу вверх (по оси Oy) (рис. 11);

б) действуем по алгоритму: вершине А приписываем индекс 0, остальным вершинам +. Вершины, смежные с А, получают новые индексы: вершина (0; 1): 0 + 9 = 9, вершина (1; 0): 0 + 7 = 7. Вершина (1; 1) может получить индекс 7 + 4 = 11 или 9 + 6 = 15. выбираем наименьший из возможных индексов - 11 (рис 12).



Рис 12

Действуя аналогичным образом, присваиваем новые индексы всем вершинам. При этом вершина В получает индекс 27 (рис. 13).



Рис. 13

Индекс 27 = 26 + 1, следовательно, из вершины В нужно идти вниз, в вершину (4; 3) с индексом 26. 26 = 25 + 1, из вершины (4; 3) переходим в вершину (3; 3)с индексом 25. Этот индекс может быть получен двумя способами: 25 = 23 + 2 = 18 + 7, т.е. получаем два пути. 18 = 17 + 1, 23 = 17 + 6; оба пути сходятся в вершине (2; 2). 17 = 16 + 1; 16 = 11 + 5; 11 = 7 + 4; 7 = 0 + 7.

мы вернулись в вершину А. Таким образом, построены два пути с наименьшей суммой весов, равной 27 (рис. 14).



Рис. 14

Вот эти пути: (0; 0) - (0; 1) - (1; 1) - (1; 2) - (2; 2) - (2; 3) - (3; 3) - (3; 4) - (4; 4)и (0; 0) - (0; 1) - (1; 1) - (1; 2) - (2; 2) - (3; 2) - (3; 3) - (3; 4) - (4; 4).

1.6Представление графов в памяти компьютера

Пусть дан орграф с n пронумерованными вершинами. Матрица А размером nn, заполненная числами

aij=

называется матрицей смежности орграфа.

Такая матрица определяет орграф однозначно вместе с нумерацией вершин.

Точно также строится матрица смежности неориентированного графа. Она обладает дополнительным свойством aij= aji, т.е. матрица симметрична относительно главной диагонали. Поэтому достаточно хранить в памяти только верхний треугольник матрицы смежности A'.

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

Рис. 15

Расположим А' в виде двоичной строки (слева направо, сверху вниз). Меняя нумерацию вершин, мы получим другие двоичные строки. Сравним их между собой как двоичные числа. Наибольшее из двоичных чисел называется кодом Харари, а возникшая при этом нумерация вершин - канонической. Код Харари определяет граф однозначно, но не всякое число может быть кодом Харари.

1. Найти код Харари графа (рис. 16)

Рис. 16

Решение.

Пронумеруем вершины графа, выпишем матрицу смежности и ее верхний треугольник (рис. 17).

, верхний треугольник, записанный в виде строки, имеет вид 01010111002 = 34810.

Легко увидеть, что данная нумерация вершин не является канонической. Действительно, сменим нумерацию вершин (рис. 18).



, верхний треугольник, записанный в виде строки, имеет вид 11000110102 = 79410.

Можно убедиться, что при всех других способах нумерации вершин получаются числа, меньшие 794. следовательно, последняя нумерация вершин является канонической, а кодом Харари данного графа является число 794.

Восстановить и нарисовать граф по числу 501 как по коду Харари. Проверить, действительно ли нумерация вершин каноническая (то есть, является ли это число кодом Харари).

Решение.

Переведем число 501в двоичную форму, для чего будем последовательно делить его на 2, справа от черты записывая остатки от деления, а слева на следующей строке частные.

5011

2500

1251

0620

0311

0151

0071

0031

001

Затем выписываем число, начиная с последнего частного, и далее все остатки снизу вверх: 01111101012. Код Харари должен быть треугольным числом, т.е. иметь длину 1, 3, 6, 10, 15, 21 и т.д., если длина, как в нашем случае, не совпадает ни с одним из этих чисел, то добавляем слева необходимое количество нулей (в данном примере добавлен один ноль слева). Разбиваем число на разряды: 0111-110-10-1, вписываем эти числа в верхний треугольник матрицы, затем восстанавливаем всю матрицу, записывая ее строки по столбцам:

Восстанавливаем по этой матрице граф с четырьмя вершинами (рис. 19):

Заметим, что данная нумерация вершин не является канонической. Перенумеруем вершины (рис. 20):



Рис. 20

Для получившегося графа матрица смежности

, верхний треугольник, записанный в виде строки, имеет вид 11101100112 = 94710.

947 > 501, значит, число 501 не является кодом Харари графа.

3. Найти префиксный код бинарного ордерева (рис.21).

Рис. 21



Решение.

Будем последовательно приписывать вершинам данного ордерева двоичные строки, состоящие из нулей и единиц. Корню не припишем ничего, его левому потомку припишем 0, правому - 1 (рис 22).

Рис. 22

Левому потомку 0 припишем индекс 00, а правому - 01, левому потомку 1 припишем индекс 10, а правому - 11 (см. рис 23).

Рис. 23

Продолжим этот процесс, пока все висячие вершины не получат некоторый двоичный индекс (рис. 24).



Рис. 24

Выпишем индексы висячих вершин слева направо.

{000, 001, 011, 101, 11}.

Это и есть префиксный код для заданного бинарного ордерева.

4.Восстановить бинарное ордерево по префиксному коду {00,010,011,101,11}.

Решение.

Поскольку наибольшая длина двоичной строки в коде равна трём, то бинарное ордерево имеет не более трёх уровней.

Так как первые цифры строк равны либо 0, либо 1, то корень имеет два потомка (рис. 25).

При этом каждый потомок корня имеет два потомка (рис.26).

Вершины 00 и 11 имеются в префиксном коде, поэтому уже являются висячими. Вершина 01 имеет два, а вершина 10 - одного потомка (рис.27).

Поскольку отмечены все висячие вершины, составляющие префиксный код, то процесс завершён.

5. Найти код Прюфера заданного дерева (рис. 28).

Решение.

Запишем список всех вершин в порядке возрастания номеров:

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}.

Рассматривая список слева направо, находим первую висячую вершину. В нашем случае это вершина № 3. Определяем номер смежной с ней вершины (№ 2) и записываем его в новый список. При этом номер висячей вершины «удаляем» из первоначального списка:

список 2: {2, …},

список 1: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11},

а саму вершину из дерева (рис. 29).

Возвращаемся к началу списка 1 и повторяем процесс: находим первую висячую вершину (№ 4), определяем номер смежной с ней вершины (№ 2) и записываем его в новый список. При этом номер висячей вершины «удаляем» из первоначального списка:

список 2: {2, 2…},

список 1: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11},

а саму вершину из дерева (рис. 30).



Повторяем процесс до тех пор, пока в списке 2 не окажется числа, где - количество вершин в исходном дереве (в нашем случае ).

Окончательно, получаем список 2: {2, 2, 1, 1, 1, 6, 7, 7, 6}. Это и есть код Прюфера для данного дерева.

6. Восстановить дерево по коду Прюфера: {3, 3, 2, 5, 5}.

Решение.

Определим количество вершин искомого дерева. В коде Прюфера 5 чисел, количество вершин на 2 больше, поэтому дерево имеет 7 вершин ().

Выпишем список всех вершин в порядке возрастания:

список 1: {1, 2, 3, 4, 5, ,6, 7}.

Слева направо просматриваем список 1, сравнивая его с кодом Прюфера (списком 2). Первая вершина, не входящая в код Прюфера, является висячей. В нашем случае это вершина № 1. Рисуем ребро дерева, соединяющее эту вершину с вершиной, стоящей первой в коде Прюфера (то есть с вершиной № 3) (рис. 31).



Номер висячей вершины удаляем из списка 1, в списке 2 отмечаем использованный номер вершины (например, подчёркиваем):

список 2: {3, 3, 2, 5, 5},

список 1: {1, 2, 3, 4, 5, 6, 7}.

Снова слева направо просматриваем список 1, сравнивая его с кодом Прюфера (списком 2). Первая вершина, не входящая в код Прюфера, является висячей. Теперь это вершина № 4. Рисуем ребро дерева, соединяющее эту вершину с вершиной, являющейся первой неотмеченной в коде Прюфера (то есть с вершиной № 3) (рис. 32).

Номер висячей вершины удаляем из списка 1, в списке 2 отмечаем использованный номер вершины:

список 2: {3, 3, 2, 5, 5},

список 1: {1, 2, 3, 4, 5, 6, 7}.

Ещё раз слева направо просматриваем список 1, сравнивая его с кодом Прюфера (списком 2). Первая вершина, не входящая в код Прюфера, является «висячей». Это уже вершина № 3. Рисуем ребро дерева, соединяющее эту вершину с вершиной, являющейся первой неотмеченной в коде Прюфера (то есть с вершиной № 2) (рис.33).

Номер висячей вершины удаляем из списка 1, в списке 2 отмечаем использованный номер вершины:

список 2: {3, 3, 2, 5, 5},

список 1: {1, 2, 3, 4, 5, 6, 7}.

Повторяем процесс до тех пор, пока не отметим все номера в списке 2. В результате получим (рис.34).



При этом в списке 1 останется две вершины (№ 5 и № 7). Поскольку одна из них (№ 5) есть в коде Прюфера, то вторая (№ 7) является висячей. Добавляем висячую вершину в рисунок (рис.35).

Искомое дерево построено.

Обойти бинарное ордерево тремя способами (рис.36).

Решение.

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

Прямой обход (КЛП - обойти корень, левое поддерево, затем правое поддерево): .

Обратный обход (ЛКП - обойти левое поддерево, корень, затем правое поддерево): .

Концевой обход (ЛПК - обойти левое поддерево, правое поддерево, затем корень): .



2. ЗАДАЧИ О РАСКРАСКЕ ГРАФА

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

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

Постановка задачи. Дан связный граф. Требуется найти значение хроматического числа и соответствующую раскраску вершин.

Алгоритм решени.

Вычислить степени всех вершин, положить .

Расположить вершины по убыванию их степеней и первую из неокрашенных вершин окрасить в цвет .

Просмотреть вершины в порядке убывания степеней и окрасить в цвет № все вершины, которые несмежны с вершинами, уже окрашенными в цвет № .

Если все вершины уже окрашены, то . Если нет, то и переходим к шагу 2.

Определение. Правильная раскраска рёбер графа - это раскраска рёбер графа некоторым количеством цветов так, чтобы никакие два инцидентных ребра графа не были окрашены в одинаковые цвета.

Минимальное число цветов необходимое для правильной раскраски рёбер графа называется хроматическим индексом графа (обозначается ).



ВОПРОСЫ К ЭКЗАМЕНУ

Что называется объединением, пересечением множеств?

Что называется разностью, симметрической разностью, дополнением множества?

Как проиллюстрировать диаграммой Эйлера-Венна одно из тождеств теории множеств?

Что такое однозначное (многозначное) отображение?

*Что такое инъективное, сюръективное, биективное отображение?

Что такое мощность конечного множества и как это связано с биекцией?

Что такое декартово произведение множеств и что вы знаете о его мощности?

*Что вы знаете о мощности множества двоичных наборов?

Какова мощность множества всех подмножеств данного множества?

Что такое отношение на множестве (с примерами)?

Что такое рефлексивное, симметричное, транзитивное отношение?

*Что такое отношение эквивалентности и каково его основное свойство?

*Что такое отношение нестрогого порядка?

*Что такое отношение строгого порядка?

Что такое вполне упорядоченное множество, цепь?

Каковы основные элементы канала связи?

В чем задача кодера и декодера?

В чем суть основополагающего вывода Шеннона?

*Что такое алфавит, буква, слово?

*Что такое код?

Что такое двоичный (n,k)-код ?

Что такое скорость(n,k)-кода и к чему она стремится при эффективном кодировании?

*Что такое расстояние Хемминга и как оно связано с исправлением единичных ошибок?

*Каков алгоритм кодера (7,4)-кода Хемминга?

Символом * отмечены вопросы, обязательные для студентов, получивших по теории четыре балла и выше; остальные студенты готовят к экзамену все вопросы.

*Каков алгоритм декодера (7,4)-кода Хемминга?

Что вы знаете о существовании других кодов Хемминга?

Как связано расстояние Хемминга с исправлением нескольких ошибок?

Что такое конечное поле GF(q) и каковы в нем операции?

В чем идея РМ-кодов, РС-кодов, БЧХ-кодов?

В чем идея каскадных кодов?

Что называется орграфом, графом, вершиной, дугой, ребром?

Что такое путь, цепь, контур, цикл?

Что такое связный граф, компонента связности?

Что такое мультиграф, взвешенный (нагруженный) граф?

В чем состоят три задачи о кратчайшем пути в графе?

*Каков алгоритм решения задачи 2 ?

*Каков алгоритм решения задачи 3 ?

Что такое эйлерова цепь (цикл) и задача Эйлера?

*У каких графов существует эйлерова цепь (цикл)?

Что такоеплоский и планарный граф?

*В чем состоит формула Эйлера и для каких объектов она верна?

*Как выглядят непланарные графы № 1 и №2, типов 1 и 2 ?

В чем состоит теорема Куратовского-Понтрягина?

Что такое толщина графа и какое неравенство для нее вы знаете?

В чем состоит теорема Уитни?

*Что такое матрица смежности орграфа и каким свойством обладает матрица смежности неориентированного графа?

Что показывают элементы степеней матрицы смежности?

*Что называется деревом, ордеревом, бинарным ордеревом?

*Как строится код Харари?

Что такое матрица инцидентности?

*Как строится код Прюфера?

Что называется уровнем вершины ордерева, глубиной ордерева, висячей вершиной ордерева и дерева?

Как строится префиксный кодбинарного ордерева?

Какие три способа обхода бинарного ордерева вы знаете?

Как связаны число вершин бинарного ордерева и его глубина?

Что такое дерево поиска и как вести поиск в нем?

Что такое идеально сбалансированное, сбалансированное ордерево?

Что называется атомом, списком и как связаны деревья со списками?

*В чем состоит задача о раскраске вершин графа и каков алгоритм ее решения?

*В чем состоит задача о раскраске ребер графа и что вы знаете о хроматическом индексе?



СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

1. Кузнецов, О.П. Дискретная математика для инженера/ О.П. Кузнецов. - Изд. 3-е, перераб. и доп. - СПб. Лань, 2004. - 394 с.

2. Спирина, М.С. Дискретная математика: учебник/ М.С. Спирина, П.А. Спирин. - М.: ACADEMIA, 2004. - 367 с.

3. Пугач, Л.И. Высшая математика. Задачи по дискретной математике, математической логике и теории алгоритмов : метод. указания к практическим занятиям для студентов 1 курса специальностей 220400 "Программное обеспечение", "22300 " Системы автоматизированного проектирования" и 075300 "Организация и технология защиты информации"/ Л.И. Пугач ; БГТУ. - Брянск: Изд-во БГТУ, 2005. - 16 с.

4. Асеев, Г.Г. Дискретная математика: учеб. пособие/ Г.Г. Асеев, О.М. Абрамов, Д.Э. Ситников. - Феникс: Торсинг, 2003. - 141 с.

5. Яблонский, С.В. Введение в дискретную математику: учеб. пособие для вузов/ С.В. Яблонский. - 3-е изд., стер. - М.: Высш. шк., 2001. - 384с.

6. Белоусов, А.И. Дискретная математика: учебник/ А.И. Белоусов, С.Б. Ткачев; под ред. В.С. Зарубина, А.П. Крищенко. - М.: МГТУ им Н.Э. Баумана, 2001. - . вып. 19. - 743с.

7. Горбатов, В.А. Основы дискретной математики: учеб. пособие для вузов/ В.А. Горбатов. - М.: Высш. шк., 1986. - 310 с.

8. Горбатов, В.А Дискретная математика: учебник для студентов втузов/ В.А. Горбатов, А.В. Горбатов, М.В. Горбатова - М., 2003. - 447 с.

9. Фалевич, Б.Я. Теория алгоритмов: учеб. пособие/ Б.Я. Фалевич. - М.: Машиностроение, 2004. - 160 с.

10. Введение в криптографию: Новые математические дисциплины./ В.В. Ященко [и др.]; под ред. В.В. Ященко. - СПб. и др.: МЦНМО: Питер, 2001. - 287с.

Размещено на Allbest.ru

...