Вопросы к экзамену (ДМ, поток К-2)
|
Полезный файл? Пожалуйста, поставьте "+"
[ Скачать Вопросы к экзамену (ДМ, поток К-2) (8.2 Kb)
]
| 24 Мая 2007, 23:10 |
|
Вопросы к экзамену по ДМ за 2й семестр (поток К-2) |
Вопросы к экзамену по курсу «Дискретная математика (Теория графов)»
1. Понятие метаграфа. Вершины и связи (носитель и сигнатура). Классы (граф, орграф, гиперграф). Смежность и инцидентность в графе.
2. Способы задания графов (орграфов). Изоморфизм. Понятие инварианта графа.
3. Элементы графов: подграф, частичный граф, частичный подграф. Типы графов: полные, пустые и двудольные графы.
4. Операции над графами.
5. Степень вершины. Степень графа. Свойство распределения степеней вершин графа (орграфа).
6. Цепь: составная, сложная и простая цепи. Длина цепи. Расстояние между вершинами в графе и его свойства. Диаметр графа.
7. Связность графа. Вершинная и реберная связность графа. Компонента связности графа. Нахождение компонент связности.
8. Связность в ориентированных графах. Компонента сильной связности. Нахождение компонент сильной связности. Конденсат орграфа.
9. Понятие цикла в графе. Эйлеров и гамильтонов циклы. Эйлеров граф. Гамильтонов граф. Критерий эйлеровости графа.
10. Цикломатика графов: пространство циклов графа, цикломатическая матрица, цикломатический базис, цикломатическое число. Алгоритм порождения циклов.
11. Разделяющее множество. Разрез графа. Коциклический ранг графа. Поиск базисной системы разрезов в графе.
12. Внешняя устойчивость графа. Число внешней устойчивости графа. Положительная и отрицательная внешняя устойчивость орграфов.
13. Внутренняя устойчивость графа. Пустой подграф. Число внутренней устойчивости. Алгоритм порождения пустых подграфов.
14. Полный граф. Полные подграфы. Плотность графа. Алгоритм порождения полных подграфов.
15. Раскраска графа. Хроматическое число. Алгоритм нахождения хроматического числа и раскраски графа.
16. Оценки хроматического числа. Приближенная оценка (раскраска) по Ершову. Значение (оценка) хроматического числа для операций над графами.
17. Рёберные графы. Свойство реберности. Критерий рёберности. Нахождения образа рёберного графа. Род поверхности и род графа. Укладка графа на поверхности. Планарные графы. Критерий планарности.
18. Группа подстановок. Свойства группы. Вычисление произведения подстановок.
19. Автоморфизм и группа автоморфизмов графа.
20. Операции на группах автоморфизмов. Сложение, произведение и композиция, групп автоморфизмов.
|
|
Категория: 1 курс, 2й семестр | Добавил: Ni-Cd
|
| Просмотров: 2498 | Загрузок: 333
| Рейтинг: 0.0/0 |
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ] |
|
| Онлайн |
Онлайн всего: 1 Гостей: 1 Пользователей: 0 |
| |
|
