Интеграл, двойной интеграл, тройной интеграл, центр тяжести, масса тела, граф, уровни, отношения, матрица

      
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3.Графы 
 

Определение 1. 

         Пусть дано множество М определенное  в евклидовом пространстве En. Бинарным отношением R на множестве M называется подмножество декартового произведения множества на само себя.

   Следовательно, отношение R представляет множество упорядоченных пар x и y некоторых элементов одного и того же множества M.

   Бинарные отношения могут быть  заданы в виде:

а) матриц – бинарные отношения R в каждой строке и столбце матрицы взаимно однозначно сопоставляются элементам множества М, при этом каждое пересечение <Xi;Xj> взаимно определенно соответствует элементам множества M.

б) графов – элементы множества изображаются точками, а отношения стрелками, соединяющими <Xi;Xj> при наличии соотношения R.

в) сечений (окрестностей единичного радиуса). 

Определение 2.

      Граф G считается определенным, если задано некоторое семейство сочетаний элементов или пар вида E=(a, b), где , указывающее какие элементы считаются связанными.

 Определение 3.

      Пара E=(a, b) называется ребром, a, b-концевыми точками ребра, вершинами.

Определение 4.

      Если  порядок расположения концевых точек  безразличен, то говорят что E=(a, b)=(b, a)- неориентированное ребро. В противном случае

E= (a, b)¹( b, a)- ориентированное ребро или дуга.

 Определение 5.

      Граф  конечен если число ребер конечно, в противном случае граф бесконечен.

Определение 6.

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

Определение 7.

      Дуга, начало и конец которой совпадают, называется петлей.

Определение 8.

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

Определение 9.

      Граф  H называется частичным для графа G, если его множество вершин содержится во множестве вершин графа G и все его ребра являются ребрами G. 

Определение 10.

      Граф  G1 называется подграфом графа G, если множество вершин D графа G1 содержится во множестве вершин V графа G и ребра графа G1 являются всеми ребрами графа G, вершины которого лежат во множестве D.

Определение 11.

      Суграф это часть графа, образованная удалением некоторых ребер.

Определение 12.

      Маршрут это последовательность смежных  ребер. Смежным считается ребро  инцидентное одной и той же вершине. Маршрут может соединять повторяющиеся ребра или вершины.

Определение 13.

      Цепь  это маршрут, в котором все  ребра различны.

Определение 14.

      Путь  это такая последовательность дуг, в которой начало последующей совпадает с концом предыдущей.

Определение 15.

      Контур  это такой конечный путь, у которого начальная вершина первой дуги совпадает с концом последней.

Определение 16.

      Цикл  это такая конечная цепь, которая начинается и заканчивается в одной и той вершине.

Определение 17.

      Длиной  цепи называется число ребер входящих в цепь.

Определение 18.

      Граф  является связанным, если для любых вершин i и j существует цепь из i в j.

Определение 19.

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

Определение 20.

      Ветви это ребра графа вошедшие в  дерево. 

         
 
 
 
 
 
 
 
 
 
 
 

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

3.1.1. Графическое  представление графов

 

  Это  самое наглядное представление  отношений между элементами.

 

 Пример №1 

 

Рис.8

Недостатки: трудоемкость изображения, сложность математизирования структуры.

 

3.1.2. Матричное  представление графов 

Определение №1

   Матрицей смежности вершин, для  неориентированного графа, называется  матрица вида,  где i,j изменяются от 1 до n, где n число вершин графа.

                             (13)

Определение №2

   В матрице смежности ориентированного  графа элементы  определяются следующим образом:

                              (14) 
 

Пример№1                 

Таблица№2

3.1.3. Множественное  представление графа 
 

Множество правых инциденций                                         Множество левых инцидеций                                                                                           

G (1) = (2, 8)                                                                  (1) = (12, 22)

G (2) = (3, 16)                                                                (2) = (1, 13)

G (3) = (z)                                                                      (3) = (2, 4, 13)

G (4) = (3, z)                                                                  (4) = (5, 14)

G (5) = (4)                                                                      (5) = (14, 15)

G (6) = (15, z)                                                                (6) = (7, 20)

G (7) = (6, z)                                                                  (7) = (16, 18)

G (8) = (16, 18)                                                              (8) = (1)

G (9) = (20)                                                                    (9) = (10, 19)

G (10) = (9, 11)                                                              (10) = (21)

G (11) = (12)                                                                  (11) = (10, 19)

G (12) = (1, 22)                                                              (12) = (11, x0)

G (13) = (1, 3, z)                                                            (13) = (Ø)

G (14) = (4, 5, z)                                                            (14) = (15)

G (15) = (5, 14)                                                              (15) = (6)

G (16) = (7)                                                                    (16) = (2, 8)

G (17) = (18, 22)                                                            (17) = (x0)

G (18) = (7, 20)                                                              (18) = (8, 17)

G (19) = (9, 20, 21)                                                        (19) = (x0)

G (20) = (6)                                                                    (20) = (9, 18, 19)

G (21) = (10, 11)                                                            (21) = (19, x0)

G (22) = (1)                                                                    (22) = (12, 17, x0)

G(x0) = (11, 12, 17, 19, 21, 22)                                      (x0) = (Ø)

G (z) = (Ø)                                                                      (z) = (3, 4, 6, 7, 13, 14) 
 
 
 
 
 
 

 

3.2. Разбиение  на слои. Критический путь

       

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

   Полученные не пересекающиеся  подмножества называются уровнями. 

Уровни

 

Рис.9 

      Из  рисунка 9 следует, что главным по значимости элементом является X0, вторым 19, третьим 21 и так далее. Особенностью этого графа является элемент 13, он, как и X0, не зависит от других элементов, но уступает по значимости X0 и поэтому находится в этой структуре на восьмом уровне. На последнем уровне находится элемент Z, он непосредственно подчиняется сразу

6 элементам и  не воздействует ни на один  элемент.

      Критическими  путями из вершины X0 в вершину Z являются пути:

(X0, 12,  1, 8, 18, 7, 6, Z); (X0, 19,  9,  15, 5, 4, 3, Z); (X0, 19, 21, 10, 11, 12, 22, 1, 8, 18, 7, Z); (X0, 19, 21, 11, 12, 1, 8, 18, 7, 6, Z).