ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 18
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
-
Понятие графа
Графом называют совокупность двух конечных множеств м множество рёбер (дуг) и равное {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 называется Гамельтовым, если он содержит гамельтовый цикл.