- •Введение
- •1. Теория множеств
- •1.1. Основные понятия
- •1.2. Операции над множествами
- •1.3. Алгебраические свойства операций над множествами
- •1.4. Нечёткие множества
- •2. Элементы комбинаторики
- •2.1. Основные правила комбинаторики
- •2.2. Выборки элементов без повторений
- •2.3. Выборки элементов с повторениями
- •2.4. Объединение комбинаторных конфигураций
- •2.5. Бином Ньютона
- •3. Отношения на множествах
- •3.1. Декартово произведение множеств
- •3.2. Булев куб и его свойства
- •3.3. Понятие отношения
- •3.4. Операции над отношениями
- •3.5. Свойства отношений на множестве
- •3.6. Отношения эквивалентности, толерантности и порядка
- •3.7. Нечеткие отношения
- •3.8. Понятие отображения
- •3.9. Алгебраическая операция
- •3.10. Общие сведения об алгебраических системах
- •4 Булевы функции
- •4.1. Основные определения и операции над высказываниями
- •4.2. Типы пф.
- •4.3. Равносильность формул
- •4.4. Дизъюнктивные и конъюнктивные нормальные формы
- •4.5 Алгоритм приведения пф к нормальным формам
- •4.6 Аналитический способ приведения к сднф
- •4.7. Табличный способ приведения к сднф
- •4.8. Табличный способ приведения к скнф
- •4.9. Логическое следствие
- •4.10. Алгоритм проверки правильности рассуждений
- •4.11. Алгоритм определения всех логических следствий из данных посылок
- •4.12. Алгоритм определения всех посылок, логическим следствием которых является данная формула
- •4.13. Полнота систем булевых функций
- •4.14. Полином Жегалкина
- •4.15. Замкнутость
- •4.16. Теорема Поста
- •4.17. Нечеткая логика
- •5. Многозначные функции
- •5.1. Функции и формулы k-значной логики
- •5.2. Полнота и замкнутость функций k-значной логики
- •5.3. Особенности k – значной логики
- •6.. Основные понятия теории графов.
- •6.1. Задачи теории графов.
- •6.2. Основные определения.
- •6.3. Степени вершин графа.
- •6.4. Изоморфизм графов.
- •6.5. Матричные способы задания графов.
- •6.6. Основные операции над графами.
- •6.7. Маршруты в графах
- •6.8. Связность в графах.
- •Связность и матрица смежности графа.
- •6.9. Матрица взаимодостижимости.
- •6.10. Деревья Свободные деревья.
- •Ориентированные, упорядоченные и бинарные деревья.
- •6.11. Эйлеровы графы.
- •6.12 Гамильтоновы графы.
- •6.13. Планарные графы.
- •6.14. Потоки в сетях. Основные определения.
- •Теорема Форда и Фалкерсона.
- •Алгоритм построения максимального потока в сети.
- •7. Конечные автоматы
- •7.1. Понятие конечного автомата Общие сведения о конечных автоматах
- •7.2. Абстрактное определение конечного автомата
- •7.3. Автоматная функция и её моделирование Понятие ограниченно детерминированной функции
- •Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •7.4. Эксперименты с автоматами
- •8. Рекуррентные уравнения
- •8.1. Определение рекуррентного уравнения/ Решение линейного однородного рекуррентного уравнения
- •8.2. Решение линейного неоднородного рекуррентного уравнения
- •8.3. Решение рекуррентного уравнения для чисел Фибоначчи
- •Заключение
- •Библиографический список
- •Оглавление
- •1.Теория множеств 5
- •2 Элементы комбинаторики 14
- •3 Отношения на множествах 22
- •4. Булевы функции 42
- •5. Многозначные функции 64
- •6. Основные понятия теории графов 70
- •7. Конечные автоматы 106
- •8. Рекуррентные уравнения 120
- •394026 Воронеж, Московский просп., 14
6.3. Степени вершин графа.
Степенью (валентностью) (обозначение d(v) или deg(v)) вершины v простого графа G называется число ребер или дуг инцидентных данной вершине v. При подсчете валентности вершин псевдографа следует учитывать каждую петлю дважды.
Если степени всех вершин н-графа равны k, то граф называется регулярным (однородным) степени k. Если степень вершины равна 0, то она является изолированной. Если степень вершины равна 1, то вершина называется концевой (висячей, тупиковой).
Для орграфа число дуг исходящих из вершины v называется полустепенью исхода (v), а входящих – полустепенью захода (v), При этом справедливо соотношение d(v)= (v)+ (v).
Теорема Эйлера: Сумма степеней вершин графа равна удвоенному количеству ребер, т.е. , или , где n – число вершин; m – число ребер (дуг). Данное утверждение доказывается тем, что при подсчете суммы степеней вершин каждое ребро учитывается два раза - для одного конца ребра и для другого.
6.4. Изоморфизм графов.
Граф называется помеченным (или перенумерованным), если его вершины отличаются друг от друга какими либо пометками (номерами). Граф считается полностью заданным в строгом смысле, если нумерация его вершин и ребер фиксирована. При этом графы G1 и G2 называются равными (обозначение G1 = G2), ,если их множества вершин и ребер совпадают. Два графа или псевдографа G1=(V1,E1) и G2=(V2,E2) называются изоморфными (обозначение ), если существуют два взаимно однозначных отображения: 1) и 2) такие, что для любых двух вершин в графе справедливо соотношение .
Два простых графа (без петель и кратных ребер) G1 и G2 оказываются изоморфными, если существуют взаимно однозначное отображение , такое что . Таким образом, изоморфными являются графы, которые отличаются только нумерацией вершин и ребер. Изоморфизм графов представляет собой отношение эквивалентности, поскольку оно обладает свойствами:
Рефлексивности - , причем биекция представляет собой тождественную функцию.
Симметричности. Если с биекцией , то с биекцией .
Транзитивности. Если с биекцией ,а с биекцией , то с биекцией .
6.5. Матричные способы задания графов.
Матрицей смежности графа G=(V,E) с n вершинами называется квадратная матрица А порядка n, элементы которой определяются следующим образом:
а) в случае неориентированного графа
б) для ориентированного графа
в ) в мультиграфе = k, где k – кратность ребра (vi vj).
Рис. 19
П ример. Для графа изображенного на рисунке матрица смежности имеет вид
Свойства матрицы смежности: Матрица смежности неориентированного графа является симметричной относительно главной диагонали. Диагональные элементы этой матрицы указывают на наличие петель в соответствующем графе.
Сумма элементов матрицы А неориентированного графа по i-ой строке (или i-му столбцу) равна d(vi). Для ориентированного графа сумма элементов матрицы А по i-ой строке равна d (vi), а по j-му столбцу d ( vj).
Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одновременной перестановкой строк и столбцов (i, j строк и i, j столбцов).
Объём памяти для матрицы смежности – О(n2)
Матрицей инцидентности графа G=(V, E) с n вершинами и m ребрами называется матрица В размера n×m, элементы которой определяются следующим образом:
а) для неориентированного графа
б) для ориентированного графа
Н апример, для графа предыдущего примера:
З аметим, что мультиграфы изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга некоторыми перестановками строк или столбцов.
Объём памяти для матрицы инцидентности – О(nm)