48) Элементы теории Графов. Граф-пара двух конечных множеств множества точек и множество линий соединенных некот.Пары точек. G(V,X) где V-множ.Точ. Х-множ.Линий.

Множество линий-является подмножеством второй декартовой степени множества точек.

(Х с )

Графы бывают: Неориентированные, и Ориентированные.

Способы задания графов: а) Геометрически(диаграммой) б) Матрицей инцидентности

в) Матрицей смежности. г) Простым перечислением его вершин и ребер(дуг)

49) Граф назыв. Неориентированным,если множ-во его линий представляет собой множество неупорядоченных пар на множестве точек. (g1, g3)

Элементы множества точек как для неориентированного так и для орграфа называются вершинами.

Элементы множества линий для неориентированного графа назыв-я ребрами, а для орграфа-дугами.

Две вершины неориентированного графа назыв-я смежными(концом ребра) если они соед-ы ребромю( G3)

Два ребра неориентированного графа назыв-я кратными ,если они имеют одинаковые концы: число кратных ребер называ.кратностью ребра.(G3, G1)

Теорема Эйлера: Сумма степеней всех вершин неориентированного графа-число четное=удвоенному числу ребер

Ребро неориентированного графа назыв.инцидентным его вершине,если вершина явл-я одним из концов ребра.

Ребро неориентированного графа,концы которого совпадают называют петлёй!

Степенью вершины неориентированного графа назыв.число ребер инцидентным данной вершине.

50) ОРГРАФ: Если множество линий графа представляет собой множество упорядоченных пар на множестве точек, то граф-ориентированный.(G2)

Элементы множества точек орграфа-назыв.вершинами.

Елементы множества линий для орграфа назыв.дугами.

Вершина V1 орграфа называется смежной вершине V2 если есть дуга графа начало которой V1 а конец V2.

Два ребра орграфа графа назыв-я кратными ,если они имеют одинаковые концы: число кратных ребер называ.кратностью ребра.

Ребро орграфа графа назыв.инцидентным его вершине,если вершина явл-я одним из концов ребра.

Степенью вершины оргафа графа назыв.число ребер инцидентным данной вершине.

Вершина графа называется четной, если ее степень-четное число,в противном случае-называется нечетной.

Утверждение: Число нечет.вершин неориентированного графа-четное.

51)Два графа называются изоморфными,если сущ.взаимно-однознач.соответствие,между их ребрами(дугами) и их вершинами,причем.соответствующие ребра(дуги) соединяют соответствующие вершины (G3 G5)

Способы задания графов: а) Геометрически(диаграммой) . Геометрическое представление графа часто называют геометрической реализацией или диаграммой графа.

б) Простым перечислением его вершин и ребер (дуг). в) Матрицей инцидентности В=(вi,j) графа называется матрица размера n на m в которой :

Неориентированный граф: вi,j=1, если Vi инцед.ребру Xj. вi,j=0, если Vi не является инц.Xj/

Орграф: вi,j=0, если Vi не явл-я инц.дуге Xi. вi,j=1, если Vi-началоXj. вi,j=-1, если Vi-конец.Xj

г) Матрицей смежности графа называется квадратная матрица размерности n на n A(aij) в которой ai,j- если Vi смежна Vi . ai,j=0 если Vi не является смеж. Vj.