ЭУМК по Дискретной математике new 2 ВВ Голенков, НА Гулякина, БГУИР 2010 (Мет пособие) / EUMK_po_Diskretnoy_matematike_new_2
Тема 8. Основные понятия теории графов
Понятие графа. Ориентированный, неориентированный граф. Пустой граф. Нуль-граф. Понятие инцидентности. Смежность вершин и ребер. Висячая вершина. Изолированная вершина. Способы задания графа.
Р.Л.: [1]; [3]; [5]; [7]; [19].
Yandex.RTB R-A-252273-3
Содержание
- Общие сведения Сведения об эумк
- Методические рекомендации по изучению дисциплины
- Рабочая учебная программа
- Протокол согласования учебной программы по изучаемой учебной дисциплине с другими дисциплинами специальности
- Пояснительная записка
- Содержание дисциплины
- 1. Наименование тем, их содержание
- Тема 5. Отношения на множествах
- Тема 6. Соответствие и функции
- Тема 7. Мультимножества
- Раздел 2. Теория графов
- Тема 8. Основные понятия теории графов
- Тема 9. Графы
- Тема 10. Орграфы
- 3. Литература
- Теоретический раздел
- 1.2 Способы задания множеств
- Глава 2. Операции над множествами
- 2.1 Сравнение множеств
- 2.2 Операции над множествами
- 2.3 Свойства операций над множествами
- 2.4 Примеры доказательств тождеств с множествами
- 2.5 Булеан
- Глава 3. Упорядоченные множества
- 3.1 Кортеж
- 3.2 Операция проекции
- 3.3 Декартово произведение множеств
- 3.4 Графики
- Глава 4. Отношения на множествах
- 4.1 Понятие отношения
- 4.2 Свойства отношений
- 4.3 Операции над отношениями
- 4.4 Отношение эквивалентности
- 4.5 Отношение порядка
- Глава 5. Соответствия и функции
- 5.1 Основные понятия соответствия
- 5.2 Операции над соответствиями
- 5.3 Свойства соответствий
- 5.4 Отображения множеств
- 5.5 Функция
- Глава 6. Мультимножества
- 6.1 Понятие мультимножества
- 6.2 Операции над мультимножествами
- Раздел 2. Теория графов Глава 1. Основные понятия
- 1.1 Определения и примеры
- 1.2 Способы задания графов
- Глава 2. Графы
- 2.1 Типы графов
- 2.2 Подграфы
- 2.3 Сильно связные графы и компоненты графа
- 2.4 Маршруты, цепи, пути и циклы
- 2.5 Связность и компоненты графа
- 2.6 Операции над графами
- 2.7 Матрица смежности и инцидентности
- Глава 3. Орграфы
- 3.1 Определения и примеры
- 3.2 Орграфы и матрицы
- 3.3 Ориентированные эйлеровы графы
- Глава 4. Ориентированные ациклические графы и деревья
- 4.1 Ориентированные ациклические графы
- 4.2 Деревья
- Глава 5. Планарность и двойственность
- 5.1 Планарные графы
- 5.2 Точки сочленения, мосты и блоки
- 5.3 Двойственные графы
- Глава 6. Поиск на графах
- 6.1 Исследование лабиринта
- 6.2 Поиск в глубину
- 6.3 Поиск в ширину
- 6.4 Нахождение кратчайшего пути (Алгоритм Дейкстры)
- Практический раздел Контрольные работы Указания по выбору варианта
- Варианты контрольных заданий
- Контрольная работа № 1 Теоретическая часть (вопросы)
- Практическая часть Контрольное задание №1.
- Контрольное задание №2.
- Контрольное задание №3.
- Контрольное задание №4.
- Контрольное задание №5.
- Контрольное задание №6.
- Теоретическая часть (вопросы)
- Контрольное задание №1.
- Контрольное задание №2.
- Контрольное задание №3.