🗊Презентация Дискретная математика. Множество

Федеральное государственное бюджетное образовательное учреждение высшего образования «КЕМЕРОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»  Кафедра прикладной математики ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1 курс лекций  Кемерово 2018   © С. Г. Гутова, 2018 © Кемеровский государственный университет, 2018 ISBN 978-5-8353-1686-1  Об издании – 1, 2, 3

Оглавление

Лекция 1 Множества

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

Георг Кантор определил множество так: Множество – это многое, мыслимое как целое.

Например: Например: множество всех станций Московского метро; множество левых ботинок; множество натуральных чисел: 1, 2, 3, 4 и т. д.; множество символов, доступных специальному печатающему устройству; множество кодов операций конкретного компьютера.

множество всех натуральных чисел: 1, 2, 3, . . Обозначим N. Часто 0 считают натуральным числом. Множество N с добавлением 0 обозначается  . множество всех натуральных чисел: 1, 2, 3, . . Обозначим N. Часто 0 считают натуральным числом. Множество N с добавлением 0 обозначается  . множество всех натуральных чисел, не превосходящих 100. множество всех решений уравнения

Множество, не содержащее элементов, называется пустым множеством и обозначается Ø. Множество, не содержащее элементов, называется пустым множеством и обозначается Ø.

Способы задания множества Перечисление всех элементов множества (список), например, множество однозначных неотрицательных чисел Множества часто рассматриваются как «неупорядоченные совокупности элементов», хотя иногда полезно подчеркнуть, что, например

Выяснить, какие из приведенных определений верные? Выяснить, какие из приведенных определений верные?

Порождающая процедура Описывает способ получения элементов множества из уже полученных элементов либо других объектов. Тогда элементы множества – все объекты, которые могут быть получены (построены) с помощью такой процедуры.

Множество натуральных степеней двойки: 2, 4, 8, 16, 32, 64, 128… Множество натуральных степеней двойки: 2, 4, 8, 16, 32, 64, 128… Порождающую процедуру зададим рекуррентно:

Пример 2 Какое множество задается рекуррентной формулой:

Задание множества описанием его элементов (разрешающая процедура)

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

Множество U называется универсальным множеством (множество элементов всех подмножеств) для некоторой системы множеств, если каждое множество этой системы является подмножеством U, т.е. Множество U называется универсальным множеством (множество элементов всех подмножеств) для некоторой системы множеств, если каждое множество этой системы является подмножеством U, т.е.

Объединением двух множеств А и В называется множество , состоящее из тех элементов, которые принадлежат или множеству А, или В, или А и В одновременно. Объединением двух множеств А и В называется множество , состоящее из тех элементов, которые принадлежат или множеству А, или В, или А и В одновременно. Рис.3. Объединение множеств

Разностью двух множеств А и В Разностью двух множеств А и В ( или ) называется множество тех элементов множества А, которые не принадлежат множеству В: Рис.5. Разность множеств

Прямым (декартовым) произведением двух множеств А и В называется множество, состоящее из упорядоченных пар элементов, в которых первый элемент принадлежит множеству А, а второй – множеству В. Прямым (декартовым) произведением двух множеств А и В называется множество, состоящее из упорядоченных пар элементов, в которых первый элемент принадлежит множеству А, а второй – множеству В.

Пример 3

Пояснение:

Пояснение:

Пояснение:

Пояснение:

Пример 4: Прямое (декартово) произведение: = {(-2, 0); (-2, 2); (-2, 4); (-2, 5);(-1, 0); (-1, 2); (-1, 4); (-1, 5);(0, 0); (0, 2);(0, 4);(0, 5); (1, 0); (1, 2); (1, 4); (1, 5); (2, 0); (2, 2); (2, 4); (2, 5)}; = {(0, -2); (0, -1); (0, 0); (0, 1); (0, 2); (2, -2); (2, -1); (2, 0); (2, 1); (2, 2); (4, -2); (4, -1); (4, 0); (4, 1); (4, 2); (5, -2); (5, -1); (5, 0). (5, 1); (5, 2)}

Из примера 2 видно, что Из примера 2 видно, что

Пример 5

Лекция 2 Векторы и прямые произведения множеств. Проекция вектора на ось

Векторы Векторы Вектор – это упорядоченный набор элементов. Его элементы зазываются координатами или компонентами вектора. Длина (размерность) вектора – число координат вектора. В отличие от элементов множества, его координаты могут совпадать. Обозначение вектора: в круглых скобках, координаты – через запятую (0, 5, 4, 5, 0, 1). Иногда скобки и даже запятые опускаются.

Векторы длины 2 называют упорядоченными парами; длины 3 – тройками; и т.д., длины n – n-ками. Векторы длины 2 называют упорядоченными парами; длины 3 – тройками; и т.д., длины n – n-ками. Два вектора равны, если они имеют одинаковую длину, и соответствующие координаты равны, т. е. если и

Прямое произведение n множеств Прямое произведение n множеств Прямое произведение множеств называется множеством всех векторов , длины n таких, что Иначе говоря

Пример 1: Найти прямое произведение множеств Перечисляем тройки элементов в лексико-графическом порядке.

Пусть А – конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания, знаки операций и т. д.). Такие множества обычно называют алфавитом. Пусть А – конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания, знаки операций и т. д.). Такие множества обычно называют алфавитом. Примеры алфавитов: 33 русских буквы, 26 латинских букв, 10 арабских цифр; список символов клавиатуры компьютера.

Слова длины n в алфавите А – это элементы множества Множество всех слов в алфавите А – это множество Слова длины n в алфавите А – это элементы множества Множество всех слов в алфавите А – это множество Здесь слово определено как вектор. При написании слова не принято пользоваться разделителями: скобками, запятыми; они могут оказаться символами самого алфавита. Поэтому слово в алфавите обозначается как конечная последовательность символов из алфавита А.

Пример 2: 1) Десятичное число – слово в алфавите цифр {0, 1, 2, 3, ... , 9}. 2) Двоичное слово в алфавите {0, 1}. 3) Текст, отпечатанный на машинке – слово в алфавите, определяемом клавиатурой этой машинки.

Теорема (о мощности прямого произведения множеств) Пусть конечные множества и Тогда мощность множества равна произведению мощностей множеств:

Следствие: Например, множество двоичных векторов длины 3, содержит

Проекции множества векторов на оси Проекцией вектора длины n на i-ю ось называется его i-я координата. Обозначается это так: Например: , тогда

Проекцией вектора Проекцией вектора длины n на оси с номерами называется вектор, составленный из соответствующих координат. Обозначается это так: Например: , тогда

Пусть дано множество V векторов одинаковой длины. Проекцией множества векторов на i-ю ось называется множество проекций на i-ю ось всех его векторов. Обозначается это так: Например: Например: , тогда

Проекцией множества векторов на оси с номерами называется Проекцией множества векторов на оси с номерами называется множество проекций на оси с номерами всех его векторов. Обозначается: Например: тогда

Пример 3: Дано множество векторов: V = {(Иванов Александр Николаевич), (Иванов Михаил Александрович), (Иванов Сергей Александрович)}. пр1 V = {Иванов}, пр2 V = {Александр, Михаил, Сергей}, пр23 V = {(Александр Николаевич), (Михаил Александрович), (Сергей Александрович)}.

Пример 4

Пример 4

Пример 4

Пример 4

Лекция 3 Комбинаторика

Правило суммы Классическая формулировка Если элемент α можно выбрать k способами, а элемент β можно выбрать m способами. Тогда α или β можно выбрать k + m способами.

Теорема о мощности объединения множеств Теорема о мощности объединения множеств (современная формулировка) Количество элементов объединения двух множеств равно сумме количества элементов в первом и во втором множестве, за вычетом количества элементов их пересечения:

Причем, если множества не пересекаются, то теорема приобретает вид, аналогичный классической формулировке:

