Маршруты. Цепи. Циклы. Связность.

Последовательность вершин графа G такая, что любые две соседние вершины в ней смежны, наз. маршрутом.Первая и последняя вершины – концевые. Маршрут, у к-го первая и последняя вершины совпадают наз. замкнутым, в противном случае – открытым. Маршрут, у к-го все рёбра различны наз. цепью. Замкнутая цепь – цикл. Цепь у к-й все вершины различны, наз. простой. Цикл, у к-го все вершины кроме первой и последней различны –простой. Граф наз. связным, если из любой его вершины можно попасть в любую по некоторому маршруту. Максимальный по включению связный подграф графа G наз. компонентой связности.

Способы задания графов

1.Списком рёбер

2 .Матрицей смежности

gij= 1(i,j)ЄU

0, в противном случае

3.Матрица инцидентности

(Рёбра нумеруються, строки соответствуют номерам рёбер)

g ij= 1, вершина i и ребро j инцидентно графе

0, в противном случае

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

Пусть граф задан матрицей смежности. Необходимо выяснить, является ли он связным.G=(N,U), M-рабочее мн-во.

1.M=. Выбираем произвольную вершину графа i и заносим её в M.

2.Если мощность мн-ва =n(│M│=n), n-колич вершин, то граф связан и конец работы алгоритма. В противном случае переходим к третьему шагу.

3.Выбираем все такие вершины, которые не вошли в M и каждая из которых смежна по крайней мере одной вершине из M.

4.Полагаем, что все такие вершины образуют множество Р.

5.Если Р= Ø, то граф не связан. Конец работы аьгоритма и тогда G(M)-компонент связности данного графа, иначе переходим на шаг 6.

6.Расширяем множество М(M∪P) и переходим на шаг 2.

Конец алгоритма.

Алгоритм не зависит от структуры. Эффективность работы алгоритма определяется двумя параметрами:

1. Объём памяти, необходимый для его реализации

2. Время работы алгоритма.

В этой паре доминирует время.

Оценим временную сложность алгоритма распознования связности, выбрав в качестве размерности число вершин n.

Величина d имеет порядок О(f(n)) если найдётся некоторая константа с, которая не зависит от n. Такая, что d≤c·f(n)

Алгоритм распознования связности состоит из повторяющихся щагов, на каждом из которых определяется мн-ство Р и разширяется мн-ство М. Число таких шагов не превышает числа вершин графа.

Оценим временную сложность каждого такого шага.

Для построения мн-ства Р достаточно перебрать все пары вершин (і,j) іЄМ, jЄN, число таких пар не превышает n^2. Определения множества Р-самая трудоёмкая часть каждого шага. Поэтому временная сложность шага не превышает n^3. Алгоритм считается эффективным, если его временная сложность оценивается многочленом от размерности задачи.В противном случае алгоритм назыв экспонициальным. Алгоритмы, временная сложность которых оценивается полиномом от размерности задачи, называется полиномиальным. Задачи, для которыз сущ полиномиальные алгоритмы, называются хорошими, а для которых не существует-труднорешаемые.

Распознование связности-хорошая задача.