Реферат: Билеты по Дискретной математике «Теория Графов»


Билеты по Дискретной математике «Теория Графов».


Понятие графа (орграфа). Смежность и инцидентность в графе. Классы (типы) графов.

Подграф. Частичный граф, подграф. Полные, пустые и двудольные подграфы.

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

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

Степень вершины, графа. Свойства распределения вершин графа.

Цепь: составная, сложная, простая. Длина цепи. Метрика. Расстояние между вершинами в графе. Диаметр в графе.

Связность графа. Вершинная и реберная связность. Компонента связности графа. Нахождение компоненты связности.

Связность в орграфах. Компонента сильной связности (КСС). Нахождение КСС. Конденсат графа.

Циклы в графе. Эйлеров и Гамильтонов циклы / графы. Критерий эйлеровости графа.

Пространство циклов графа. Цикломатическая матрица. Цикломатический базис. Цикломатическое число. Алгоритм порождения циклов.

Разделяющее множество. Разрез графа. Ко-циклический ранг графа. Поиск базисной системы разрезов графа.

Внутренняя устойчивость графа. Пустой подграф. Число внутренней устойчивости. Алгоритм порождения пустых подграфов.

Полный граф. Полные подграфы. Плотность графа. Алгоритм порождения полных подграфов.

Внешняя устойчивость графа. Положительная и отрицательная внешняя устойчивость орграфа.

Раскраска графа. Хроматическое число. Алгоритм нахождения хроматического числа и раскраски графа.

Оценки хроматического числа. Приближенная раскраска (оценка по Ершову). Значение (оценка) хроматического числа для операций над графами.

Реберные графы. Критерий свойства реберности. Нахождение образа реберного графа.

Группа подстановок. Свойства группы. Вычисление произведения подстановок.

Автоморфизм и группа автоморфизмов графа.
еще рефераты
Еще работы по разное