Для трех множеств теорема имеет вид: Для трех множеств теорема имеет вид:

Пример 1 Пример 1 Из 35 учащихся класс по итогам года имели “5” по математике – 14 человек; по физике – 15 человек; по химии – 18 человек; по математике и физике – 7 человек; по математике и химии – 9 человек; по физике и химии – 6 человек; по всем трем предметам – 4 человек. Сколько человек имеют “5” по указанным предметам? Сколько человек не имеет “5” по указанным предметам? Имеет “5” только по математике? Имеет “5” только по двум предметам?

Пример 1 Пример 1 Введем обозначения. Обозначим буквой U множество всех учеников класса, буквой М множество учеников, имеющих «5» по математике, буквой Ф – имеющих «5» по физике, Х – имеющих «5» по химии. Тогда, согласно условию,

Пример 1 Пример 1 На рисунке 1 приведено множество, состоящее из учеников, имеющих «5» хотя бы по одному из указанных предметов. Рис.1. Множество учеников, имеющих «5» хотя бы по одному предмету

Пример 1 Пример 1 Очевидно, что это объединение множеств М, Ф и Х. Для нахождения количества элементов объединения воспользуемся правилом суммы.

Пример 1 Пример 1 На рисунке 2 приведено множество, состоящее из учеников, не имеющих «5» ни по одному из указанных предметов. Обозначим его буквой Н. Рис. 2. Множество учеников, не имеющих «5» по указанным предметам

Пример 1 Пример 1 Очевидно, что это разность между универсальным множеством U и объединением множеств М, Ф и Х.

Пример 1 Пример 1 На рисунке 3 приведено множество, состоящее из учеников, имеющих «5» только по математике. Обозначим его буквами ТМ. Рис. 3. Множество учеников, имеющих «5» только по математике

Пример 1 Пример 1 Очевидно, что это разность между множеством М и множествами ТМФ – имеющих «5» только по математике и физике, ТМХ – имеющих «5» только по математике и химии, и

Пример 1 Пример 1 На рисунке 4 приведено множество, состоящее из учеников, имеющих «5» только по двум предметам. Обозначим его Т2. Очевидно, что Т2 является суммой трех непересекающихся множеств ТМФ, ТМХ, ТФХ. Рис. 4. Множество учеников, имеющих «5» только по двум предметам  

Найдем мощность каждой части искомого множества: Тогда искомая мощность примет вид:

Правило произведения Классическая формулировка Если элемент α можно выбрать k способами, а элемент β можно выбрать m способами. Тогда пару α и β можно выбрать km способами.

Теорема о мощности прямого произведения множеств (современная формулировка) Теорема о мощности прямого произведения множеств (современная формулировка)

Пример 2: Из 3 экземпляров учебника алгебры, 7 экземпляров учебника геометрии и 6 экземпляров учебника физики, надо выбрать комплект, содержащий все учебники по одному разу. Сколькими способами это можно сделать? Ответ: 3 ⨉ 7 ⨉ 6 = 126.

Пример 2: Из 10 арабских цифр составляют 5-значный код. Сколькими способами это можно сделать так, чтобы: а) все цифры были разными; б) на последнем месте четная цифра. а) 10 ⨉ 9 ⨉ 8 ⨉ 7 ⨉ 6; б) 10 ⨉ 10 ⨉ 10 ⨉ 10 ⨉ 5.

Число размещений без повторений Число размещений без повторений из n по k – это число способов, сколькими можно из n различных элементов построить векторов с k различными координатами. Число размещений без повторений находится по формуле:

Число размещений без повторений Пример 3: Сколькими способами можно построить 3-значное число с различными цифрами, не содержащее цифры 0?

Число размещений с повторениями Число размещений с повторениями из n по k – это число способов, сколькими можно из n различных элементов построить векторов с k координатами, среди которых могут быть одинаковые. Число размещений с повторениями находится по формуле:

Число размещений с повторениями Пример 4: Сколько слов длины 6 можно составить из 26 букв латинского алфавита?

Число перестановок без повторений Число перестановок без повторений из n элементов – это число способов, сколькими можно расположить на n различных местах n различных элементов. Число перестановок без повторений находится по формуле:

Задача на рассадки и расстановки В задачах на рассадки и расстановки используется тот факт, что n различных элементов на n различных местах можно расставить n! различными способами

Пример 5: Сколькими способами можно расставить на книжной полке 5 различных книг? В скольких случаях две определенные книги А и В окажутся рядом? Всего вариантов расстановки 5 книг на 5 местах : 5!=120

Замечание: В задаче на рассадки и расстановки число элементов множества А ищут по формуле: где х1 – число способов выбрать нужные места; х2 – число способов расположить на них нужные элементы; х3 – число способов расположить остальные элементы на оставшихся местах.

Рис. 5. Схема расстановки

Число сочетаний без повторений Число сочетаний без повторений из n по k – это число способов, сколькими можно из n различных элементов выбрать k штук без учета порядка. Число сочетаний без повторений находится по формуле:

Свойства числа сочетаний

Урновая задача Урновая задача – это задача, в которой производится выбор сразу нескольких элементов из заданной совокупности. Пример 6: В урне 7 шаров. Из них 3 белых, 4 черных. Наугад выбирают 3 шара. Сколькими способами это можно сделать? В скольких случаях среди них будет: 1) один белый; 2) два белых; 3) все белые.

Схема урновой задачи

Общее число исходов эксперимента найдем по общей формуле

Количество элементов множества А1 найдем по формуле:

Количество элементов множества А2 найдем по формуле:

Количество элементов множества А3 найдем по формуле:

Лекция 4 Соответствия

Соответствия и функции Соответствия и функции

Соответствие G называется всюду (полностью) определенным –  если пр1 G = А (в противном случае – частично определенное соответствие). Соответствие G называется всюду (полностью) определенным –  если пр1 G = А (в противном случае – частично определенное соответствие). Соответствие G называется сюрьективным, если пр2 G = B.

Образ элемента в множестве B при соответствии G – это множество всех элементов которые соответствуют a. Образ элемента в множестве B при соответствии G – это множество всех элементов которые соответствуют a. Прообраз элемента в множестве А при соответствии G – это множество всех которым соответствует b.

Образом множества  Образом множества  называется объединение образов всех элементов С. Прообразом множества   называется объединение прообразов всех элементов D.

Соответствие G называется функциональным (однозначным) соответствием, если образом любого элемента из пр1 G является единственный элемент из пр2 G. Соответствие G называется функциональным (однозначным) соответствием, если образом любого элемента из пр1 G является единственный элемент из пр2 G.

Соответствие G называется инъективным соответствием, если прообразом любого элемента из пр2 G является единственный элемент из пр1 G. Соответствие G называется инъективным соответствием, если прообразом любого элемента из пр2 G является единственный элемент из пр1 G.

Соответствие F является функцией типа Соответствие F является функцией типа если оно функционально (однозначно)

Соответствие G является отображением множества А в множество В, если оно функционально и полностью определено. Соответствие G является отображением множества А в множество В, если оно функционально и полностью определено. Соответствие G является отображением множества А на множество В, если оно сюрьективно.

Соответствие G является взаимно однозначным, если оно: 1) всюду определено; Соответствие G является взаимно однозначным, если оно: 1) всюду определено; 2) сюрьективно; 3) функционально; 4) инъективно.

Пример 1: Определить свойства соответствия G между множествами A и B. A = {a, b, c}, B = {1, 2, 3}. G = {(a, 2), (b, 2), (c,3)}.

Область определения: Область определения: D(G) = пр1G = {a, b, c} = A, значит полностью определено. Область значения: Е(G) = пр2G = {2, 3} ≠ B, значит не сюрьективно.

Образы элементов области определения: Образы элементов области определения: G (a) = {2}; G (b) = {2}; G (c) = {3}. Видим, что есть единственность образа, значит соответствие функционально.

