Лекция 16

ТЕМА: СООТВЕТСТВИЯ И ОТОБРАЖЕНИЯ

ПЛАН:

1. Соответствие

2. Функция

3. Отображение

4. n –местная функция

5. Обратная функция

6. Свойства отображений

ЛЕКЦИЯ 17

ТЕМА: НЕОРИЕНТИРОВАННЫЙ ГРАФ.

ПЛАН:

1. Основные понятия

2. Смежность, инцидентность. Степени вершин

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

4. Маршруты в неориентированном графе

5. Операции над графами

6. Связность. Компоненты связности

ЛЕКЦИЯ 18

ТЕМА: ЗАДАЧИ НА НЕОРИЕНТИРОВАННЫЕ ГРАФЫ

ПЛАН:

1. Поиск маршрута с минимальным числом ребер

2. Метрические характеристики неориентированного графа

3. Минимальные маршруты в нагруженных графах

4. Задачи на деревьях

5. Цикловой ранг графа. Цикломатическое число

ЛЕКЦИЯ 19

ТЕМА: ЭЙЛЕРОВЫ И ГАМИЛЬТОНОВЫ ЦЕПИ И ЦИКЛЫ

ПЛАН:

1. Эйлеровы цепи и циклы

2. Гамильтоновы циклы и цепи

ЛЕКЦИЯ 20

ТЕМА: ДВУДОЛЬНЫЕ ГРАФЫ

ПЛАН:

1. Двудольный граф. Условие существования двудольного графа

2. Паросочетания . Реберные покрытия

ЛЕКЦИЯ 21

ТЕМА: ПЛОСКИЕ ГРАФЫ

ПЛАН:

1. Задача о плоской укладке графа

2. Основные определения

3. Алгоритм плоской укладки графа

ЛЕКЦИЯ 22

ТЕМА: ОРИЕНТИРОВАННЫЙ ГРАФ

ПЛАН:

7. Основные понятия

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

9. Путь в ориентированном графе

10. Связность. Компоненты связности в орграфе

ЛЕКЦИЯ 23

ТЕМА: ЗАДАЧИ НА ОРИЕНТИРОВАННЫЕ ГРАФЫ

ПЛАН:

1. Поиск путей с минимальным количеством дуг

2. Минимальные пути в нагруженных орграфах

3. Порядковая функция орграфов без контуров

ЛЕКЦИЯ 1

ТЕМА: ОСНОВЫ ТЕОРИИ МНОЖЕСТВ.

ПЛАН:

7. Понятие множества. Способы задания множеств.

8. Отношения между множествами.

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

10. Алгебра множеств.

11. Теорема о количестве подмножеств конечного множества.

12. Формула включений и исключений.

Главная

1. Понятие множества. Способы задания множеств.

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

Множества обозначаются заглавными буквами латинского алфавита , а элементы множества- строчными.

Приведем примеры множеств.

Классы (множества) чисел: N – натуральные числа, Z – целые числа, Q- рациональные числа, R- действительные (вещественные) числа, C – комплексные числа.

Студенты одной группы – множество, элементы которого- студенты, общее свойство – обучение одной специальности.

Множество В – корни уравнения ½ = cosx . Элементы – вещественные числа, общее свойство – обращают данное уравнение в верное равенство.

Если х – элемент множества Х, то говорят: х принадлежит Х и пишут : хХ. Если х не принадлежит Х, то пишут хХ.

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

Конечные и бесконечные множества в свою очередь подразделяются на неупорядоченные и упорядоченные; неупорядоченные бесконечные – на счетные и несчетные.

Рассмотрим два основных способа задания неупорядоченных множеств:

1. перечисление всех его элементов;

2. описание характеристического (общего) свойства его элементов.

Первым способом задаются конечные множества.

Примеры:

А – множество чисел, являющихся делителями числа 20: А = {1, 2, 4, 5, 10, 20}.

В – список группы: В = {Архипов, Белов,…}.

Вторым способом можно задать конечные множества, бесконечные, пустые. Множество элементов. Обладающих характеристическим свойством Р, обозначается:

{x | P(x)} и читается так: множество всех х таких, что х обладает свойством Р(х).

Примеры:

{x | x R, x² – 4 = 0} - это конечное множество и его можно задать перечислением элементов : {2, -2}.

{x | x  R, 2< x < 5 } – бесконечное несчетное множество, а именно, числовой промежуток (2, 5).

{x | x  R, 1= sinx} – бесконечное счетное множество.

{x | x  R, x² + 9 = 0 } – это пустое множество, т.к. ни одно вещественное число не удовлетворяет данному уравнению.