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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


задача Элементы теории графов. Центры и периферийные вершины графов, их радиусы и диаметры. Максимальный поток транспортировки груза и поток минимальной стоимости. Пропускная способность пути. Анализ сетей Петри, их описание аналитическим и матричным способами.

Информация:

Тип работы: задача. Предмет: Математика. Добавлен: 28.08.2010. Сдан: 2010. Уникальность по antiplagiat.ru: --.

Описание (план):


3

Задача 1. Элементы теории графов

Связный ориентированный граф G (Х, Г) задан множеством вершин X={x1, x2, …, xn} и отображением Гxi={x|Ik|, x|Il|}, i =1, 2,, n. Здесь i - текущий номер вершины, n- количество вершин графа. Значение индексов n, k и l возьмем из табл.1 в соответствии с номером варианта. Индексы k и l формируют значения индексов , , … переменной x в отображении Гxi = {x , x , x,…}. Если значения индексов , , … переменной x не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Гxi.

Выполнить следующие действия:

а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами;

б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов;

в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов;

г) описать систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами xi и xj

i*j при i j;

Kij =

1/ (p+1) при i<j .

Найти передачу между вершинами x1 и xn, используя правило Мезона. Построить структуру кибернетической системы, определяемой топологией графа;

Таблица 1


варианта
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
K
2
3
4
1
1
1
3
5
2
4
2
3
4
5
6
L
1
1
1
2
3
4
2
1
3
3
1
1
1
1
1

варианта
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
N
6
6
6
6
6
6
6
6
6
7
7
7
7
7
7
K
1
1
1
1
3
2
5
5
2
3
4
5
6
5
3
L
2
3
4
5
2
3
2
3
3
2
3
2
1
3
5
Решение:
Множество вершин
X = {x1, x2, x3, x4, x5, x6 }, n = 6 k = 2, l = 1 Гxi={x|Ik|, x|Il|}.
а) определим исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами:
Определим граф аналитическим способом:
Гx1 = { x1, x3, x2 };
Гx2 = { x4, x1, x3 };
Гx3 = { x1, x5, x2, x4 };
Гx4 = { x2, x6, x3, x5 };
Гx5 = { x3, x4, x6 };
Гx6 = {x4, x5 }.

Ориентированный граф графическим способом:
Неориентированный граф графическим способом:
Ориентированный граф матричным способом:
RG - матрица смежности
x1
x2
x3
x4
x5
x6
x1
1*
1
1
0
0
0
x2
1
0
1
1
0
0
x3
1
1
0
1
1
0
x4
0
1
1
0
1
1
x5
0
0
1
1
0
1
x6
0
0
0
1
1
0
AG - матрица инцидентности
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
v11
v12
v13
v14
v15
v16
v17
v18
v19
x1
1*
1
-1
0
0
0
0
0
0
0
0
1
-1
0
0
0
0
0
0
x2
0
-1
1
1
-1
0
0
0
0
0
0
0
0
1
-1
0
0
0
0
x3
0
0
0
-1
1
1
-1
0
0
0
0
-1
1
0
0
1
-1
0
0
x4
0
0
0
0
0
-1
1
1
-1
0
0
0
0
-1
1
0
0
1
-1
x5
0
0
0
0
0
0
0
-1
1
1
-1
0
0
0
0
-1
1
0
0
x6
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
0
0
0
-1
1
Неориентированный граф матричным способом:
RD - матрица смежности
x1
x2
x3
x4
x5
x6
x1
1*
2
2
0
0
0
x2
2
0
2
2
0
0
x3
2
2
0
2
2
0
x4
0
2
2
0
2
2
x5
0
0
2
2
0
2
x6
0
0
0
2
2
0
AD - матрица инцидентности
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
v11
v12
v13
v14
v15
v16
v17
v18
v19
x1
1*
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
x2
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
x3
0
0
0
1
1
1
1
0
0
0
0
1
1
0
0
1
1
0
0
x4
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
0
0
1
1
x5
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
0
0
x6
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов:
- матрица отклонений имеет вид:
x1
x2
x3
x4
x5
x6
x1
1
1
1
2
2
3
x2
1
0
1
1
2
2
x3
1
1
0
1
1
2
x4
2
1
1
0
1
1
x5
2
2
1
1
0
1
x6
3
2
2
1
1
0
- вектор отклонения
=>
х2, х3, х4, х5 - центры графа с наименьшей удаленностью. Радиус с (G) = 2.
Периферийными вершинами являются вершины х1, х6 с наибольшей удаленностью. Диаметр графа D (G) = 3.
в) выделим в ориентированном графе два подграфа и найдем объединение, пересечение и разность подграфов.
Выделяем два подграфа: G1 и G2

X1 - {x1, x2}, Г1х1 = {x1, x2}, Г1х2 = {x1},
X2 - {x1, x2, x3}, Г2х1 = {x2}, Г2х2 = {x3}, Г2х3 = {x2}.
Объединение ,
,, , .
G

Пересечение
,,, .
G

Разность
,
, , .
G
г) Считая, что передача между вершинами xi и xj