Прообразы элементов области значений: Прообразы элементов области значений: Нет единственности прообраза, значит не инъективно.

Выводы: Соответствие является функцией, так как функционально. 2. Соответствие является отображением, так как полностью определено и функционально. 3. Соответствие является отображением А в В, так как не сюрьективно. 4. Соответствие не является взаимно однозначным, так как не сюьективно и не инъективно.

Пример 2: Определить свойства соответствия G между множествами A и B. A = {a, b, c}, B = {1, 2, 3}. G = {(b, 1), (b, 2), (c,3)}.

Область определения: Область определения: D(G) = пр1G = {a, b} ≠ A, значит не полностью определено Область значения: Е(G) = пр2G = {1, 2, 3} = B, значит сюрьективно

Образы элементов области определения: Образы элементов области определения: G (b) = {1, 2}; G (c) = {3}. Видим, что нет единственности образа, значит соответствие не функционально.

Прообразы элементов области значений: Прообразы элементов области значений: G-1 (1) = {b}, G-1 (2) = {b}, G-1 (3) = {c}  Есть единственность прообраза, значит инъективно.

Выводы: Соответствие не является функцией, так как не функционально. 2. Соответствие является отображением, так как не полностью определено и не функционально. 3. Соответствие не является взаимно однозначным, так как не функционально и не полностью определено.

Преобразованием множества А называется отображение типа Преобразованием множества А называется отображение типа Функция типа называется n-местной функцией

Соответствие называется обратным к если Н таково, что

Если соответствие, обратное к функции Если соответствие, обратное к функции является функциональным, то оно называется функцией, обратной к f,

Пусть дана функция Соответствие является функцией тогда и только тогда, когда f инъективна, и является отображением тогда и только тогда, когда f инъективна и сюрьективна, то есть биективна.

Утверждение: Утверждение: Для функции существует обратная функция тогда и только тогда, когда f является взаимно однозначным соответствием между своей областью определения и областью значений.

Пусть даны функции Пусть даны функции и Функция называется композицией функций f и g, если Часто говорят, что h получена подстановкой f в g.

Для многоместных функций Для многоместных функций и возможны различные варианты подстановки f в g, задающие функции различных типов. Например, при m = 3 и n = 4 функция имеет 6 аргументов и тип

Для множества многоместных Для множества многоместных функций типа возможны любые подстановки функций друг в друга, а также любые переименования аргументов. Например, переименование в из функции четырёх аргументов порождает функцию трёх аргументов:

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

Взаимно однозначные соответствия и мощность множеств Утверждение (о взаимно однозначном соответствии равномощных множеств): Если между конечными множествами А и В существует взаимно однозначное соответствие, то

Взаимно однозначные соответствия и мощность множеств Доказательство: Пусть мощность А больше, чем мощность В.

Взаимно однозначные соответствия и мощность множеств Тогда если выполняется свойство полной определенности, то не выполняется свойство инъективности.

Взаимно однозначные соответствия и мощность множеств Доказательство: 2. Пусть мощность А меньше, чем мощность В.

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

Взаимно однозначные соответствия и мощность множеств Таким образом, получили противоречие, что доказывает истинность сформулированного утверждения.

Этот факт: Этот факт: 1) позволяет установить равенство мощностей двух множеств, не вычисляя мощностей этих множеств; 2) дает возможность вычислить мощность множества, установив его взаимно однозначное соответствие с множеством, мощность которого известна или легко вычисляется.

На понятии взаимно однозначного соответствия строится доказательство многих важных теорем в теории множеств. На понятии взаимно однозначного соответствия строится доказательство многих важных теорем в теории множеств. Теорема о числе подмножеств конечного множества Если мощность конечного множества U равна n, то число его подмножеств равно 2n .

Доказательство: Доказательство: Пусть элементы множества U перенумерованы: U = {a1 , a2 , a3 ,…, an }. Установим взаимно однозначное соответствие между множеством всех подмножеств U – булеаном ℬ (U) и множеством двоичных векторов длины n – Вn.

Доказательство: Доказательство: Двоичный вектор v = (v1 , v2 , v3 ,…, vn ), соответствующий подмножеству М множества U: имеет координату vi = 0, если ai не принадлежит U; vi = 1, если ai принадлежит U.

Например: Например: Элементу булеана Ø соответсвует двоичный вектор (0, 0, …, 0); подмножеству {a1} – (1, 0,…,0); подмножеству {a2} – (0, 1,…,0); подмножеству {a1 , a2 } – (1, 1,…,0); подмножеству U – (1, 1,…,1).

Теорема о числе подмножеств конечного множества Таким образом, между множествами ℬ (U) и Вn установлено взаимно однозначное соответствие. Согласно утверждению, их мощности равны: │ℬ (U)│= │Вn │= 2n .

Лекция 5 Отношения

Определение:

Одноместное отношение – это просто подмножество М. Такие отношения называют признаками: элемент а – обладает признаком R, если и Одноместное отношение – это просто подмножество М. Такие отношения называют признаками: элемент а – обладает признаком R, если и Свойства одноместных отношений это свойства подмножеств М, поэтому для случая n = 1 термин «отношение» употребляется редко.

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

При n = 2 – отношения называются двуместными или «бинарными». При n = 2 – отношения называются двуместными или «бинарными». Если a и b находятся в отношении R, это записывается aRb. Таким образом, бинарное отношение, заданное на множестве М, это любое подмножество

Способы задания Бинарные отношения задаются: 1) Списком; 2)  Матрицей бинарного отношения; 3) Графом.

Задание списком Списком задаются отношения, где М – конечное множество, а R содержит небольшое количество пар. Пример 1: – алфавит из трех букв, отношение R – предшествования букв в алфавите. Тогда R содержит пары:

Пример 2: Отношение R – «быть больше или равно»

Задание графом При задании графом, элементы М сопоставляются одноименным точкам. Точки a и b соединяются стрелками, если aRb. Пример 3: Отношение – быть меньше. Рис. 1. Задание отношения графом

Свойства бинарных отношений Отношение R на М называется рефлексивным, если для любого выполняется Главная диагональ матрицы такого отношения содержит только единицы, граф – петлю в каждой вершине. Пример 4: Отношение «быть делителем», заданной на множестве N. 1 делитель 1; 2 делитель 2; 3 делитель 3; и т. д.

Свойства бинарных отношений Отношение R на М называется антирефлексивным, если для любого выполняется Главная диагональ матрицы такого отношения содержит только нули, граф – не имеет петель. Пример 5: Отношение «быть больше», заданной на множестве N. 1 не больше 1; 2 не больше 2; 3 не больше 3; и т.д.

Свойства бинарных отношений Отношение R на М называется симметричным, если для любой пары из aRb следует bRa (то есть, для любой пары отношение R выполняется в обе стороны или не выполняется вообще). Матрица симметричного отношения – симметрична относительно главной диагонали, у графа все стрелки парные, симметричные.

Пример 6: Отношение «жить в одной комнате в общежитии». Если А живет в одной комнате с В, то и В живет в одной комнате с А. Если С живет в одной комнате с D, то и D живет в одной комнате с C. И так далее.

Свойства бинарных отношений Отношение R на М называется антисимметричным, если для любой пары из того, что одновременно выполняется: aRb и bRa следует что a = b . Матрица антисимметричного отношения не имеет ни одной симметричной 1, у графа все стрелки непарные, направлены лишь в одну строну.

Пример 7: Отношение «быть начальником». Если А начальник В, то В не является начальником А. Если C начальник D, то D не является начальником C. И так далее.

Свойства бинарных отношений Отношение R на М называется транзитивным, если для любых трех из того, что выполняется aRb и одновременно bRc следует, что aRc. Пример 8: Отношение «быть больше», заданной на множестве N. если 3 больше 2 и 2 больше 1, то 3 больше 1; если 5 больше 3 и 3 больше 1, то 5 больше 1; и т.д.

