Вопросы к экзамену по дискретной математике

1.  Основные определения теории графов. Способы задания графа.

2.  Матрицы инциденций, смежности и их свойства.

3.  Матрицы достижимости и расстояний.

4.  Операции над графами.

5.  Пути. Маршруты. Связность в неориентированном и ориентированном графе.

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.  Обратимость автоматов и автоматы БПИ.