90935

Моделирование структуры дискретной системы

Лабораторная работа

Математика и математический анализ

Используя электронные таблицы Excel (функция СЛУЧМЕЖДУ, клавиша F9 отменяет изменение значения) сформировать случайным образом множество связей между 4 элементами системы, для чего построить при помощи датчика случайных чисел матрицу смежности вершин соответствующего ориентированного графа.

Русский

2015-07-10

53.5 KB

14 чел.

Лабораторная работа №2

Моделирование структуры дискретной системы.

2.1. Учебные цели занятия:

изучение и практическое освоение основных понятий теории систем;

изучение методов описания структуры системы;

экспериментальная (на компьютере) проверка теоретических положений.

22. Некоторые теоретические сведения.

Системой называется рассматриваемая как единое целое совокупность элементов, связей между элементами и взаимодействий с внешней средой. Структура – совокупность двух множеств: множества элементов V={vi, i=1,…n} и множества связей между элементами E={eij}. Математической моделью структуры является граф.

Граф называется конечным, если конечными являются множества его вершин и дуг. Граф называется ориентированным, если дуга eij имеет направление (например, из vi в vj), если ориентация не указана, то дуга называется ребром.  Ориентированный граф называют орграфом. Дуга (ребро) называется петлёй, если оно начинается и заканчивается в одной вершине.

Матрица инциденций орграфа R=[rij] – прямоугольная матрица размерности mn, строки которой соответствуют вершинам, а столбцы – дугам графа. При этом rij =1, если дуга uj выходит их вершины vi;  rij = 1, если дуга uj заходит в вершину vi и rij=0 в остальных случаях. Если граф является неориентированным, то элементами матрицы будут 0 и 1. Строки матрицы инциденций называются векторами инциденций.

Матрица смежности вершин орграфа A=[aij]: aij=1, если есть дуга, ведущее из vi в vj, и aij=0 в противном случае. Очевидно, если граф неориентированный, тогда aij=aji, т.е. матрица смежностей для неориентированного графа – симметрична. Для орграфа в общем случае aijaji. Матрица смежности дуг орграфа В=[bij]: bij=1, если есть дуга ui, непосредственно предшествующая дуге uj, и bij=0 в противном случае.

Степень вершины P(vi) - это количество инцидентных ей рёбер. Вершина степени 1 называется висячей. Вершина степени 0 называется изолированной. Полустепень захода вершины орграфа (количество входящих дуг) P+ (vi) равна сумме элементов i–го столбца матрицы смежности вершин. Полустепень исхода вершины орграфа (количество выходящих дуг) P-(vi) равна сумме элементов i–ой строки матрицы смежности вершин. Путь из вершины v1 в вершину vk – это последовательность смежных рёбер (v1,v2),(v2,v3), …,(vk-1,vk), где v1, v2,…, vkразличные вершины, кроме, может быть, v1=vk. Граф называется связным, если между любыми двумя его вершинами существует путь.

2.3. Порядок выполнения работы

  1.  Используя электронные таблицы Excel (функция СЛУЧМЕЖДУ, клавиша F9 отменяет изменение значения) сформировать случайным образом множество связей между 4 элементами системы, для чего построить при помощи датчика случайных чисел матрицу смежности вершин соответствующего ориентированного графа.
  2.  Построить графически структуру полученной системы в виде орграфа. Построить матрицу смежности дуг и матрицу инциденций полученного ориентированного графа (для чего предварительно пронумеровать дуги).
  3.  На основе построенных матриц исследовать структуру полученной системы в соответствии с вариантом. Проверить результаты исследования графически.
  4.  Подготовить отчет.

2.4. Задания для лабораторной работы и самостоятельной работы студентов.

варианта

Задание

  1.  

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

б) определить все изолированные вершины графа.

  1.  

а) определить, является ли данный граф связным;

б) определить все вершины, смежные вершине 1.

  1.  

а) определить, образуют ли цикл вершины 1,2,3;

б) определить все изолированные вершины графа.

  1.  

а) определить вершину, в которую направлено минимальное количество дуг;

б) определить все висячие вершины графа.

  1.  

а) определить, в какие вершины направлены дуги из вершины 2;

б) определить вершину, которой инцидентно максимальное количество дуг графа.

  1.  

а) определить все пары вершин, связанных между собой прямыми и обратными дугами.

б) определить вершину, которой инцидентно минимальное количество дуг графа.

  1.  

а) определить вершину, из которой направлено минимальное количество дуг,

б) определить все вершины, имеющие петли.

  1.  

а) определить вершину, в которую направлено максимальное количество дуг;

б) определить количество дуг графа.

  1.  

а) определить вершину, из которой направлено максимальное количество дуг;

б) определить сумму степеней вершин графа.

  1.  

а) определить, является ли построенный граф связным;

б) определить все вершины, достижимые из вершины 3 по двум  дугам.

  1.  

а) определить, из каких вершин направлены ребра в вершину 4;

б) определить вершину, в которую не входит ни одна дуга.

  1.  

