Презентация на тему Теория Графов

непустого множества V (множества вершин) и множество E двухэлементных

подмножеств множества V. Множество E называется множеством ребер.
Ребро, которое соединяет вершину саму с собой, называется петлей

ребром (vi, vj) или инцидентны к ребру (vi, vj),

если (vi, vj)E. Если (vi, vj) – ребро, тогда вершины vi и vj называются концами ребра (vi, vj).
Число вершин графа G обозначим v, а число ребер - e:

такой граф, который состоит из множества V вершин и

множества E упорядоченных пар элементов из V. Элемент множества E называется дугой. Если (vi, vj)E, то vi называется начальной вершиной дуги (vi, vj), а vj называется конечной вершиной.

e2=(v1,v3) образована начальной вершиной v1 и конечной вершиной v2

G(V,E), если V V, E E. Если V=V, то

G называется остовным подграфом G.

называется количество ребер, инцидентных этой вершине. Вершина степени 0

называется изолированной. Вершина степени 1 называется висячей.
Теорема (Теорема Эйлера) Сумма степеней вершин графа равна удвоенному количеству ребер:

дуг, для которых v является начальной вершиной, обозначается d-(v).

Полустепенью захода вершины v называется количество дуг, для которых v является конечной вершиной, обозначается d+(v) .

вершин, называют квадратную матрицу A=aij n-го порядка, у которой

строки и столбцы матрицы соответствуют вершинам неориентированного графа. Элементы aij матрицы A равны числу ребер, направленных из i-й вершины в j-ю.

это квадратная матрица A=aij n-го порядка, у которой строки

и столбцы матрицы соответствуют вершинам орграфа. Элементы aij матрицы A равны числу дуг, направленных из i-й вершины в j-ю. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0, либо 1.

m ребрами называется матрица Bij=[bij]размерности n x m ,

строки которой соответствуют вершинам, а столбцы – ребрам. Элементы матрицы инцидентности неориентированного графа равны 1, если вершина инцидентна ребру , и 0 в противном случае

m ребрами называется матрица Bij=[bij]размерности n x m ,

строки которой соответствуют вершинам, а столбцы – ребрам. Элементы матрицы инцидентности неориентированного графа равны 1, если вершина инцидентна ребру , и 0 в противном случае

v1, v2, …, vnV и ребрами e1, e2, …,

emE. Маршрутом (путем) длины k из v0 в vk (или между v0 и vk) называется последовательность v0e1v1e2v2e3v3…vk-1ekvk такая, что ei=(vi-1, vi).
Если все ребра различны, то путь называется цепью. Если все вершины различны (а значит, и ребра), то путь называется простой цепью. Замкнутая цепь называется циклом. Замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим.

то такое число называется весом, а сам граф называется

взвешенным графом. Простой взвешенный граф (сеть) может быть представлен также своей матрицей весов W=[ij], где ij – вес ребра, соединяющего вершины vi и vj. Весы несуществующих ребер (дуг) полагают равными нулю или бесконечности в зависимости от приложений.

– это граф, компоненты которого являются деревьями.
Ориентированное дерево T

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

T – подграф графа G и каждая вершина G

является вершиной в T.
Минимальным остовным деревом называется такое остовное дерево графа G, что вес T меньше или равен весу любого другого остовного дерева графа G. Вес минимального остовного дерева будем обозначать min(T).
 

минимального веса, не принадлежащее множеству E и такое, что

его добавление в E не создает цикл в дереве T.
2) Добавить это ребро во множество ребер E.
3) Продолжить, пока имеются ребра, обладающие указанными свойствами.