Дискретная математика МК2 / терия модуль 2

Теоретические вопросы по курсу дискретная математика. Модуль 2

1. Способы задания графа при программировании

2. Степень вершины графа. Однородные графы.

3. Маршрут на графе. Типы маршрутов.

4. Связный граф. Компонента связности. Мост, точка сочленения.

5. Эйлеров цикл, путь в графе. Условия существования.

6. Гамильтонов цикл, путь в графе. Условия существования.

7. Расстояние между вершинами. Свойства расстояний. Метрика.

8. Радиус вершины и радиус графа. Диаметр графа.

9. Хроматическое число и хроматический класс графа.

10. Грани графа. Характеристика поверхности Эйлера.

11. Дерево. Цикломатическое число графа.

12. Бинарное дерево. Двоичное дерево поиска.

13. Полный граф. Граф-дополнение.

14. Изоморфные графы. Пример.

15. Ориентированный граф. Исток. Сток.

16. Достижимость. Матрица достижимости и контрдостижимости.

17. Остов графа. Минимальный остов .

18. Четный граф. Применение.

19. Кратные ребра. Изолированные вершины. Петли.

20. Сеть. Потоки с сетях. Максимальная пропускная способность сети.

21. Обход вершин графа.

22. Плоские и планарные графы. Характеристика Эйлера таких графов.

Структура билета!

1. Теоретический вопрос

2. Найти зависимость производящих функций f и f1.

3. Ручной расчет к-л алгоритма на графе

4. закодировать строку кодом Хаффмана или кодом Шеннона-Фано и определить эффективность кодирования