Отношение эквивалентности Отношение R на М называется отношением эквивалентности, если оно Рефлексивно, Симметрично, Транзитивно.

Пример 9: На множестве натуральных чисел задано отношение R – иметь одинаковый остаток от деления на 3. R – рефлексивно, так как каждое число само с собой имеет одинаковый остаток от деления на 3, например 1 и 1, 2 и 2, 3 и 3, и т.д.

Отношение: иметь одинаковый остаток от деления на 3 R – симметрично, так как каждое если число а имеет с числом b одинаковый остаток от деления на 3, то и число b с числом а тоже имеет одинаковый остаток от деления на 3. Например, 1 и 4 имеют одинаковый остаток от деления на 3, то и 4 и 1 тоже имеют одинаковый остаток; 2 и 5 имеют одинаковый остаток от деления на 3, то и 5 и 2 тоже имеют одинаковый остаток; 3 и 12 имеют одинаковый остаток от деления на 3, то и 12 и 3 тоже имеют одинаковый остаток, и т.д.

Отношение: иметь одинаковый остаток от деления на 3 R – транзитивно, так для каждых чисел а , b и с если а с b имеют одинаковый остаток от деления на 3, и b с с имеют одинаковый остаток от деления на 3, то и а с с тоже имеют одинаковый остаток от деления на 3, например 1 и 4 имеют одинаковый остаток от деления на 3, и 4 и 13 тоже имеют одинаковый остаток от деления на 3, тогда 1 и 13 тоже имеют одинаковый остаток.

Отношение: иметь одинаковый остаток от деления на 3 Таким образом, отношение R – рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности.

Разбиение на классы эквивалентности Если отношение R – отношение эквивалентности, то оно разбивает множество, на котором задано, на классы эквивалентности.

Разбиение на классы эквивалентности Для разбиения на классы надо: 1) Выбрать из М произвольный элемент и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему; 2) Затем из оставшихся элементов М выбрать элемент и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему; 3) Делать, пока останутся нераспределенные по классам элементы. Число классов разбиения – индекс разбиения I.

Отношение: иметь одинаковый остаток от деления на 3 Для разбиения на классы надо: 1) Выбрать произвольный элемент 1 и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему: 4, 7, 10, 13, ... ; 2) Затем из оставшихся элементов М выбрать элемент 2 и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему: 5, 8, 11, 14, 17, … ; 3) Затем из оставшихся элементов М выбрать элемент 3 и поместить его в класс , затем поместить в этот класс все элементы, эквивалентные ему: 6, 9, 12, 15, … Индекс разбиения равен 3.

Отношение порядка Отношение R – отношение порядка, если оно антисимметрично и транзитивно.

Отношение порядка Отношение порядка R – отношение строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно.

Отношение порядка Отношение порядка R – отношение нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно.

Отношение порядка Если элементы a и b связаны отношением порядка, то есть aRb или bRa, то a и b сравнимы по отношению порядка R.

Отношение порядка Если любые два элемента a и b сравнимы по отношению порядка R, то R отношение полного или линейного порядка, а М называется полностью упорядоченным.

Пример 10: отношение «быть делителем», задано на N R – рефлексивно, так как каждое число является делителем самого себя: 1 делитель 1; 2 делитель 2; 3 делитель 3, и т.д.

Отношение «быть делителем», задано на N R – антисимметрично, так как если числа разные и a делитель b,то b не является делителем a: если 1 делитель 2 и 2 не делитель 1; если 4 делитель 8, то 8 не делитель 4; если 3 делитель 9, то 9 не делитель 3, и т. д.

Отношение «быть делителем», задано на N R – транзитивно, так как если числа разные и a делитель b и b делитель с, то а тоже является делителем с: если 1 делитель 2 и 2 делитель 4, то 1 – делитель 4; если 4 делитель 8 и 8 делитель 24, то 4 – делитель 24, и т. д.

Отношение «быть делителем», задано на N R – рефлексивно, антисимметрично и транзитивно, значит R – отношение нестрогого порядка.

Отношение «быть делителем», задано на N R – задает неполный порядок, так как можно найти хотя бы одну пару несравнимых элементов, например: 2 и 3; 7 и 11; 4 и 9, и т.д.

Лекция 6 Операции и алгебры

Определение операции N-арная операция на множестве М – это функция типа где n – арность операции. Операция замкнута относительно множества М по определению, то есть операция над элементами множества М, и результат тоже элемент М.

Определение алгебры Алгеброй называется множество М, вместе с заданной на нем совокупностью операций то есть система .

М – основное (несущее) множество (носитель алгебры) алгебры А. М – основное (несущее) множество (носитель алгебры) алгебры А. Тип алгебры – вектор арностей операций. Сигнатура – совокупность операций Σ.

Множество называется замкнутым относительно n-арной операции на М, если Множество называется замкнутым относительно n-арной операции на М, если т. е. если значения на аргументе из М' принадлежат М' .

Если М' замкнуто относительно Если М' замкнуто относительно всех операций алгебры А с носителем М, то система называется подалгеброй алгебры А.

Пример 1: Алгебра – называется полем действительных чисел. Обе операции бинарные, поэтому тип этой алгебры (2,2). Сигнатура Подалгеброй этой алгебры является, например, поле рациональных чисел.

Примеры 2: Пусть Определим на операции:  – «сложение по модулю р», – «умножение по модулю р», следующим образом: и где с и d – остатки от деления на р чисел а + b и а  b соответственно.

Пример 2: Пусть, например, р = 7, тогда и Часто обозначают: a + b = с (mod p) и a  b = d (mod p).

Конечным полем характеристики р называется алгебра Конечным полем характеристики р называется алгебра если р – простое число.

Пример 3: Булеаном U называется множество всех подмножеств множества U (обозначается ℬ(U)). Булева алгебра множеств над U или алгебра Кантора – алгебра (ℬ(U), ) Ее тип (2,2,1), сигнатура

Пример 3: Для любого B' = (ℬ(U'), U, ∩, ¬ ) – является подалгеброй  В.

Пример 3: Множество U={a, b, c, d} тогда основное множество алгебры В содержит 16 элементов. B՛=(ℬ({a, b}),U, ∩, ¬ ). является подалгеброй В.

Свойства бинарных алгебраических операций Операция φ называется ассоциативной, если для любых элементов а, b, с .

Пример 4: 1. Сложение и умножение чисел ассоциативны, что позволяет не ставить скобки в выражениях 2. Возведение в степень – не ассоциативна, так как не равно

Пример 4: 3. Прямое произведение множеств не ассоциативно:

Свойства бинарных алгебраических операций Операция φ называется коммутативной, если для любых элементов a, b

Пример 5: 1. Сложение чисел коммутативно («от перемены мест слагаемых сумма не меняется»): 2. Умножение чисел коммутативно («от перемены мест множителей произведение не меняется»):

Пример 5: 3. Вычитание и деление – некоммутативные операции: 4. Умножение матриц – некоммутативная операция, например:

Свойства бинарных алгебраических операций Операция φ называется дистрибутивной слева относительно операции ψ, если для любых a, b, с

Свойства бинарных алгебраических операций Операция φ называется дистрибутивной справа относительно операции ψ, если для любых a, b, с

Пример 6: 1. Умножение дистрибутивно относительно сложения слева и справа

Пример 6: 2. Возведение в степень дистрибутивно относительно умножения справа.

Пример 6: но не слева, так как

Пример 6: 3. Сложение не дистрибутивно относительно умножения

Лекция 7 Гомоморфизм алгебр

Булевы алгебры Кантора образованные двумя различными множествами U и U΄ одинаковой мощности, изоморфны. Операции у них просто одинаковы, а отображением Г может служить любое взаимно однозначное соответствие между U и U΄ .

