Примерный перечень вопросов для подготовки к экзамену. 1. Определение и обозначения множеств

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. Лес, дерево. Количество ребер в дереве с n вершинами

28. Свойства деревьев.

29. Количество помеченных деревьев с n вершинами. Код Прюфера.

30. Стягивающее дерево.

31. Алгоритмы построения стягивающего дерева наименьшего веса.

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

33. Нахождение расстояния между всеми парами вершин орграфа с помощью алгоритма Флойда.

34. Задачи сетевого планирования и управления.

Не нашли, что искали? Воспользуйтесь поиском: