Для ориентированного графа

_b _ij =-1, если дуга aj выходит из вершины vi

__b _ij =1, если дуга aj входит в вершины vi

__b _ij =2, если дуга aj явл. петлей в вершине vi.

__b _ij =0, если вершина vi не инцидентна ребру aj

СПИСОК СМЕЖНОСТИ:

__Список смежности – массив указателей P(n) (n- число вершин) на списки смежности для вершин.

__Список для каждой вершины состоит из информативного поля содержащего смежную вершину и указатель на следующую смежную вершину. Последний эл-т имеет нулевой указатель.

__Для ориентированного графа в список заносятся вершины являющимися конечными для ребер инцидентных с рассматриваемой вершиной.

__вершины должны быть отсортированы в порядке возрастания.

X1 a x2 a x3 a x5 a 0

X2 a x2 a x5 a 0

X3 a 0

X4 a x3 a 0

X5 a x4 a 0

X6 a x1 a x5 a x6 a 0

26. Маршрут, цикл, обход, цепь, простая цепь графа. Длина маршрута, расстояние между вершинами. Аксиомы метрики графа. Одноместные операции: удаление или добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин), подразбиение ребра. Декартово произведение, композиция графов.

Маршрут — последовательность ребер, в которой каждые два соседних ребра имеют общую вершину.

Длина маршрута равна кол-ву ребер в маршруте.

Цикл – маршрут, нач. и заканч. в одной вершине.

Маршрут, содержащий все вершины или ребра графа называется обходом графа.

__Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины и ребра различны.

Длина кратчайшей простой цепи, соединяющей вершины v_i и v_j, называется расстоянием d (v_i,v_j) между v_i и v_j.

АКСИОМЫ::::::

В связном неориентированном графе расстояние удовлетворяет аксиомам метрики: для любых вершин и, v и w

1) d(u, v) ³ 0 и d(u, v) = 0 когда u = v;

2) d(u, v) = d(v, u);

3) d(u, v) + d(v, w) ³ d(u, w)

При удалении вершины в матрице смежности обнуляются строка и столбец с номером этой вершины. При удалении ребра обнуляется эл-т на пересечении указанных строки и столбца (номеров 2-х вершин).

27. Подграфы. Связанный подграф. Компонента связности. K-связанный подграф, К-реберно связанный подграф. Путь, полупуть, достижимость и соединимость вершин в ориентированном графе. Категории связанности ориентированного графа: сильно, односторонне и слабо связанный.

Подграфом G¢ (V¢, E¢) графа G(V, E) называется граф с множ. вершин V¢ Í V и множ. ребер (дуг) E¢ Í E, — такими, что каждое ребро (дуга) из E¢ инцидентно (инцидентна) только вершинам из V¢.

Граф называется связным, если любая пара его вершин соединена маршрутом.

Любой максимальный связный подграф (то есть, не содержащийся в других связных подграфах) графа G называется компонентой связности. Несвязный граф имеет, по крайней мере, две компоненты связности.

Граф называется k-связным (k - реберносвязным), если удаление не менее k вершин (ребер) приводит к потере свойства связности.

Путь из Ui в Uj — послед-ть дуг, соед. вершины Ui в Uj, в кот. конец пред. дуги совпад. с началом след.

Полупуть, соед. Ui и Uj — последовательность дуг, соед. вершины Ui и Uj, в кот. направ. дуг не учитывается.

Вершина Ui достижима из вершины Uj, если имеется путь из Uj в Ui.

Вершины Ui и Uj соединимы, если имеется полупуть, соединяющий Ui и Uj.

· Сильно связным (сильным, категории связности 3) называется орграф D, у которого для каждой пары вершин Ui и Uj вершина Ui достижима из Uj и Uj достижима из Ui.

· Односторонне связным (односторонним, категории связности 2) называется орграф, у которого для каждой пары вершин Ui и Uj, Ui достижима из Uj или Uj достижима из Ui.

· Слабо связным (слабым, категории связности 1) называется орграф, у которого каждая пара вершин Ui и Uj соединима полупутем.

28. Алгоритм определения компонент связности в неориентированном графе.

Любой максимальный связный подграф (не содерж. в других связных подграфах) графа G называется компонентой связности.

Обозначения:

u или v — вершины, (u,v) — ребро;

num — кол-во компонент связности

comp[v] — массив для каждой вершины хранит номера компонент связности, которым принадлежит данная вершина.

DFS(v) — процедура поиска в глубину.

Итог: массив comp[v] содержит число связности для каждой вершины.

1. begin

2. Задание графа // Ваш интерфейс

3. for (v ∊ V)

do comp[v]=0 // все вершины Ï КС

4.num=0 //начальное кол-во КС 0.

5. for (v ∊ V) цикл по всем вершинам

6. {

7. if comp[v]=0 then Если v Ï КС

8. { num=num+1; DFS(v) }

9. }

10. Интерфейс для вывода числа КС и всех КС

11. end

12.Procedure DFS(v)

13. begin

14.comp[v]=num // вершина v Î КС num

15.for (u: (v,u) ∊ E) // по смежным с v

16.{ if comp[u] = 0 then DFS(u) }

17. end

29. Эйлеров путь в графе. Эйлеров цикл. Теорема о существовании эйлерова цикла. Алгоритм нахождения эйлерова цикла и его вычислительная сложность.

___Эйлеровым путем в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз.

___Если v ₁ = v_{m +1}, то такой путь называется эйлеровым циклом. Задача существования эйлерова пути в заданном графе была решена Эйлером в 1736 году, и представленное им необходимое и достаточное условие существования такого пути считается первой в истории теоремой теории графов.

Дата добавления: 2015-11-16