Это позволяет получить такие соотношения в алгебре А и автоматически распространить их на все алгебры, изоморфные А. Распространенное в математике выражение «рассматривать с точностью до изоморфизма» означает, что рассматриваются только те свойства объектов, которые сохраняются при изоморфизме, т. е. являются общими для всех изоморфных объектов.   Это позволяет получить такие соотношения в алгебре А и автоматически распространить их на все алгебры, изоморфные А. Распространенное в математике выражение «рассматривать с точностью до изоморфизма» означает, что рассматриваются только те свойства объектов, которые сохраняются при изоморфизме, т. е. являются общими для всех изоморфных объектов.   В частности, изоморфизм сохраняет ассоциативность, коммутативность, дистрибутивность.

Лекция 8 Графы. Определения, способы задания. Виды графов.

Определение графа Пусть V – множество вершин, а Е – множество ребер. Графом G называется пара объектов (V, E) между которыми задано отношение инцидентности: Г : е → (v, w), где вершина v и ребро e инцидентны друг другу, если вершина является для этого ребра концевой точкой.

Определение графа Вершины v' и v" называются смежными, если существует ребро, соединяющее их, т.е. они инцидентны одному и тому же ребру. Ребра e' и e" называются смежными, если они имеют, по крайней мере, одну общую вершину (инцидентны одной вершине).

Определение графа Граф, содержащий направленные ребра (дуги) с началом v' и концом v" , называется ориентированным графом (ор-графом). Для ор-графа Граф, содержащий ненаправленные ребра с конами v' и v" , называется неориентированным графом (н-графом). Для н-графа

Определение графа Рис.1 Неориентированное ребро (a,b) Рис.2 Ориентированное ребро (a,b)

Определение графа Ребро, концевые вершины которого совпадают, называется петлей. Рис.3. Неориентированная петля Рис.4. Ориентированная петля

Определение графа Ребра (дуги), имеющие одинаковые начало и конец, называются параллельными или кратными. Рис.5. Кратные неориентированные ребра

Определение графа Рис. 6. Кратные ориентированные ребра

Определение графа Ребра ор-графа, соединяющие одну и туже пару вершин в разных направлениях называются симметричными или противоположно-направленными. Рис. 7. Симметричные ребра

Определение графа Граф называется конечным, если множество его элементов (вершин и ребер) конечно. Рис. 8. Конечный граф

Определение графа Граф называется бесконечным, если бесконечно множество вершин или множество его ребер. Рис. 9. Граф с бесконечным числом вершин

Определение графа Рис. 10. Граф с бесконечным числом ребер

Определение графа Рис. 11. Бесконечный граф

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

Каноническое соответствие Рис 12. Канонически соответствующие графы

Способы задания Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности. Пусть вершины графа ; ребра графа G. Граф задают: 1) Матрицей инцидентности. 2) Матрицу смежности. 3) Списком ребер. 4) Рисунком.

Матрица инцидентности матрица инцидентности размера (строкам соответствуют ребра, столбцам – вершины графа), в которой для н-графа

Матрица инцидентности для ор-графа

Пример 1: Рис.13 Матрица инцидентности н-графа

Пример 2: Рис. 14. Матрица инцидентности ор-графа

Матрица смежности Матрица смежности размера , столбцам и строкам которой соответствуют вершины графа. Для н-графа равно количеству ребер, связывающих i-ю и j-ю вершины, для ор-графа равно количеству ребер выходящих из i-й и входящих в j-ю вершину.

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

Пример 3: Рис. 15. Матрица смежности н-графа

Пример 4: Рис. 16. Матрица смежности ор-графа

Список ребер Списком ребер можно задать граф без кратных ребер. Ребро представляется парой вершин, инцидентных ему, например е = (v, w). Для н-графа порядок вершин в строке произволен, для ор-графа первым стоит номер вершины–начала ребра.

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

Пример 5: Рис. 17. Список ребер н-графа E = {(a,a), (a,b), (a,c), (b,c)}.

Пример 6: Рис. 18. Список ребер ор-графа E={(a,a), (a,b), (a,c), (с,a), (b,c)}.

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

Планарные графы На рисунке приведен пример не планарного графа Рис. 19. Граф «три дома - три колодца»

Изоморфные графы Графы, отличающиеся только нумерацией вершин, называются изоморфными.

Изоморфные графы Рис.20. Изоморфные графы

Изоморфные графы Графы, отличающиеся только нумерацией вершин, называются изоморфными.

Пустой и полный граф Граф называется пустым, если множество ребер пусто: Рис. 21. Пустой граф

Пустой и полный граф Н-граф называется полным, если любые две вершины связаны ребром: Рис. 22. Полный н-граф

Пустой и полный граф Ор-граф называется полным, если любые две вершины связаны парой симметричных ребер: Рис. 23. Полный ор-граф

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

Двудольный граф Рис. 6. Двудольный граф

Двудольный граф Граф называется полным двудольным, если каждая вершина Связана ребром с каждой вершиной Рис. 24. Полный двудольный граф

Двудольный граф Если а то полный двудольный граф обозначается:

Двудольный граф Рис. 25. Полный двудольный граф

Двудольный граф Рис. 26. Полный двудольный граф На рис. 24 приведен пример На рис. 19 приведен пример

Лекция 9 Локальные степени вершин

Локальные степени вершин н-графа Пусть G = (V, E) – н-граф. Локальной степенью вершины называется число равное числу ребер, инцидентных вершине v. При этом вклад петли в степень вершины равен 2.

Локальные степени вершин н-графа Вектор степеней н-графа G = (V, E) – вектор размерности n, составленный из степеней вершин графа, расположенных по убыванию.

Локальные степени вершин н-графа ρ(a)=5 ρ(b)=2 ρ(c)=3 ρ(d)=0 Вектор степеней ρ = (5, 3, 2, 0) Рис.1 Степени вершин н-графа

Локальные степени вершин н-графа Замечание 1: векторы степеней изоморфных графов одинаковы: ρ = (5,3,2,0) Рис. 2. Граф, изоморфный графу на рис.1

Локальные степени вершин н-графа Замечание 2: Сумма всех локальных степеней вершин н-графа равна удвоенному количеству ребер. - число ребер н-графа.

Локальные степени вершин н-графа Теорема (о числе вершин нечетной степени) Число вершин нечетной степени – четно.

Локальные степени вершин н-графа Доказательство: Сумма в левой части равенства – четна. Если убрать все четные слагаемые, сумма останется четной. Сумма нечетных слагаемых четна, если их четное число.

Локальные степени вершин н-графа Однородным степени k называется н-граф, локальные степени которого одинаковы и равны k. Для однородного графа степени k:

Локальные степени вершин н-графа Локально-конечным называется н-граф, все локальные степени которого конечны. Рис. 3. Локально- конечный, бесконечный однородный граф степени 4.

Локальные степени вершин ор-графа Пусть G = (V, E) – ор-граф. Локальной степенью исхода вершины называется число равное числу ребер, выходящих из вершины v.

Локальные степени вершин ор-графа Локальной степенью захода вершины называется число равное числу ребер, входящих в вершину v.

Локальные степени вершин ор-графа Вектор степеней исхода ор-графа G = (V, E) – вектор размерности n, составленный из степеней исхода вершин графа, расположенных по убыванию.

Локальные степени вершин ор-графа Вектор степеней захода ор-графа – вектор размерности n, составленный из степеней захода вершин графа, расположенных по убыванию.

Локальные степени вершин ор-графа

Локальные степени вершин ор-графа Замечание 3: Векторы степеней исхода и степеней захода изоморфных графов одинаковы.

Локальные степени вершин н-графа Замечание 4: Сумма всех локальных степеней исхода вершин и сумма всех локальных степеней захода ор-графа равна количеству ребер.

Локальные степени вершин ор-графа Однородным степени k называется ор-граф, локальные степени исхода и степени захода которого одинаковы и равны k. Для однородного графа степени k:

