ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Понятие графа
Графом называют совокупность двух конечных множеств м множество рёбер (дуг) и равное {u1..un}, состоящего из пар элементов (xi, xj) множество Х.
Классификация графов
Графы делятся на связные и несвязные. В связном графе между любой парой вершин существует как минимум один путь. В несвязном графе существует хотя бы одна вершина, не связанная с другими. Графы также подразделяются на ориентированные, неориентированные и смешанные.
Способы задания графов
Аналитический способ - указание множества вершин и множества ребер (дуг)
Геометрический способ (графический) - посредством графического изображения
Матрицей смежности — квадратная матрица, размер которой определяется числом вершин в графе.
Матрицей идентичности — прямоугольная матрица, число строк которой равно числу вершин, а число столбцов – числу дуг (ребер) графа.
Построение матричной смежности
Построение матрицы инцидентности
Метрические характеристики (расстояние, эксцентриситет, диаметр, радиус, центр, передаточное число, медиана)
Расстояние - длина кратчайшего маршрута (он же является простой цепью) между вершинами u и v и обозначается через d(u, v)Эксцентриситет – наибольшее расстояние от вершины u до других вершин графа e(u) = max d(u,v)Диаметр - максимальный из эксцентриситетов вершин графа d(G) = max e(u)Радиус - минимальный из эксцентриситетов вершин связного графа r(G) = min e(u)Центр – множество вершин графа G с наименьшим эксцентриситетом Передаточное число - Медиана – вершина, у которой передаточное число минимально
Маршруты, цепи, циклы в графах
Деревья, остовы графа
Дерево - связанный ациклический граф, имеющий не менее двух вершин. Остов - дерево графа «G», содержащее все вершины дерева этого графа.
Алгоритмы построения остовов (в глубину и в ширину)
Эйлеровцикл – цикл, проходящий по одному разу через каждое ребро графа. Связный граф называется эйлеровым, если он содержит эйлеровый цикл и полуэйлеровым, если в нем существует незамкнутая эйлеровая цепь.(По теореме Эйлера: связный граф является Эйлеровым тогда, когда степень всех его вершин четная. Если число вершин нечетной степени в связном графу = 2, то данный граф содержит Эйлеровую цепь, при этом вершины нечетной степени являются начальной и конечной вершинами цепь).
Гамильтоновы циклы в графе
Гамельтовыйцикл – цикл, проходящий по одному разу через все вершины графа.Граф G называется Гамельтовым, если он содержит гамельтовый цикл.
