23. Задача о распределении средств между n предприятиями (основные уравнения)

S₀=4д.е., размеры вложений кратны 1д.е.

Х	Z1	Z2	Z3
0	0	0	0
1	6	3	4
2	7	4	6
3	11	7	8
4	13	11	13

X₁ X₂ X₃

S₀ S₁ S₂ S₃

S1=S0-X1

S2=S1-X2

S3=S2-X3

24. Понятие графа и способы его задания. Степень вершины. Инцидентность. Матрица смежности.

Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:

- V это непустое множество вершин или узлов,

- E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра – линиями, соединяющими те точки, соответствующим вершинам которых ребра инцидентны.

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

задание графа как алгебраической системы. <{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>. Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин. Тогда данный граф запишется как <{a,b,c,d}; {(a,b), (b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)}>. В таком представлении ребру соответствуют две пары вершин (v1,v2) и (v2,v1), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин – его мы и будем отождествлять с ребром.

Задание графов матрицей смежности: Матрица смежности – квадратная матрица порядка p (кол-во вершин), элемент которой, стоящий в i строке и j столбце определяется по правилу:

Задание графов матрицей инцидентций

Матрицей  инцидентции называется прямоугольная матрица размерности   (p –  количество вершин, q – количество ребер), элемент которой стоящий в i строке и j столбце определяется по правилу:

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

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

ПРИМЕР

Степенью deg V вершины V называют количество инцидентных ей рёбер(при этом петли считают дважды). Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Пусть v и u вершины графа,  e = (v, u) это ребро графа, тогда вершина v и ребро e u называются инцидентными, вершина u и ребро e так же инцидентные.

25. Понятие маршрута, цепи, простой цепи, цикла для графа. Связные, несвязные графы. Дерево, лес.

Маршрутом в графе  называется  последовательность   вершин  и ребер  v₀ v₁ v₂ v₃ …v_n

Длиной маршрута называется количества ребер в нем

Маршрут, в котором все вершины различны, называется простой цепью Замкнутая простая цепь называется простым циклом

Замкнутая цепь называется циклом

Расстоянием между вершинами u и v  называется длина кратчайшей цепи d(u, v)

Граф называется связанным, если любые его две вершины можно соединить цепью. Граф сильно связан, если для его двух любых вершин х_i ≠х_j существует путь, идущий изх_i и х_j.

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

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

Совокупность деревьев называется лесом.