Локальные степени вершин ор-графа Локально-конечным называется ор-граф, все локальные степени исхода и захода которого конечны. Рис. 5. Локально- конечный, бесконечный однородный граф степени 2.

Лекция 10 Части графа. Операции над частями графа

Часть графа Пусть G = (V, E) – н-граф. Частью (подграфом) графа G называется граф Н =(V', E' ), где V' V, E' E , причем все ребра множества E' входят в граф Н вместе со своими концами.

Суграф Подграф Н = (V', E' ), называется суграфом, если V' = V. Суграф называется покрывающим, если каждая вершина инцидентна хотя бы одному ребру графа G.

Подграф, порожденным множеством вершин Подграф Н = (V', E' ), называется подграфом, порожденным множеством вершин А V, если V' = А, E' состоит из ребер множества Е, соединяющих вершины множества А.

Звездный граф Подграф Н = (V', E' ), называется звездным графом вершины если V' составляют вершина v и все смежные ей вершины, E' состоит из ребер множества Е, инцидентных вершине v.

Пример покрывающего суграфа G(V,E) Н1 = (V', E' ) Рис.1. Покрывающий суграф

Пример непокрывающего суграфа G(V,E) Н2 = (V', E' ) Рис.2. Непокрывающий суграф

Пример подграфа, порожденного множеством А G(V,E) Н3 = (А, E' ), А={3,4,5,6} Рис.3. Подграф, порожденный множеством А

Пример звездного графа G(V,E) Н4 = (V', E' ) = Z(4) Рис. 4. Звездный граф

Операции над частями графа Суммой подграфов Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется граф Н = (V, E ), такой что Обозначается:

Операции над частями графа Пересечением подграфов Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется граф D = (V, E ), такой что Обозначается:

Операции над частями графа Сумма подграфов Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется прямой по ребрам, если у них нет общих ребер:

Операции над частями графа Сумма подграфов Н1 = (V1, E1 ) и Н2 = (V2, E2 ) называется прямой по вершинам, если у них нет общих вершин:

Операции над частями графа Дополнением подграфа Н = (V1, E1 ) до графа G = (V, E ) называется подграф где множество его ребер:

Операции над частями графа а множество вершин V2 состоит из всех вершин множества V, инцидентных ребрам из Е2 и всех изолированных вершин, не попавших в множество V1.

Пример суммы подграфов Н1 = (V1, E1 ) Н2 = (V2, E2 ) Рис. 5. Сумма подграфов

Пример пересечения подграфов Н1 = (V1, E1 ) Н2 = (V2, E2 ) Рис. 6. Пересечение подграфов

Пример суммы, прямой по ребрам Н1 = (V1, E1 ) Н2 = (V2, E2 ) Рис. 7. Прямая по ребрам сумма подграфов

Пример суммы, прямой по вершинам Н1 = (V1, E1 ) Н2 = (V2, E2 ) Рис. 8. Прямая сумма подграфов

Пример дополнения Н = (V1, E1 ) G(V,E) Рис. 9. Дополнение

Замечание: Подграф и его дополнение являются прямой суммой по ребрам:

Лекция 11 Маршруты. Расстояние в графе

Маршруты Пусть G = (V, E) – н-граф. Маршрутом в графе G называется чередующаяся последовательность вершин и ребер где ребро инцидентно вершинам

Маршруты Вершина - начальная вершина маршрута М, – конечная, – внутренняя вершина, маршрут соединяющий и Дина маршрута – число его ребер.

Маршруты Маршрут М называется маршрутом общего вида, если вершины и ребра повторяются, цепью – если его ребра не повторяются, простой цепью – если его вершины не повторяются.

Маршруты Маршрут М называется циклическим, если начальная и конечная вершина совпадают. Замечание: совпадают, не значит повторяются.

Маршруты Циклический маршрут М называется маршрутом общего вида, если вершины и ребра повторяются, циклом – если его ребра не повторяются, простым циклом – если его вершины не повторяются (кроме начала и конца). .

Пример 1 М1 = (1, 2, 3, 4, 1, 3, 4, 5) – общего вида. М2 = (1, 2, 3, 4, 1, 5) – цепь М3 = (5, 6, 3, 4, 1) – простая цепь. Рис.1. Маршруты

Маршруты М1 =(1, 2, 3, 1, 2, 3, 1) – циклический маршрут общего вида. М1 =(1, 3, 4, 5, 6, 4, 1) – цикл (не простой) М1 =(1, 2, 3, 4, 1) – простой цикл. Рис.2. Циклические маршруты

Расстояния в графе Расстоянием между вершинами a и b называется длина минимальной простой цепи, связывающей их. Расстояние обозначается d(a, b). Аксиомы метрики: 1) d(a, b) = d(b, a); 2) d(a, b) ≥ 0, d(a, b) = 0 ↔ a = b; 3) d(a, b) ≤ d(a, c) + d(c, b)

Расстояния в графе

Расстояния в графе ri – эксцентриситет i-ой вершины – расстояние от этой вершины до наиболее удаленной от нее вершины. ri = max d(vi,vj) по всем j от 1 до n.

Расстояния в графе Диаметр графа G – максимальное расстояние между вершинами графа d(G)= max d(vi,vj) по всем i и j от 1 до n, или d(G)=max ri по всем i от 1 до n.

Расстояния в графе Центр графа G – это вершина, расстояние от которой до наиболее удаленной вершины – минимальное. Что бы найти центр, надо сначала найти радиус графа.

Расстояния в графе Радиус графа G –расстояние от центра графа до наиболее удаленной вершины. r (G) = min ri по всем i от 1 до n.

Расстояния в графе Центр графа G –такая вершина vi, для которой ri = r(G). Замечание: Центр в графе может быть не единственный.

Расстояния в графе В нашем примере центром является вершина 5. Радиус – 1, диаметр – 2.

Расстояния в графе Диаметральные цепи графа G – простые цепи, длина которых равна d(G), соединяющие наиболее удаленные вершины графа.

Расстояния в графе Радиальные цепи графа G – простые цепи, длина которых равна r(G), соединяющие центр и наиболее удаленные от него вершины графа.

Расстояния в графе D1=(1,5,4), D2=(1,3,4), D3=(1,2,4), D4=(2,5,3), D5=(2,1,3), D6=(2,4,3), R1=(5,1), R2=(5,2), R3=(5,3), R4=(5,4). Рис.4. Расстояния

Лекция 12 Связные компоненты графа

Связность Пусть G = (V, E) – н-граф. связными называются вершины a и b если существуют маршрут, связывающий их. Н-граф G называется связным, если все его вершины связны.

Связность Утверждение: отношение связности является отношением эквивалентности. Доказательство: 1.Каждая вершина связана сама с собой маршрутом нулевой длины, значит отношение связности рефлексивно.

Связность 2. Если вершина a связна с b, то и b связна с a. Если a с b связаны маршрутом М(a,b), то b с a связаны маршрутом М(b,a), где ребра и вершины идут в обратном порядке. Значит отношение связности симметрично.

Связность 3. Если вершина a связана маршрутом с b, b связана с с, то и a связана маршрутом с с. Это маршрут, начало которого М(a,b), окончание – M(b,c), вершина b – общая. Значит отношение связности транзитивно.

Связность Отношение рефлексивно, симметрично и транзитивно, значит является отношением эквивалентности. Множество вершин V разбивается отношением связности на классы эквивалентности – подмножества связных вершин.

Связность Связными компонентами графа G называются подграфы, порожденные классами эквивалентности по отношению связности. Замечание: В связном графе одна связная компонента.

Связные компоненты V={a,b,c,d,g}, класс V1 = { a,c,d }, класс V2 = {b,g}. Рис. 1. Связные компоненты

Разделяющие множества Разделяющим множеством н-графа G = (V, E) называется множество ребер, при удалении которых число компонент связности графа увеличивается.

