-
Понятие графа
Графом называют совокупность двух конечных множеств м множество рёбер (дуг) и равное {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 называется
Гамельтовым, если он содержит гамельтовый цикл.