Составление графа по заданной системе уравнений; преобразование графа

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

БАЛАКОВСКИЙ ИНСТИТУТ ТЕХНИКИ ТЕХНОЛОГИИ И УПРАВЛЕНИЯ

КАФЕДРА: УИТ

Практическая работа №3

По дисциплине МОТС

Вариант № 15

Выполнила: ст. гр. УИТ-32

Федорова А. В.

Проверила: Ефремова Т.А.

БАЛАКОВО 2008

Задание №1. По заданной системе уравнений составить граф и провести его преобразование.

Избавимся от дифференциалов в заданной системе уравнений, т.е. произведем замену оператора дифференцирования на оператор Лапласа.

Построим граф:

 

Рис.1

Избавимся от встречно-параллельных дуг:

Избавимся от петли на узле z₂:

Избавимся от петли на узле z₃:

Избавимся от встречно-параллельных дуг:

 

                                                                                                  

 

Рис.2

Избавимся от петли на z₁

Избавимся от петли на z₅:

 

Рис. 3

Избавимся от узла z_3: , при этом каждую входную дугу умножим на все выходные дуги при этой вершине:

 

Рис.4

Избавимся от параллельных дуг:

и от петли на z_4:

Узел z₄ – сток. Избавимся от z₄:

 

Рис.5

Избавляемся от узла z₂:

Избавляемся от параллельных дуг:

 

Рис.6

Избавляемся от узла z₅

Исключаем параллельные дуги

Рис.7

Избавляемся от узла z₁

Избавляемся от параллельных дуг

 

Рис. 8

Задание №2. По заданным схемам ориентированного и неориентированного графов составить матрицы смежности и инцидентности, а т.ж. провести оптимизацию графов.

Неориентированный граф

                                       a                     1                     b

                                                         3        c     2

                               2             4           6         7       6

                         d                2                        e

Рис. 9

Составим списки ребер в порядке увеличения их весов

    1      2      2       2       3      4      6      6     7

(a,b) (a,d) (c,b) (d,e) (a,c) (d,c) (a,e) (e,b) (c,e)

F=1+2+2+2=7

        a                          b           a                          b           a                    b               a                    b

                            c                                     c                                  c                                     c 

 

d                         e            d                         e        d                       e           d                     e

Рис. 10

Таблица №1. Матрица смежности

A=	a	b	c	d	e
a	0	1	1	1	1
b	1	0	1	0	1
c	1	1	0	1	1
d	1	0	1	0	1
e	1	1	1	1	0

Таблица №2. Матрица инцидентности

B=	ab	bc	cd	de	ae	ad	be	bd
a	1	0	0	0	1	1	0	0
b	1	1	0	0	0	0	1	1
c	0	1	1	0	0	0	0	0
d	0	0	1	1	0	1	0	1
e	0	0	0	1	1	0	1	0

Ориентированный граф

                                                      a                1                      b     

                                                              1          c       4   

                                                      1         3      4          3

                                                      e         6           d

Рис.11                                           

Минимальный путь от истока к стоку (0-ae)

Вес пути F=1                                       

(0)    a      1      1              b

1            c       4    3

                                               3       4

      (1)(3)(6)(8)(15)(4)(11)e      6       d

                    Рис.12

Таблица №3. Матрица смежности

C=	a	b	c	d	e
a	0	1	1	0	1
b	0	0	1	0	0
c	0	0	0	1	1
d	0	1	1	0	1
e	0	0	0	0	0

Таблица №4. Матрица инцидентности

D=	ab	bc	cd	de	ac	ec	ae	bd
a	+1	0	0	0	+1	0	+1	0
b	-1	+1	0	0	0	0	0	-1
c	0	-1	+1	0	-1	+1	0	0
d	0	0	-1	+1	0	0	0	+1
e	0	0	0	-1	0	-1	-1	0