Разделяющие множества Разрезом в н-графе G =(V, E) называется разделяющее множество в котором нет лишних ребер, то есть минимальное разделяющее множество.

Разделяющие множества Мостом или перешейком в н-графе G = (V, E) называется разрез, состоящий из одного ребра.

Рис.2. Разделяющее множество Разделяющее множество: {(1,4), (2,3), (7,8)}; разрез:{(1,4), (2,3)}, (7,8) – лишнее; мост :{(4,5) }.

Шарнир Вершина н-графа G = (V, E) называется шарниром, если удаление этой вершины и всех инцидентных ей ребер приводит к увеличению числа компонент связности графа.

Шарнир Рис.3. Шарнир в графе Шарниром является вершина 4.

Лекция 13 Задачи об обходах

Задача о мостах Кёнигсберга Рис.1. Карта мостов Кенигсберга во времена Эйлера

Граф – схема мостов Части города – вершины, мосты – ребра. Из рисунка видно, что задача, поставленная Эйлером, не выполнима. Рис.2. Граф, соответствующий схеме мостов

Известные головоломки Рис.3. Сабли Магомеда Рис.4. Пентаграмма

Эйлеров граф Эйлеровым циклом в н-графе называется цикл, обходящий все ребра графа (ровно по одному разу). Эйлеров граф – граф, в котором есть эйлеров цикл.

Полуэйлеров граф Эйлеровой цепью в н-графе называется цепь, обходящая все ребра графа (ровно по одному разу). Полуэйлеров граф – граф, в котором есть эйлерова цепь.

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

Теорема (условие полуэйлеровости графа) Для того, чтобы произвольный н-граф был полуэйлеровым, необходимо и достаточно, чтобы: 1) он был связен; 2) локальные степени всех его вершин, кроме двух, были четными. Вершины с нечетными степенями являются началом и концом эйлеровой цепи.

Эйлеров, полуэйлеров, не эйлеров графы Рис.5. Эйлеров граф Рис.6. Полуэйлеров граф Рис.7. Не эйлеров граф

Алгоритм Флери При построении эйлерова цикла начинаем с произвольной вершины и двигаемся в произвольном направлении выполняя два условия: стираем пройденные ребра и изолированные вершины, которые при этом появляются; идем по мосту, только если нет другой возможности.

Рис. 8. Пример построения эйлерова цикла

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

Полугамильтонов граф Гамильтоновой цепью в н-графе называется простая цепь, обходящий все вершины графа (ровно по одному разу). Полугамильтонов граф – граф, в котором есть гамильтонова цикл.

Гамильтонов, полугамильтонов графы Рис.9. Гамильтонов граф Рис.10. Полугамильтонов граф

Задача о кратчайшем пути Пусть G = (V, E) – н-граф. Пусть каждому ребру e графа приписано положительное число – длина ребра L(e). Задача заключается в нахождении маршрута от вершины a к вершине b, наименьшей длины.

Алгоритм Присвоим всем вершинам метки s(v) = +∞, причем метка s(а) = 0. Проверим каждое ребро (vi , vj) на выполнение условия пересчета: s(vj) - s(vi) > L(vi,vj). Если это так, пересчитаем метку конца ребра: s(vj) = s(vi) + L(vi,vj).

Алгоритм Совершаем пересчет меток до тех пор, пока не перестанет выполнятся указанное условие. Метка, которую получила вершина b является длиной искомого маршрута.

Пример 1 Рис. 11. Задача о кратчайшем пути

Задача о кратчайшем пути

Задача о кратчайшем пути

Задача о кратчайшем пути Таким образом, длина кратчайшего пути равна 5. Возвращаясь от вершины 6 переходя к вершинам, инцидентным ребрам, ведущим в вершину 6, доходим о вершины 2. μ = ( 2, 1, 5, 7, 6)

Лекция 14 Деревья

Определения дерева Пусть G =(V, E) – н-граф. Деревом называется связный ациклический граф. Рис. 1. Дерево

Определение леса Лесом называется несвязный ациклический граф. Рис. 2. Лес

Теорема 1 (о деревьях) Граф будет дерево тогда и только тогда, когда любые две его вершины связаны единственной простой цепью. Связность дает наличие такой цепи, ацикличность – ее единственность. Рис. 3. Теорема 1

Терема 2 (о деревьях) Граф с n вершинами будет деревом тогда и только тогда, в нем ровно n-1 ребро. Если ориентировать дерево о выбранной вершины, то в каждую вершину будет входить 1 ребро, а в а0 – 0. Рис. 4. Теорема 2

Вершины максимального типа Дано неориентированное дерево Т. Концевые вершины дерева – вершины, локальная степень которых равна 1. Назовем их вершинами первого типа дерева Т. Рис. 5. Вершины 1 типа

Вершины максимального типа Удалим из дерева Т ребра, инцидентные концевым вершинам – концевые ребра. Получим дерево Т1. Концевые вершины дерева Т1 – Вершины типа 2. Рис. 6. Вершины 2 типа

Вершины максимального типа Удалим из дерева Т1 концевые ребра. Получим дерево Т2. Концевые вершины дерева Т2 – вершины типа 3. Рис. 7. Вершины максимального типа

Вершины максимального типа Утверждение 1: В конечном дереве есть вершины только конечного числа типов. Утверждение 2: Вершин максимального типа k одна или две.

Вершины максимального типа Утверждение 3: Центрами деревьев являются вершины максимального типа k и только они. Все диаметральные цепи проходят через центры. Длина диаметральной цепи равна 2k-1, если центра два и 2k-2, если центр один.

Вершины максимального типа k = 3 , центров два, длина диаметральной цепи 2k-1=5. Рис. 8. Диаметральная цепь

Корень дерева Если дерево не ориентировано, то его можно ориентировать от корня. Корень – это один из центров дерева.

Корень дерева У всех вершин дерева локальные степени захода равны 1, а у корня 0. Вершины, степени исхода которых равны 0 называются листьями. Высотой дерева называется наибольшее расстояние от корня до листа.

Рис. 9 Листья

Бинарное дерево Бинарным деревом называется ориентированное дерево с корнем, где каждая вершина имеет локальную степень исхода, равную 2.

Ветвь дерева Ветвью вершины а в дереве Т с корнем а0 называется подграф, порожденный множеством вершин В(а) состоящим из вершин, связанных с корнем цепь, проходящей через а.

Ветвь

Лекция 15 Характеристические числа графа

Цикломатическое число Цикломатическим числом графа G называется число ребер, которые надо убрать, что бы граф стал ацикличным.

Цикломатическое число 1.1 1.2 Рис.1. Цикломатическое число

Цикломатическое число Цикломатическое число графа G находится по формуле:

Цикломатическое число Замечание 1: Цикломатическое число дерева равно 0. Замечание 2: Цикломатическое число леса равно 0. Замечание 3: Если цикломатическое число графа равно 1, то в графе ровно 1 цикл.

Цикломатическое число Пример 1: Рис. 3. Нахождение цикломатического числа

Цикломатическое число Пример 2: Рис.4. Цикломатическое число несвязного графа

Число внутренней устойчивости Внутренне устойчивым множеством графа G называется множество вершин S, все вершины которого попарно несмежны. Число внутренней устойчивости:

Число внутренней устойчивости

Число внешней устойчивости Внешне устойчивым множеством графа G называется множество вершин Q, таких, что из всех вершин множества Q ведут ребра в вершины множества Q. Число внутренней устойчивости:

Число внешней устойчивости

Хроматическое число Граф G называется h- хроматическим, если его вершины можно раскрасить h различными красками так, чтобы никакие две смежные (различные) вершины не были окрашены в один цвет. Хроматическое число графа – это наименьшее число красок.

Хроматическое число

Хроматическое индекс Граф G называется k-раскрашиваемым, если его ребра можно раскрасить k различными красками так, чтобы никакие два смежные ребра не были окрашены в один цвет. Хроматический индекс графа – это наименьшее число красок.

