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

Страницы работы

Содержание работы

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

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

КАФЕДРА: УИТ

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

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

Вариант № 15

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

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

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

БАЛАКОВО 2008

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

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

P+9

15p-2Построим граф:

1,p-1,02,p-+0,1,P+0,1,-0,5,9,0,5,0,5,-0,3,-0,2,1,1,0,1,0,6,0,5,-0,6,0,25,0,1,1,2
 


Рис.1

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

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

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

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

P+9

p-2,p+0,1,a1,-0,2,a7,a8,a2,0,25,1,Z1,Z5,Z4,a6
 


0,1y-0,6                                                                                                  

a4,Z2
x
 


Рис.2

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

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

2
 


Рис. 3

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

a1,2
a12
 


Рис.4

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

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

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

a1,a2,a10,а9,a4,а11,2
 


Рис.5

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

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

a18,a10,a9,a19,2 


Рис.6

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

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

a9,a21,a22


Рис.7

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

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

a24
 


Рис. 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

Похожие материалы

Информация о работе

Тип:
Отчеты по лабораторным работам
Размер файла:
48 Kb
Скачали:
0