Тема 6. Соответствие и функции

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

Р.Л.: [1]; [2]; [3]; [4]; [6]; [11]; [14]; [16]; [19].

Тема 7. Мультимножества

Понятие мультимножества. Компонента мультимножества. Функция кратности. Порождающее множество (домен). Мощность мультимножества. Высота (пиковое значение) мультимножества. Подмультимножество. Надмультимножество. Операции над мультимножествами.

Р.Л.: [1]; [2]; [3]; [4]; [6]; [11]; [14]; [16]; [19].

Раздел 2. Теория графов

Тема 8. Основные понятия теории графов

Понятие графа. Ориентированный, неориентированный граф. Пустой граф. Нуль-граф. Понятие инцидентности. Смежность вершин и ребер. Висячая вершина. Изолированная вершина. Способы задания графа.

Р.Л.: [1]; [3]; [5]; [7]; [19].

Тема 9. Графы

Типы графов. Полный граф. Симметрический, антисимметрический граф. Полный граф. Связный граф. Ориентированное дерево. Планарный/непланарный граф. Ориентированный/неориентированный граф. Двудольный граф. Подграфы. Остов подграф. Собственный подграф. Правильный подграф. Виды подграфов. Порожденный подграф. Сильно связанные графы и компоненты графа. Маршрут в графе. Открытый маршрут. Замкнутый маршрут. Цепь. Открытая цепь. Замкнутая цепь. Длина пути. Длина цикла. Свойства путей и циклов. Связность и компоненты графа. Операции над графами. Матрица смежности и инцидентности.

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18], [19].

Тема 10. Орграфы

Понятие орграфа. Основание орграфа. Вершина орграфа. Изоморфные орграфы. Матрица смежности орграфа. Ориентированный маршрут в орграфе. Орцепь. Орциклы. Сильный орграф. Слабый орграф. Односторонний орграф. Несвязный орграф. Порожденный орграф. Матрицы орграфов. Ориентированные эйлеровы графы.

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18], [19].

Тема 11. Ориентированные ациклические графы и деревья

Понятие ациклических графов. Понятие ориентированных ациклических графов. Понятие дерева. Лес. Остово дерево. Коциклический ранг графа. Остов лес. Фундаментальная система циклов.

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18], [19].

Тема 12. Планарность и двойственность

Понятие планарного графа. Графы Куратовского. Точки сочленения, мосты, блоки. Двойственные графы. Лемма. Абстрактно двойственные графы.

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18], [19].