Дискретная математика вопросы к экзамену

1. Понятие множества. Определение подмножества. Равные множества. Операции пересечения, объединения и дополнения. Примеры.

2. Законы алгебры множеств. С доказательством одного из законов.

3. Последовательности. Декартово произведение двух множеств. Примеры. Декартово произведение n-множеств. Примеры.

4. Определение соответствия. Функциональное, полное, сюръективное, инъективное, биективное (взаимно-однозначное) соответствие. Примеры.

5. Определение отображения. Инъективные, сюръективные, биективные отображения. Примеры.

6. Определение отношения. Свойства бинарных отношений. N-местное отношение на множестве А. Примеры.

7. Отношение эквивалентности. Классы эквивалентности. Фактор-множество. Примеры.

8. Отношение частичного порядка. Частично упорядоченное множество. Диаграммы Хоссе. Примеры.

9. Частично упорядоченное множество. Наименьший, наибольший, максимальные, минимальные элементы частично упорядоченного множества.

10. Частично упорядоченное множество. Верхняя (наименьшая верхняя) и нижняя (наибольшая нижняя) грани подмножества В в множестве А. Примеры.

11. Понятие равномощных множеств. Мощность конечного множества. Примеры.

12. Счетное множество. Свойства счетных множеств. С доказательством одного из свойств.

14. Представление множества в алгебре множеств, порожденной системой образующих. Конституэнта, первичный терм, элементарное пересечение, нормальная форма кантора. Совершенная нормальная форма кантора. Примеры

15. Алгоритм нахождения минимальной формы кантора. Нахождение простых импликант. Таблица Квайна. Покрытие строк столбцами. Ядро покрытия. Пример.

16. Алгоритм нахождения минимальной формы кантора. Нахождение простых импликант. Сокращенная нормальная форма кантора. Таблица Квайна. Пример.

17. Граф ориентированный и не ориентированный – основные определения. Понятие псевдографа, мультиграфа.

18. Пустой, полный, двудольный графы, полный двудольный граф. Плоский и планарный граф. Примеры.

19. Степени вершин. Расстояние между вершинами, диаметр графа. Четные (нечетные) вершины. Число нечетных вершин в графе. Примеры.

20. Степени вершин графа. Связь между суммой степеней всех вершин и количеством ребер. Количество нечетных вершин графа.

21. Изоморфизм графов. Свойства изоморфизма графа. Примеры.

22. Способы задания графа. Примеры.

23. Маршруты, цепи, циклы. Способы записи маршрутов. Простые цепи и циклы. Примеры.

24. Связный граф. Компоненты связности графа. Разделяющее множество, разрез, перешеек. Точки сочленения. Примеры.

25. Ориентированный граф. Понятие слабой и сильной связности ориентированного графа. Примеры.

26. Теорема о возможности выделения простой цепи в маршруте соединяющем две разные вершины.

27. Алгоритм Терри. Первая часть обоснования алгоритма Терри.

28. Признак существования эйлерова цикла в связном графе. Алгоритм выделения эйлерова цикла.

29. Двудольный граф. Признак двудольности графа. Доказательство достаточности.

30. Двудольный граф. Признак двудольности графа. Доказательство необходимости.

31. Доказательство того, что связный граф, имеющий число ребер на единицу меньше чем вершин является деревом.

32. Доказать равносильность двух определений дерева:

а) граф у которого две любые вершины соединяются единственной и притом простой цепью

б) связный граф, не имеющий циклов.

33. Доказательство того, что у дерева число ребер на единицу меньше, чем вершин.

34. Остовное дерево связного графа. Алгоритм выделения остовного дерева связного графа с обоснованием.

35. Определение взвешенного графа. Алгоритм №1 нахождения кратчайшего маршрута во взвешенном графе.

36. Определение взвешенного графа. Алгоритм №2 нахождения кратчайшего маршрута во взвешенном графе.

37. Цикломатика. Базисная система циклов. Цикломатическое число.

38. Алгоритм нахождения базисной системы циклов.

39. Определение взвешенного графа. Алгоритм Дейкстора нахождения кратчайшего маршрута во взвешенном графе.

40. Определение взвешенного графа. Безымянный алгоритм нахождения кратчайшего маршрута во взвешенном графе.