а) определить, образуют ли цикл вершины 1,3,4;

б) определить вершину, из которой не выходит ни одна дуга.

  1.  

а) определить полустепень захода заданной вершины

орграфа;

б) определить являются ли две заданные дуги смежными.

  1.  

а) определить полустепень исхода вершины 3 орграфа;

б) определить являются ли две вершины 3 и 4 смежными.

  1.  

а) определить полустепень исхода вершины 2 орграфа;

б) определить являются ли две вершины 3 и 4 смежными.

1.5. Контрольные вопросы

  1.  Что такое система, подсистема, элемент, связь?
  2.  Что такое внешняя среда, входы и выходы системы?
  3.  Что такое состояние элемента (системы) и процесс?
  4.  Как связаны между собой потребность и цель?
  5.  Как классифицируются системы?
  6.  Что такое структура системы?
  7.  Почему структура является статической моделью системы?
  8.  Какие основные матричные способы задания графов?


 

А также другие работы, которые могут Вас заинтересовать

26001. Особенности древнекитайской философии. Конфуцианство 34.09 KB
  Философия Бакунина Михаил Александрович [1830. В эти годы Бакунин Михаил Александрович последователь философии И. В Берлинском университете Бакунин Михаил Александрович слушал лекции К. В Цюрихе Бакунин Михаил Александрович познакомился с В.
26002. Натурфилософия Древней Греции. Сущность материализма 29.47 KB
  Жан Жак Руссо .В любом из произведений Руссо непрестанно звучат четыре лейтмотива: культ личности чувствительность культ природы и ощущение социальной несправедливости. Эти Руссо замечает что жизнь человека в этом лучшем из миров не соответствует его подлинной сущности что человек не таков каким он должен быть согласно своей истинной природе но и представляется не тем что он есть на самом деле люди не решаются показаться тем что они есть стало выгоднее притворяться не таким каков ты есть на самом деле. Чем больше накапливаем...
26003. СМО с бесконечной очередью для пуассоновских потоков. Граф, система уравнений, расчетные соотношения 23.44 KB
  СМО с бесконечной очередью для пуассоновских потоков. Из СМО с очередью конечной длины можно получить СМО с неограниченной очередью если устремить. Рассмотрим частный случай одноканальной системы с бесконечной очередью
26004. СМО с бесконечной очередью для произвольных потоков. Граф, система уравнений, расчетные соотношения 30.06 KB
  СМО с бесконечной очередью для произвольных потоков. Рассмотрим случай который можно интерпретировать либо как наличие немедленного обслуживающего прибора интенсивность обслуживания которого растет линейно с ростом числа ожидающих требований либо как систему в которой всегда найдется новый обслуживающий прибор доступный каждому вновь поступающему требованию. СМО типа М М ∞ с бесконечным числом обслуживающих приборов Переходя к равенству: Получаем: Можно выписать искомые решения для pk и N: Условие эргодичности в данном случае также...
26005. СМО с бесконечной очередью и частичной взаимопомощью для пуассоновских потоков. Граф, система уравнений, расчетные соотношения 60.64 KB
  СМО типа М М m Переходя к решению для pk в соответствии с равенством: Видим что это решение должно быть разбито на две части так как зависимость k от k также имеет две части. Соответственно при k≤m: Аналогично при k≥m: Объединяя результаты получим: Где: Теперь с помощью: Можно выписать решение для p0: И следовательно: Вероятность того что поступающее требование окажется в очереди задается равенством: Таким образом:.
26006. СМО с бесконечной очередью и частичной взаимопомощью для произвольных потоков. Граф, система уравнений, расчетные соотношения 35.06 KB
  Эта система в строгом смысле является саморегулируемой. Подходящей моделью для описания такой системы является процесс размножения и гибели при следующем выборе параметров: Система является эргодической.
26007. СМО с бесконечной очередью и полной взаимопомощью для пуассоновских потоков. Граф, система уравнений, расчетные соотношения 32.91 KB
  Каждое вновь поступившее требование подается на свой отдельный обслуживающий прибор однако если требование поступает в момент когда все приборы заняты то оно теряется.
26008. СМО с бесконечной очередью и полной взаимопомощью для произвольных потоков. Граф, система уравнений, расчетные соотношения 46.78 KB
  Такая модель задается следующим образом: Эта система является эргодической. СМО типа М М ∞ М Для вероятностей pk этой системы из: Имеем: Где биноминальные коэффициенты определяются обычным образом: Определяя p0 получаем: И следовательно: Таким образом: Не составляеет труда вычислить среднее число требований в системе: Используя частную производную получаем:.
26009. СМО с конечной очередью для пуассоновских потоков. Граф, система уравнений, расчетные соотношения 76.36 KB
  Длина очереди m число мест в очереди. Если все места в очереди заняты то заявка получает отказ. Если при обслуживании освобождается канал то из очереди переходит очередная заявка на обслуживание; все заявки сдвигаются и вновь поступившая заявка ставится в конец очереди. вероятность того что заявке придется стоять в очереди вероятность очереди: 4.