Экзаменационные вопросы по курсу «Дискретная математика»

1. 
   Понятие множества. Мощность множества. Отношения между множествами.
   
2. 
   Операции над множествами.
   
3. 
   Свойства операций над множествами.
   
4. 
   Отношения на множествах. Композиция отношений.
   
5. 
   Отображения множеств.
   
6. 
   Специальные бинарные отношения: рефлексивные, симметричные, транзитивные отношения.
   
7. 
   Специальные бинарные отношения: эквивалентные отношения. Классы эквивалентности и фактор-множество.
   
8. 
   Специальные бинарные отношения: отношения порядка и отношения доминирования. Диаграммы Хассе.
   
9. 
   Понятие нечеткого множества.
   
10. 
    Понятие графа. Виды графов по типу отношений.
    
11. 
    Понятие псевдографа, мультиграфа и остова.
    
12. 
    Полные, насыщенные, регулярные и взвешенные графы.
    
13. 
    Смежность в графе.
    
14. 
    Связность в неографе. Понятие цепи и простой цепи. Компоненты связности, мост в графе.
    
15. 
    Связность в орграфе. Путь и простой путь, полупуть и простой полупуть в орграфе.
    
16. 
    Достижимость и контрдостижимость в орграфе.
    
17. 
    Связные орграфы: сильные, односторонние и слабые.
    
18. 
    Минимальные маршруты в графе.
    
19. 
    Волновой метод поиска минимального маршрута в связном графе.
    
20. 
    Матричные способы представления графа: матрицы смежности, связности и инцидентности. Свойства матриц.
    
21. 
    Аналитические способы представления графа. Методы поиска в глубину и ширину.
    
22. 
    Расстояния в графе. Диаметр, радиус и центр графа.
    
23. 
    Операции над графами: объединение и пересечение двух графов.
    
24. 
    Операции над графами: вычитание и произведение двух графов.
    
25. 
    Операции над графами: стягивание ребер и расщепление вершин.
    
26. 
    Циклы и простые циклы в неографе.
    
27. 
    Контуры и простые контуры в орграфе. Понятие полуконтура.
    
28. 
    Независимые циклы в графе.
    
29. 
    Цикл Эйлера. Граф Эйлера и его свойства.
    
30. 
    Цикл и цепь Гамильтона. Граф Гамильтона и его свойства.
    
31. 
    Метод Робертса и Флореса для поиска циклов Гамильтона в графе.
    
32. 
    Задача коммивояжера. Метод ветвей и границ для решения задачи коммивояжера.
    
33. 
    Части графа: подграф и суграф. Граф-дополнение.
    
34. 
    Дерево, лес. Основные свойства деревьев.
    
35. 
    Остовное дерево графа. Теорема Прима о минимальном остовном дереве (МОД).
    
36. 
    Метод Прима для построения МОД в связном графе.
    
37. 
    Метод Краскала для построения МОД в связном графе.
    
38. 
    Понятие корневого ориентированного дерева. Глубина, высота и уровень вершины в корневом дереве.
    
39. 
    Двоичное дерево. Полное двоичное дерево. Способы представления двоичных деревьев.
    
40. 
    Метод Хаффмана для оптимального префиксного кодирования.
    
41. 
    Двудольный граф. Теорема Кенига (критерий двудольности графа).
    
42. 
    Изоморфизм и гомеоморфизм графов. Необходимые условия изоморфизма.
    
43. 
    Метод установления изоморфизма двух графов на основе обобщенных локальных характеристик вершин.
    
44. 
    Цикломатическое число графа. Теорема об основном свойстве цикломатического числа.
    
45. 
    Хроматическое число графа. Оценка нижней границы хроматического числа для связного графа.
    
46. 
    Метод раскраски графа на основе метода Магу.
    
47. 
    Эвристические подходы к вершинной раскраске графа.
    
48. 
    Число внутренней устойчивости графа. Связь между числом внутренней устойчивости и хроматическим числом графа. Оценки верхней границы числа внутренней устойчивости.
    
49. 
    Метод Магу-Вейсмана для поиска наибольшего ВУМ в графе.
    
50. 
    Число внешней устойчивости графа. Минимальная и наименьшая опора в графе. Понятие ядра графа.
    
51. 
    Кликовое число графа. Связь задач поиска ПП и ВУМ в графе. Кликовое покрытие графа.
    
52. 
    Метод поиска НПП на основе операции разборки графа.
    
53. 
    Число паросочетания и число реберного покрытия графа.
    
54. 
    Плоские и планарные графа. Грани плоского графа.
    
55. 
    Свойства плоских укладок.
    
56. 
    Теорема Эйлера для плоского графа. Следствия теоремы.
    
57. 
    Теорема Понтрягина-Куратовского (критерий планарности графа).
    
58. 
    Понятие гиперграфа. Представление гиперграфа в виде графа Кенига.
    
59. 
    Инцидентность и смежность в гиперграфе. Однородные гиперграфы. Подгиперграфы.
    
60. 
    Двойственность гиперграфов.
    
61. 
    Цепи и циклы в гиперграфе. Связность гиперграфа.
    
62. 
    Цикломатический ранг гиперграфа.
    
63. 
    Транспортная задача. Поиск опорного плана методом «северо-западного угла».
    
64. 
    Транспортная задача. Поиск оптимального плана методом потенциалов.
    
65. 
    Понятие сети Петри (СП). Маркированная СП.
    
66. 
    Структура СП. Входная и выходная функция СП.
    
67. 
    Классификация СП по структуре.
    
68. 
    Метод преобразования произвольной СП в ординарную СП.
    
69. 
    Автоматная СП и синхрограф.
    
70. 
    Функционирование СП.
    
71. 
    Правила срабатывания переходов в СП.
    
72. 
    Множество достижимости для СП.
    
73. 
    Классификация СП по динамическим свойствам: безопасная и ограниченная СП.
    
74. 
    Классификация СП по динамическим свойствам: сохраняющаяся, строго сохраняющаяся и живая СП.
    
75. 
    Динамические свойства автоматной СП.
    
76. 
    Динамические свойства синхрографа.
    
77. 
    Покрывающее дерево СП, расширенная маркировка.
    
78. 
    Метод построения покрывающего дерева СП.
    
79. 
    Методы анализа динамических свойств СП на основе покрывающего дерева.
    

Составитель: зав. кафедрой КОТ, д.т.н. Л.С. Лисицына