i*j при i j;
Kij =
1/ (p+1) при i<j .
Сигнальный граф имеет вид
Система уравнений, соответствующая сигнальному графу имеет вид
x1 = x1 +2x2 +3x3
x2 = x1 +6 x3 +8 x4
x3 = x1 + x2+12x4 +15x5
x4 = x2 + x3 +20 x5 +24x6
x5 = x3 + x4 +30x6
x6 = x4 +x5

Определить передачу k16 по правилу Мезона. Формула Мезона имеет вид


PS - передача пути,
DS - алгебраическое дополнение,
D - определитель.
Пути из х1 в х6 и передаточные функции для каждого из них имеют вид:
Контура:
;
;;
;;
;;
;;
;;
;
;.
;.
Пары несоприкасающихся контуров
L1L3, L1L4, L1L5, L1L6, L1L8, L1L9, L1L10, L1L13, L1L14, L1L15, L1L16, L1L17, L1L18;
L2L4, L2L5, L2L6, L2L8, L2L9, L2L10, L2L15, L2L16, L2L17, L2L18;
L3L5, L3L6, L3L10, L3L17, L3L18;
L4L6, L5L7; L5L11, L5L12, L6L7, L6L8, L6L11, L6L12, L6L13, L6L14;
L7L8, L7L10, L7L17, L7L18;
L8L9, L9L10, L10L11, L10L12, L11L17, L11L18, L12L17, L12L18.
Независимые тройки
L1L3L5, L1L3L6, L1L3L10, L1L3L17, L1L3L18, L1L4L6, L1L6L8, L1L6L13, L1L6L14, L1L8L9,L1L9L10, L2L4L6, L2L9L10, L6L7L8.

Отсюда
D = 1 - (L1 +L2 +L3 +L4 +L5 + L6 +L7 + L8 +L9 +L10 +L11 +L12 +
+L13 +L14+L15 +L16+L17 +L18)+ (L1L3+L1L4+L1L5+L1L6+L1L8+L1L9+L1L10+L1L13+L1L14+L1L15+L1L16+L1L17+L1L18+L2L4+L2L5+L2L6+L2L8+L2L9+L2L10+L2L15+L2L16+L2L17+L2L18 +L3L5+L3L6+L3L10+L3L17+L3L18 L4L6+L5L7+L5L11+L5L12+L6L7+L6L8+L6L11+L6L12+L6L13+L6L14+L7L8+L7L10+L7L17+L7L18+L8L9+L9L10+L10L11+L10L12+L11L17+L11L18+L12L17+L12L18) -
(L1L3L5+L1L3L6+L1L3L10+L1L3L17+L1L3L18+L1L4L6+L1L6L8+L1L6L13+L1L6L14+L1L8L9+L1L9L10+L2L4L6+L2L9L10+L6L7L8).
D1 = 1- L8;
D2 = 1;
D3 = 1;
D4 = 1 - L9;
D5 = 1;
D6 = 1.
.

Структура кинематической системы представлена на рисунке:

Задача 2. Задача о максимальном потоке и потоке минимальной стоимости

Транспортная сеть задана в виде ориентированного графа, приведенного на рисунке.

На каждом из ребер проставлены значения пропускной способности С () ребра .

Для заданной сети определить максимальный поток max транспортировки груза между указанной парой вершин, считая одну из них источником, а другую -- стоком.

Решение:

Максимальный поток max транспортировки груза между указанной парой вершин, считая одну из них источником, а другую -- стоком:

Первый шаг.1. Находим какой-либо путь из х1 в х9 с положительной пропускной способностью.

Tаблица 1.

x1
x2 (1)
x3 (1)
x4 (1)
x5 (2)
x6 (3)
x7 (3)
x8 (2)
x9 (6)
x1
7
9-
4
x2
0
8
3
6
x3
0+
5
8-
4
x4
0
0
0
9
2
x5
0
2
x6
0+
5
3-
x7
0
0
0
7
6
x8

0
0
0
0
8
x9

0+
0
0
В результате получен путь l1 = (x1, х3, х6, х9). Элементы этого пути Cij помечаем знаком минус, а симметричные элементы Cji - знаком плюс.
Определяем пропускную способность найденного пути, которая равна наименьшей из пропускных способностей дуг:
Определяем остаточные пропускные способности дуг найденного пути и симметричных ему дуг. Для этого из элементов табл.1 вычитаем C1, а к элементам прибавляем C1. В результате получим новую табл.2 с измененными пропускными способностями.
Tаблица 2
x1
x2 (1)
x3 (1)
x4 (1)
x5 (2)
x6 (3)
x7 (3)
x8 (2)
x9 (7)
x1
7
6-
4
x2
0
8
3
6
x3
3+
5
5
4-
x4
0
0
0
9
2
x5
0
2
x6
3
5
0
x7
0+
0
0
7
6-
x8

0
0
0
0
8
x9

3
0+
0
Второй шаг.1. Помечаем столбцы табл.2, находим второй путь l2 = (x1,x3, х7, х9) и расставляем знаки.
2. Пропускная способность пути l2

Изменим пропускные способности помеченных дуг на С2 в табл.3.
Tаблица 3
x1
x2 (1)
x3 (1)
x4 (1)
x5 (2)
x6 (3)
x7 (4)
x8 (2)
x9 (7)
x1
7
2
4-
x2
0
8
3
6
x3
7
5
5
0
x4
0+
0
0
9-
2
x5
0
2
x6
3
5
0
x7
4
0+
< и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.