Diskretnaya_matematika_1_semestr
35. Способы задания графов
1.Списком рёбер
2 .Матрицей смежности
gij= 1(i,j)ЄU
0, в противном случае
3.Матрица инцидентности
(Рёбра нумеруються, строки соответствуют номерам рёбер)
g ij= 1, вершина i и ребро j инцидентно графе
0, в противном случае
Содержание
- Множества. Основные понятия.
- Операции над множествами и их свойства.
- Декартово произведение. Разбиение множеств.
- Алгебра множеств
- Отношение. Бинарное отношение
- Алгебра бинарных отношений
- Отображение. Виды отображений
- Отношение порядка. Изоморфизм упорядоченных множеств.
- Алгебраические системы. Изоморфизм алгебраических систем.
- Функции алгебры логики.
- Формулы. Реализация функций формулами.
- Эквивалентность формул. Свойства элементарных булевых функций.
- Двойственные функции. Принцип двойственности
- Разложение булевых функций по переменным. Сднф.
- Разложение булевых функций по переменным. Скнф.
- Полнота и замкнутость.
- Представление булевых функций в виде полинома Жегалкина. Теорема Жегалкина.
- Классы т0, т1.
- Класс s.
- Класс м.
- Класс l
- Задача минимизации булевых функций.
- Задача минимизации булевых функций в геометрической постановке.
- Сокращенные днф.
- Тупиковые днф и решение задачи минимизации.
- Графы. Основные понятия.
- Орграфы. Основные понятия.
- Маршруты. Цепи. Циклы. Связность.
- Операции над графами
- 30.Двудольные графы.
- 31. Планарные графы.
- 32. Эйлеровы и гамильтоновы графы
- 33. Дерево. Лес
- 34. Графическое разбиение.
- 35. Способы задания графов
- 36. Типы связности орграфов
- 38. Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала.
- 39. Задача о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона.
- 40. Теорема Форда-Фалкерсона