Презентация на тему Операции над графами

G2 есть граф G, для которого x1• x2= G

(рис. 10.17).






Рис. 10.17

вершин (рис. 10.18).




Рис. 10.18

двойственная стягиванию ребра (рис. 10.19)




Рис. 10.19

Построим некоторые из них.
Матрицей смежности вершин графа называется квадратная

матрица А = {aik} размером n х n, у которой строки и столбцы соответствуют вершинам, а элементы aik определяют из условий:

смежности A(G).






Рис. 10.20

G = (X,U) называется прямоугольная матрица размерности n х

т (n — число вершин графа, m — количество дуг), элементы которой удовлетворяют условиям:

ее построении элементы -1 следует заменить на 1.
Построим матрицу

B(G) инциденций для орграфа G (рис. 10.20).

{cik} графа G называется квадратная матрица размерности n х

n, элементы которой определяют из условий:


Матрицу пропускных способностей дуг С = (G) можно построить на основании матрицы смежности А = (G), в которой 1 заменяются значением cik пропускной способности соответствующей дуги графа.

G называется квадратная матрица размерности n х n (n

— число вершин орграфа), элементы которой удовлетворяют условиям:

все вершины соединены простой цепью называется связным.
Отношение связности

вершин графа называется эквивалентностью. Классы эквивалентности по отношению к связности называются компонентами связности графа, или компонентой связности графа называется его связный подграф.

граф имеет две компоненты связности, на рис. 10.20, 6

у графа 3 компоненты связности.







Рис. 10.22

G обозначается k(G).
Граф G является связным, когда k(G)

= 1.
Если k(G) > 1, то граф называется несвязным. Например, для графа на рис. 10.24 k(G) = 1, для графа (рис. 10.25) k(G) = 2 и для графа G, представленного на рис. 10.26, k(G) = 3.







Рис. 10.24 Рис. 10.25

точкой сочленения, если ее удаление увеличивает число компонент связности.

Мостом называется ребро графа, удаление которого увеличивает число компонент связности.
Блоком называется связный граф, не имеющий точек сочленения.
На рис. 10.23, в графе G: вершины х3 и х4 являются точками сочленения, ребро U4 (x3, х4) называется мостом и связные подграфы {x1,x2,x3}, {x4,x5,x6}, {xs,x6,x7}, {х4,х5,х6,х7} являются блоками.

= (X,U) связен тогда и только тогда, когда его

нельзя представить в виде объединения двух графов.

связным графом или сильным, если для любых различных двух

вершин хi и хк существует по крайней мере один путь, соединяющий эти вершины, т.е. любые две вершины взаимно достижимые (рис. 10.24).
Орграф G2 называется односторонне связным или односторонним, если для двух вершин хi и хк существует путь либо из хi в хк либо из хк в хi (рис. 10.25).





Рис. 10.24 Рис. 10.25

или слабым, если для двух любых вершин графа существует

по крайней мере один маршрут (рис. 10.26).
Орграф G4 называется несвязным, если для некоторой пары вершин его не существует маршрута, соединяющего их (рис. 10.27).




Рис. 10.26 Рис. 10.27

ребер в нем (с повторениями). Обозначается ׀М׀ = К.
Расстоянием

между вершинами хi и хк называется длина кратчайшей цепи, а сама кратчайшая цепь называется геодезической. Обозначается расстояние l (xi, xk).
Диаметром графа G (обозначается D(G)) называется длина наибольшей геодезической.
Эксцентриситетом е(хi) вершины хi в связном графе G(X,U) называется максимальное расстояние от вершины до других вершин графа G.
Радиусом R(G) графа G называется наименьший из эксцентриситетов вершин.
Вершина xi называется центральной, если ее эксцентриситет совпадает с радиусом графа, т.е. е(хi) = R(G).

эксцентриситеты вершин и центры двух графов G1 и G2.
Вершины,

составляющие центры, выделены.

заключается в нахождении маршрута путем обхода семи мостов по

одному разу, который начинается и оканчивается в одной части города, рис. 10.29.
При решении задачи (рис. 10.29, а) Эйлер составил граф G (рис. 10.29, б) и доказал, что поставленная задача решений не имеет. Указанный замкнутый маршрут, называемый циклом, существует в графах с четными степенями вершин.

содержащий все ребра графа по одному разу, то такой

цикл называется эйлеровым циклом, а соответствующий граф называется эйлеровым.

все ребра (по одному разу) графа, но и все

вершины этого графа (возможно по несколько раз). Эйлеровым может быть только связный граф. Примером такого графа является граф, представленный на рис. 10.30.




Рис. 10.30

= (X,U) связан и нетривиален, то следующие утверждения эквивалентны:
G

= (X,U) — эйлеров граф.
Каждая вершина имеет четную степень.
Множество ребер можно разбить на простые цепи.

задачи о кругосветном путешествии, сформированной У. Гамельтоном: Необходимо обойти

все вершины графа, диаграмма которого представляла укладку додекаэдра (рис. 10.31), по одному разу и вернуться в исходную точку. В начальной постановке задачи вершинами графа были столицы государств.

цикл, содержащий все вершины графа по одному разу, то

такой цикл называется uамельтоновым циклом, а граф называется гамельтоновым.
Гамельтонов цикл не обязательно содержит все ребра графа, но сам граф может быть только связным.

= (Х,U) с n вершинами степень каждой вершины не

меньше чем ,то граф является гамельтоновым.
Задача коммивояжера заключается в отыскании кратчайшего гамельтонова цикла в нагруженном полном графе.
Имеется n городов, расстояние между которым известны, коммивояжер должен посетить все n городов по одному разу, вернувшись в исходный город. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным.