Билеты по Дискретной математике «Теория Графов»
| Вид материала | Документы |
- Задание графов соответствием 9 > Матричное представление графов 10 Вопросы применения, 230.14kb.
- Спецкурс проходит по вторникам с 18: 30 до 19: 50 в ауд. 301 лк. Первая лекция состоится, 20.89kb.
- Задача является np-полной для кубических планарных графов, реберных графов, ориентированных, 39.45kb.
- 1. Элементы теории графов Введение в теорию графов: основные понятия и определения., 32.17kb.
- «Теория графов», 114.81kb.
- Программа вступительного экзамена в аспирантуру по специальностям 05. 13. 05 - "Элементы, 88.59kb.
- Математика и компьютерные науки, 120.83kb.
- Темы лекций по высшей математике элементы теории вероятностей. Относительная частота, 8.28kb.
- Математика и компьютерные науки, 102.47kb.
- Спецкурс «Теория графов» пм 4 курс История возникновения и развития теории графов., 13.97kb.
Билеты по Дискретной математике «Теория Графов».
- Понятие графа (орграфа). Смежность и инцидентность в графе. Классы (типы) графов.
- Подграф. Частичный граф, подграф. Полные, пустые и двудольные подграфы.
- Способы задания графов (орграфов). Изоморфизм графов.
- Операции над графами.
- Степень вершины, графа. Свойства распределения вершин графа.
- Цепь: составная, сложная, простая. Длина цепи. Метрика. Расстояние между вершинами в графе. Диаметр в графе.
- Связность графа. Вершинная и реберная связность. Компонента связности графа. Нахождение компоненты связности.
- Связность в орграфах. Компонента сильной связности (КСС). Нахождение КСС. Конденсат графа.
- Циклы в графе. Эйлеров и Гамильтонов циклы / графы. Критерий эйлеровости графа.
- Пространство циклов графа. Цикломатическая матрица. Цикломатический базис. Цикломатическое число. Алгоритм порождения циклов.
- Разделяющее множество. Разрез графа. Ко-циклический ранг графа. Поиск базисной системы разрезов графа.
- Внутренняя устойчивость графа. Пустой подграф. Число внутренней устойчивости. Алгоритм порождения пустых подграфов.
- Полный граф. Полные подграфы. Плотность графа. Алгоритм порождения полных подграфов.
- Внешняя устойчивость графа. Положительная и отрицательная внешняя устойчивость орграфа.
- Раскраска графа. Хроматическое число. Алгоритм нахождения хроматического числа и раскраски графа.
- Оценки хроматического числа. Приближенная раскраска (оценка по Ершову). Значение (оценка) хроматического числа для операций над графами.
- Реберные графы. Критерий свойства реберности. Нахождение образа реберного графа.
- Группа подстановок. Свойства группы. Вычисление произведения подстановок.
- Автоморфизм и группа автоморфизмов графа.