Хроматическое индекс Согласно теореме Визинга, если максимальная локальная степень вершины графа равна k, то хроматический индекс подчиняется условию:

Хроматическое число

Пример 7: В пунктах Х1, Х2, Х3, Х4, Х5, Х6 могут быть источники излучения. Если источники расположены в пунктах Xi и Xj влияют друг на друга (поражают друг друга), то на графе они соединены ребром (Xi, Xj). Можно ли расположить в каких-либо из данных пунктов 4 или 3 источника, не поражающих друг друга?

Рис.9. Нахождение Рис.9. Нахождение максимального внутренне устойчивого множества. S1={X2, X5}, S2={X1, X4}, S3={X3, X6}, S4={X2, X4, X6}.

Пример 8: Объекты Х1, Х2, … , Х9 расположены так, как показано на графе. Объекты, которые просматриваются друг из друга соединены ребрами. Определить в каких объектах достаточно поставить камеры наблюдения, чтобы они в совокупности просматривали все объекты.

Пример 9: Дана политическая карта континента. Найти минимальное число цветов, чтобы раскрасить карту. Пример 9: Дана политическая карта континента. Найти минимальное число цветов, чтобы раскрасить карту.

Рис.12. Замена стран на вершины, а границ между ними на ребра. Рис.12. Замена стран на вершины, а границ между ними на ребра. Найдем хроматическое число графа. χ(G) = 3.

Рис.13. Раскраска карты в три цвета Рис.13. Раскраска карты в три цвета

Лекция 16 Сети, потоки в сетях

Введение Сети – это графы, которые моделируют реальные транспортные и коммуникационные сети.

Введение Задача о максимальном потоке в сети заключается в том, чтобы подсчитать максимальное количество некоторых объектов, которые могут двигаться от одного конца сети к другому. При этом пропускная способность узлов сети ограничена.

Введение Под объектами могут пониматься - пакеты данных, путешествующих по интернету; - коробки с товарами, которые везут по автомагистрали; и т. д.

Введение Эта задача может использоваться при составлении расписания авиарейсов, распределения задач в суперкомпьютерах, обработке цифровых изображений и расположении последовательности ДНК.

Введение Перемещение объектов могут ограничено пропускной способностью соединений сети или скоростью транспорта на загруженных дорогах.

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

Сети Сетью называется частично ориентированный граф G(V, E) Истоком и стоком (входным и выходным полюсом) называются некоторые отмеченные вершины.

Сети Исток – вершина, локальная степень захода которой равна 0. Сток – вершина, локальная степень исхода которой равна 0.

Сети Если в сети k истоков и m стоков – сеть называется (k,m)- полюсником. Если в сети 1 исток и 1 сток, сеть называется двухполюсной. Далее будем рассматривать только двухполюсные сети.

Сети Пусть s – исток, t – сток, так что любая другая вершина лежит на пути из вершины s в t. Вершины, не являющиеся истоком и стоком называются внутренними вершинами сети.

Сети Разобьем множество вершин V на два подмножества Х и таких, что Множество ребер, реализующих это разбиение назовем разрезом в сети

Сети Ориентированные ребра с началом в Х и концом в называются прямыми. Множество прямых ребер обозначим

Сети Ориентированные ребра с началом в и концом в Х называются обратными. Множество обратных ребер обозначим

Сети Все неориентированные ребра являются прямыми. Их ориентация произвольна, и определяется при задании потока в сети.

Сети Замечание 1: Прямым или обратным ребро будет в зависимости от вида разреза в сети.

Пример 1 Дана частично ориентированная двухполюсная сеть.

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

Поток в сети Потоком в сети S называется пара, составленная из числовой и нечисловой функций ( f ,w): w – ориентация всех неориентированных ребер сети, f =f(e) – функция значений потока на ребрах.

Поток в сети Функция f удовлетворяет условиям: 1) 2) выполняется закон Киргофа: дивергенция любой внутренней вершины сети равна 0.

Поток в сети Дивергенция вершины сети – число находимое по формуле:

Поток в сети Величина потока в сети S – равна дивергенции потока в вершине s (дивергенция истока).

Поток в сети Замечание 2:

Поток в сети Замечание 3: Величина потока в сети есть величина переменная, зависящая от значений функции f(e).

Пример 2 Дана частично ориентированная двухполюсная сеть. Найти величину потока в сети.

с(a)=2; c(b)=3; c(h)=1; c(d)=2; c(q)=1; c(w)=1; c(x)=3; c(y)=2; c(z)=2.

Поток в сети Каждому ребру разреза R ставится в соответствие пропускная способность разреза с(R), равная сумме пропускных способностей всех прямых ребер разреза.

с(a) = 2; c(b) = 3; c(h) = 1; c(d) = 2; c(q) = 1; c(w) = 1; c(x) = 3; c(y) = 2; c(z) = 2. C = c(w) + c(d) = 3 + 1 = 4.

C = c(b) + c(h) + c(x) + c(y) = = 3 + 1 + 3 + 2 = 9.

Поток в сети Теорема Форда-Фалкерсона Максимальная величина потока в сети S равна минимальной пропускной способности среди всех ее разрезов.

Лекция 17 Основы теории кодирования

Основы теории кодирования

Основы теории кодирования Пример 1: Алфавит А={0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Слова: натуральные числа, составленные их цифр. n1=23421, n2= 5600976, и так далее. Двоичный код натуральных: разложение по неотрицательным степеням 2. код числа m1 = 3 – v1 =11; код числа m2 = 4 – v2 =100; код числа m3 = 6 – v3 =110; код числа m4 = 12 – v4 =1100; и так далее.

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

Побуквенное кодирование Пример 4: Алфавит А={a, b, c, d} Двоичные код букв: код буквы a – v1 =0; код буквы b – v2 =11; код буквы c – v3 =01; код буквы d – v4 =011. Тогда слово bc имеет код 1101. Его можно однозначно разделит на коды букв. Тогда слово ab имеет код 011. Его можно декодировать как ab или как d.

Побуквенное кодирование Побуквенный код называется равномерным, если коды букв имеют одинаковую длину. Пример 5: Алфавит А={a, b, c, d} Двоичные код букв: код буквы a – v1 =000; код буквы b – v2 =110; код буквы c – v3 =010; код буквы d – v4 =011.

Побуквенное кодирование Побуквенный код называется префиксным, если ни одно кодовое слово не является началом другого кодового слова. Пример 6: Алфавит А={a, b, c, d} Двоичные код букв: код буквы a – v1 =00; код буквы b – v2 =10; код буквы c – v3 =010; код буквы d – v4 =011.

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

Побуквенное кодирование Утверждение 1: Равномерный код всегда разделим. Утверждение 2: Префиксный код всегда разделим. Утверждение 3: Префиксный код всегда является разделимым, но разделимый код не обязательно является префиксным, т. е. префиксность является достаточным условием разделимости, но не является необходимым условием.

Пример 6: Дано распределение частот для букв алфавита. Построить код Фано. Найти стоимость кода.

Код Фано 1. Упорядочить буквы по не возрастанию частот.

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

Код Фано 1. Упорядочить буквы по не возрастанию частот. 2.Разделить список на две последовательные части так, чтобы разница между суммами частот этих частей была минимальна. 3. Сопоставить частотам первой части символ 0, второй части сопоставить 1.

Код Фано 1. Упорядочить буквы по не возрастанию частот. 2.Разделить список на две последовательные части так, чтобы разница между суммами частот этих частей была минимальна. 3. Сопоставить частотам первой части символ 0, второй части сопоставить 1. 4.С каждой из полученных частей произвести аналогичное деление.

Стоимость кода Стоимость кода V при распределении Р находится по формуле: Здесь длина кодирующего слова частота появления слова

Стоимость кода