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