Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Письменная часть
(1), (2), (3), (4)
Устная часть
Граф G(V,E) - комбинаторный объект, состоящий из Z конечных множеств: V-множество вершин и множество пар элементов из v,
т.е. E подмножество или равно V*V, называемого множеством ребер, если пары неупорядочены и множеством дуг, если пары упорядочены.
1)ориентированный граф 2)неориентированный граф
(1) (2)
Если e=(V1,V2), e содержится в E, то говорят что ребро е соединяет вершины V1 и V2. Если V1=V2, то ребро е - петля.
Две вершины V1, V2 - смежные, если существует соединяющее их ребро(дуга). Тогда каждая из вершин зовется инцидентной соответствующему
ребру.
Два различных ребра смежные, если имеют одну общую вершину.
Способы задания графов:
1)Граф как алгеброическая система
Модель носителем которой является множество венршин, а отношение - бинарное отношение смежности вершин.
[{a,b,c,d} - множество вершин {(a,b,),(b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)}(3) - множество ребер]
2)геометрический - получается путем расположения различных точек на плоскости для каждой вершины v содержится в V причем если
(V1,V2) содержатся в E, то проводится ребро (дуга) из V1 в V2.
3)Матрица смежности (матричный способ задания бинарного значения)
Пусть дан граф G его матрица смежности A=(a[i,j]) определяется так:
a[i,j]=1 если в G существует дуга (xi,xj)
a[i,j]=0 если в G нет дуги (xi,xj)
Сумма всех элементов строки xi матрицы смежности является полустепенью исхода вершины xi.
Сумма всех элементов столбца xi матрицы смежности является полустепенью захода вершины xi.
множество столбцов имеющих 1 в строке xi, есть множество вершин дуг, для которых xi является началом.
4)Матрица инциденций (инцидентности)
(почти никогда не бывает квадратной)
Пусть дан граф G с n вершинами и m дугами.
Матрица инциденций графа G обозначается B=(b[i,j]) и является матрицй размерности n*m определяемой так:
b[i,j]=1 xi - начальная вершина дуги aj
b[i,j]=-1 xi - конечная вершина дуги aj
b[i,j]=0 xi - не является конечной вершиной дуги aj или если aj является петлей
Если в графе имеются петли, то их можно обозначать любым символом/цифрой отличной от +1,-1,0 (дабы в матрице сохранить структуру графа)
Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец
либо содержит один элемент, равный 1, и один равный -1, либо все элементы столбца равны 0.
Если G - неориентированный граф, то его матрица инциденций определяется также как и выше, за исключением того, что все элементы
равные -1 заменяются на +1.
Степени вершины.
Степенью (deg V) или валентностью вершины V неориентированного графа G называется число ребер, инцидентных вершине.
вершина степени 0 называется изодированной
Вершина степени 1 называется концевой или висячей
Пусть G ориентированный граф
Полустепенью захода (deg -V)вершины V называется число дуг, входящих в вершину V.
Полустепенью исхода (deg +V)вершины V называется число дуг, выходящих из вершины V.
справедливо следующее:
deg V = (deg +V) + (deg -V)
Маршрут - последовательность ребер e1,...,e2, такая, что ei, e(i+1) имеют общую вершину.
Число ребер называется длиной маршрута.
Пусть G неориентированный граф
Маршрут называют цепью, есливсе ребра в нем различны.
Если ни одна из вершин не появляется более 1 раза, то маршрут называется простой цепью.
Маршрут циклический, если первая вершина в нем равна последней.
Циклическая цепь - цикл, циклическая простая цепь - простой цикл.
Неориентированный граф без циклов называется ациклическим.
(1,2), (1,2,4,7), (3,4,5,6) - простые цепи
(1,2,4,7,8,4) - не простая цепь
(1,2,4,7,8,4,2) - маршрут не цепь
(1,2,4,7,8,4,1) - цикл не простой
(1,2,4,1) - простой цикл
Обхват графа = 3
(4)
Обхват - самый короткий цикл в графе
Реберная и вершинная связанность
Вершинной связаностью графа G зовут наименьшее число вершин, удаление которых приводит к несвязному графу
Реберная связанность определяется как наименьшее количество ребер, удаление которых приводит к несвязному графу
Максимальный связный подграф графа G называется компонентой связности
Пусть G граф с n вершинами k компонентами связности. Если граф связный, то число ребер в нем min, когда он ациклический,
и max, когда он полный.
Тогда имеет место следующая оценка для числа ребер связного графа:
n-1<=|E|<=n(n-1)/2
Дополнительная часть
1
2
3
4
5
6
7
8